ICPC 2019 NWRRC D. Double Palindrome

求长度小于等于n,由前k个小写字母组成的字符串中,满足双回文串定义的有多少个。

双回文串:本身为回文串或者由两个回文串拼接成的字符串。

先计算双回文串可能的数量,令

\displaystyle R(n) = \sum_{i=0}^{n-1}k^{\lceil \frac{i}{2} \rceil}k^{\lceil \frac{n-i}{2} \rceil} 

考虑减去那些重复计算的字符串。可以发现如果一个字符串p的划分方式不唯一,那么这个字符串必然可以写成s \times m的形式,其中s是一个划分唯一的串。然后通过R(n)的表达式以及s \times m的性质,这个字符串被统计了m次。

则唯一划分字符串个数的表达式为\displaystyle D(n) = R(n)-\sum_{l|n, l < n} \frac{n}{l} D(l)。最后答案为\displaystyle \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor D(i)

R(n)可以通过简单的数学推导在线性时间复杂度内求出,其余计算的时间复杂度O(n \log n)

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 100010;
int f[maxn];
int pow(int x, int u){
    int y = 1;
    for (; u; u >>= 1, x = 1LL * x * x % mod) if (u & 1) y = 1LL * x * y % mod;
    return y;
}
int main(){
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        if (i & 1) f[i] = 1LL * i * pow(k, (i + 1) / 2) % mod;
        else f[i] = (1LL* i / 2 * pow(k, i / 2) + 1LL * i / 2 * pow(k, i / 2 + 1)) % mod;
    }

    for (int i = 1; i <= n; i++)
        for (int j = i + i; j <= n; j += i)
            f[j] = (f[j] - 1LL * j / i * f[i]) % mod;
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + 1LL * f[i] * (n / i)) % mod;
    if (ans < 0) ans += mod;
    cout << ans << endl;
}

Educational Codeforces Round 97 F. Emotional Fishermen

给出一个长度为n~(2\leq n \leq 5000)的数组a_1,a_2,a_3,...,a_n~(1\leq a_i \leq 10^9),求有多少种将a重新排列后的b满足对\forall~ 2 \leq i \leq n都有b_i \geq 2max\{b_1,b_2,...,b_{i-1} \}2b_i \leq max\{b_1,b_2,...,b_{i-1} \}

先将数组a升序排序。用f[i][j]表示最大值为a[i]长度为j的序列总数。考虑如下两种转移:

  • 在序列末尾加入一个大于两倍最大值的数,f[k][j+1] \leftarrow f[i][j]a_k \geq 2a_i,实现时使用前缀和优化
  • 从满足2a_k \leq a_i且未在序列中的数a_k中选择一个加入序列末尾,f[i][j+1] \leftarrow f[i][j] * (k - j + 1),其中k表示最大的k满足2a_k \leq a_i

时间复杂度O(n^2)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010;
const int mod = 998244353;
int a[maxn]; 
int sum[maxn][maxn], f[maxn][maxn];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int t = 0; sum[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        while (2 * a[t + 1] <= a[i]) t++;
        for (int j = 1; j <= i; j++) {
            f[i][j] = sum[t][j - 1];
            if (j - 1 <= t) {
                (f[i][j] += 1ll * f[i][j - 1] * (t - j + 2) % mod ) %= mod;
            }
        }
        for (int j = 0; j <= i; j++)
            sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
    }
    cout << f[n][n] << endl;
}

2020CCPC秦皇岛 I. Interstellar Hunter

给出一系列二维向量(x_i,y_i)~(0 \leq x_i,y_i \leq 10^6),问一个给定向量(x,y)是否可以被这些向量的整数组合表示。

首先显然向量组\{\boldsymbol{a}, \boldsymbol{b}\}与向量组\{\boldsymbol{a} \pm \boldsymbol{b}, \boldsymbol{b}\} 以及向量组 \{\boldsymbol{a}, \boldsymbol{b} \pm \boldsymbol{a}\}所能生成的点集等价。

于是若已知向量组\{\boldsymbol{a}=(x_1,y_1), \boldsymbol{b}=(x_2,y_2)\},设g = (y_1, y_2),那么我们可以通过类似辗转相除的方法将向量组变成\{(tx_1, 0), (tx_2, g) \}。其中

\displaystyle tx_1 = \frac{y_2}{g}x_1 - \frac{y_1}{g}x_2, tx_2 = ax_1 + bx_2, ay_1 + by_2 = g

再加入一个新向量(x_3,y_3)时,可以继续把该向量与向量(tx_2,g)变换成(x,0)(tx_3,(g,y_3)),其中向量(x,0)可以和之前的向量(tx_1,0)通过gcd合并。

于是我们可以维护一个大小为2的与输入向量等价的向量基来进行判断。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1; y = 0; return a;
    }
    ll ret = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
int main(){
    int t, cas = 0;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        ll x = 0, y = 0, d = 0, ans = 0;
        while(n--){
            ll opt, tx, ty, w;
            scanf("%lld%lld%lld", &opt, &tx, &ty);
            if(opt == 1){
                if(ty == 0){
                    d = __gcd(d, abs(tx));
                    continue;
                }
                if(ty < 0) ty *= -1, tx *= -1;
                ll g, a, b;
                g = exgcd(y, ty, a, b);
                d = __gcd(abs(x * ty / g - tx * y / g), d);
                y = g;
                x = a * x + b * tx;
                if(d) x = (x % d + d) % d;
            }
            else{
                scanf("%lld", &w);
                if(y == 0){
                    if(d == 0){
                        if(tx == 0 && ty == 0)
                            ans += w;
                    }
                    else if(tx % d == 0 && ty == 0)
                        ans += w;
                }
                else if(ty % y == 0){
                    if(d && (tx - ty / y * x) % d == 0)
                        ans += w;
                    else if(!d && !(tx - ty / y * x))
                        ans += w;
                }
            }
        }
        cout << "Case #" << ++cas << ": " << ans << endl;
    }
    return 0;
}

东北赛回顾

1001

中期的时候喵了一下这题,成功把模型转换成最小生成树,然后就不会做了。

1002

网络流裸题。ly写完+WA*2,AC。

1003

题目大意:定义了一个模(x+1)的类似hash的函数F(x),再定义了一个函数g(n, m),表示一个数n经过mF嵌套后得到的值。求g(n, 1)g(n, m)的和。

solution:发现有人过了此题,我就去看了。开始感觉没什么思路,搞不懂这个F(x)是在干啥,也找不到什么规律。思考了一会之后感觉这个%(x+1)必有蹊跷,这样x只增不减,说不定很快就收敛了。然后迅速写了一个暴力发现果然是这样,交了一下WA。原来我的F(x)x=0的时候会输出1。。。修改了一下就过了。成功贡献一发罚时。

1004

题目大意:糖豆人模拟题。一个皇冠在0-H的高度上以1/s的速度上下移动,当且仅当皇冠高度小于等于h时,糖豆人才能够得着。给出每个人到达皇冠的时间和延迟,求最后谁最先摸到皇冠。

solution:本场我过的第二道题(说实话第一次看到此题的时候直接就跳了,以为会花很多时间)。做法很简单,计算到达皇冠的时候皇冠的位置,如果能够得着就直接结束,不行就再模拟计算一下皇冠下一次到达h的时间。最后加上延时sort一下。

1005

题目大意:构造一个包含NN01向量的向量组,每个向量中1的个数为K,且向量组在XOR运算下线性无关。

solution:写完1003就来看这题了,本以为可以通过贪心+线性基求第k大+二分过此题,然后发现事情没有这么简单,挣扎了10分钟后放弃了去看ly题。最后在czq写了一个较为奇妙但又WA又T的暴力然后不经意间看到了输出的答案发现了构造方法后PE了一下才A掉了这题(这合理吗.jpg)。

1007

题目大意:有K个人在打牌。有A,B,G,P四种牌,牌上有一个数字x。现在要给这K个人轮流发一共N张牌,每发一张牌会覆盖那个人上一次得到的牌。记cnt_i为发了这张牌后,桌面上数字和为5的牌的种类数。求cnt_1cnt_N的和。

solution:本场我过的第一题。说实话这题意我看了足足有5min。交的第一发初始化把i打成了另一个变量然后WA了一下。成功贡献一发罚时。做法也很简单,直接模拟。

1008

题目大意:给一个小写字符串,每次可以将一个连续的子串压缩,压缩方式是将连续的字母以单字母紧接一个16进制数来表示个数。现可以从原串中最多删去一个字母(删去后,两端的字符串不连续),求一个压缩结果最短的方案。若有多个方案使压缩结果最短,输出字典序最小的。

solution:看完1009就来看此题,和ly讨论了一下大致做法后就开写。一共WA了四次,原因是没发现可以选择子区间压缩:总结,一道阅读理解题+模拟题。做法就是将连续的字母提取出来,然后分为几种情况考虑。1.只有一个字母。2.连续两个字母。3.连续大于2个。对于第一种情况,不压缩比压缩优,于是删了后会使长度减少1;若删了后字典序变小(与后一个字母比较),则优先考虑位置靠前的否则尽量靠后。对于第二种情况,压缩比不压缩优(a2比aa字典序小),删了后会形成单字母,长度减少1,而字典序一定会增大,则尽量往后考虑。对于第三种情况,又分为两种情况:退位和不退位。退位(1000->FFF)长度-1,字典序增大,尽量往后考虑。不退位(1100->10FF, 1A00->19FF,etc.)长度不变,字典序减小,那么在长度-1不存在的情况下,选择首位删除。

1009

题目大意:给一个n*ndis矩阵,保证所对应的图联通且的边长是定值,求一个边数最小的子图,满足Dis矩阵和原dis矩阵相同。输出边数。

solution:在看1005的时候听ly高呼说这是多校原题()。我想那应该稳了。过了一会ly说复杂度不太对,然后我去看了一下题,看见了边长相等这个条件,告诉ly说这不是签到题吗(不懂为什么这么多人喷这题的题面,稍微细心一点还是能够理解的好吧)。ly发现事情真相后破口大骂,随即A掉此题。

1011

本场过的最后一题。当时不知道是否可以连续憋气,加上写了一个倍增维护答案,就一直WA。然后发现K大于1000的时候我的数组会溢出(竟然没有显示RE)。最后输入K的时候对1000取了一个min就A了。感觉挺离谱的。标程是用的单调队列,比倍增少个log,还很好写。当时怎么没想到用单调队列啊。。

1012

czq肝到比赛结束依然没有肝出来。

1013

签到题,czq写完一发A。

总结

这次夺冠也是我万万没有想到的。一些不足之处在于边界情况忘判导致的罚时以及题意阅读上的疏漏。