MENU

Solution. Codeforces Round #779

Div.2 only，打得烂到飞起，简直像是一年前的自己。

上来先 D 开，一看发现 D 大概很简单，写了一发过了 D1 的 pretests，D2 看了看没啥思路就先放着，A 和 B 打完之后（B 上浪费了不少时间）跑去看 C，结果想了一辈子也不会，实际上我那个 -1 的 submission 已经无限接近正解了。

然后 D1 fst 了，原因是多测每次暴力 memset 清空了 8×105 的数组，t≤105 直接挂穿，所以很多时候还是应该暴力清空，最有竞争力的一道题没了这场也就直接裂开。

但是排除 D1，我觉得 C 和 D2 做不出来也是挺大的问题。

A. Martin and Photoshoot 展开目录

没什么好说的，我觉得样例给的提示已经够多了，最后的答案一定是形如 0110110 这样的，i.e. 两个 0 之间至少有两个 1，随便打打就行了。

Code 

  • namespace Main{

  •     const int N = 105;

  •     int t, n, ans;

  •     char s[N];

  •     void Main(){

  •         input(t);

  •         while(t--){

  •             input(n); scanf("%s", s);

  •             ans = 0;

  •             bool flag = false;

  •             for(int i = 0, c = 0; i < n; i++){

  •                 if(s[i] == '0'){

  •                     if(!flag) flag = true;

  •                     else ans += max(0, 2 - c);

  •                     c = 0;

  •                 }

  •                 else c++;

  •             }

  •             write(ans), puts("");

  •         }

  •         return;

  •     }

  • } // namespace

B. Martin and Anti-coprime Permutation 展开目录

这个题放在 B 应该算是道好题。

样例丢到 oeis 你就可以查到这个数列的通项，但是这很没意思。

题目给出的式子是这个样子的，若 p1…n 是 1∼n 的一个排列，求满足

gcd(1⋅p1,2⋅p2,3⋅p3,…,n⋅pn)>1

的 p1…n 的数量。

Observation. gcd≤2

证明很简单，1∼n 中含有 3 这个质因子的数的数量应该是 ⌊n3⌋，在 1⋅p1∼n⋅pn 中也最多只能使得 2⌊n3⌋ 个数拥有 3 这个质因子，这显然无法使 gcd=3，更大的质因子同理。◼

结合题目要求，我们有 gcd=2，此时我们要求 2⌊n2⌋=n，即 n 为偶数，换言之 n 为奇数时答案为 0。当 n 为偶数时，将 1∼n 分为奇数和偶数两类，p 中的奇数与系数中的偶数匹配，另一类同理，故答案为 ((n2)!)2。

式子有了之后我随手打了个代码验证 n=1000 的情况，但是没打最后那个平方，导致我一度怀疑我的式子是错的。

Code 

  • namespace Main{

  •     const int MOD = 998244353;

  •     int t, n;

  •     void Main(){

  •         input(t);

  •         while(t--){

  •             input(n);

  •             if(n & 1) { puts("0"); continue; }

  •             ll ans = 1;

  •             for(int i = 1; i <= (n >> 1); i++) ans = ans * i % MOD;

  •             write(ans * ans % MOD); puts("");

  •         }

  •         return;

  •     }

  • } // namespace

C. Shinju and the Lost Permutation 展开目录

首先最容易发现的是 c1…n 中应当恰好有一个 1，对应着原排列中的最大值 pk。

对于任意一个数 pi 而言，当它被旋转到开头时，考虑此时的前缀最大值数组，我们依次往后扫，一旦遇到 pk，后面就全部会被推平，也就是说 pk 后面的内容是无需考虑的。

那么我们不妨也对 c1…n 作一下修改，将 1 旋转到开头，这不会影响我们判断合法性，为了方便描述，ci 对应的 pj 我们称之为 pi′。

容易发现，ci 的取值取决于 p1…i−1′ 中最后一个大于 pi′ 的那个数，不妨称之为 pj′，那么 ci=cj+1，于是就有了我的赛时做法，即 ci 应当不大于前缀最大值 +1。

但实际上这个条件是不充分的，如果 pi′>pi−1′，那么 ci≤ci−1；如果 pi′<pi−1′，那么显然 ci 应该从 ci−1 转移，i.e. ci=ci−1+1，于是我们得到了一个更强的限制条件，ci≤ci−1，这样就正确了，可以通过构造进行证明。

Code 

  • namespace Main{

  •     const int N = 100005;

  •     int t, n, a[N<<1];

  •     void Main(){

  •         input(t);

  •         while(t--){

  •             input(n);

  •             int cnt = 0;

  •             for(int i = 0; i < n; i++) input(a[i]), cnt += (a[i] == 1);

  •             if(cnt != 1) { puts("NO"); continue; }

  •             for(int i = n; i < (n << 1); i++) a[i] = a[i-n];

  •             bool flag = true;

  •             for(int i = 0; i < n; i++){

  •                 if(a[i] != 1) continue;

  •                 int m = 0;

  •                 for(int j = 0; j < n; j++){

  •                     if(a[i+j] > m + 1) { flag = false; break; }

  •                     else m = a[i+j];

  •                 }

  •                 break;

  •             }

  •             puts(flag ? "YES" : "NO");

  •         }

  •         return;

  •     }

  • } // namespace

至于构造一组合法解，我们考虑这样的过程。注意这建立在 p1′ 为最大值的基础上，构造完再转回去就行了。

我们将转移关系建成一棵以 1 为根的树，具体的，如果 i 从 j 转移而来（即 ci=cj+1，如果有多个 cj 等价就任意选择一个，构造出来的都应该是可行解），我们就连一条 i→j 的边。

接下来，按深度从小到大为第一关键字，下标从大到小为第二关键字排序，依次分配 n,n−1,…,1，这样就能够造出合法的 p1…n′。

（口胡的，不保证正确性，如果假了请务必告诉我 /bx）

D. 388535 展开目录

只讲我的做法，你也可以去研究研究官方题解。

先从 easy version 开始，easy version 保证了 l=0，这意味着原本的 a0…n 中应当存在一个 0，操作之后这个数就变成了 x，这意味着我们可以遍历 a0…n，对于每个数假设它是 x，然后检查是否合法。

检查的方式也很简单，我们希望所有数在异或之后恰好为 0…n，注意到异或之后必然满足所有数两两不同，同时必然存在一个 0（当前遍历到的数异或上自己），这样我们只需要保证异或后的最大值为 n 即可，查询异或最大值的操作可以使用 01trie 完成。

fst 的原因在前面讲过。然后我很疑惑的就是我已经拥有了一个可拓展性如此强的做法为什么我当时不会做 hard version。

如果你是像上面一样完成的 easy version，那么 hard version 的做法就无比显而易见，我们类似的假设每个数是 l⊕x，然后用 01trie 检查一下最小值，检查一下最大值即可。

我当时居然觉得我的做法是建立在原排列中含有 0 的基础上的，实在是不可理解，这个 0 实际上换成啥都能做。

Code 

  • namespace Main{

  •     const int N = 200005;

  •     int t, l, r, a[N];

  •     struct trie{

  •         static const int L = 20;

  •         int ch[N<<1][2], cnt = 1;

  •         void init() { for(int i = 1; i <= cnt; i++) ch[i][0] = ch[i][1] = 0; cnt = 1; }

  •         void insert(int x){

  •             for(int i = L, p = 1; i >= 0; i--){

  •                 if(!ch[p][x>>i&1]) ch[p][x>>i&1] = ++cnt;

  •                 p = ch[p][x>>i&1];

  •             }

  •         }

  •         int queryMin(int x){

  •             int res = 0;

  •             for(int i = L, p = 1; i >= 0; i--){

  •                 if(ch[p][x>>i&1]) p = ch[p][x>>i&1], res += (x >> i & 1) << i;

  •                 else p = ch[p][~x>>i&1], res += (~x >> i & 1) << i;

  •             }

  •             return res;

  •         }

  •         int queryMax(int x){

  •             int res = 0;

  •             for(int i = L, p = 1; i >= 0; i--){

  •                 if(ch[p][~x>>i&1]) p = ch[p][~x>>i&1], res += (~x >> i & 1) << i;

  •                 else p = ch[p][x>>i&1], res += (x >> i & 1) << i;

  •             }

  •             return res;

  •         }

  •     }tree;

  •     void Main(){

  •         input(t);

  •         while(t--){

  •             tree.init();

  •             input(l, r);

  •             for(int i = 0; i < r - l + 1; i++) input(a[i]), tree.insert(a[i]);

  •             for(int i = 0; i < r - l + 1; i++){

  •                 int x = a[i] ^ l;

  •                 if((tree.queryMin(x) ^ x) == l && (tree.queryMax(x) ^ x) == r){

  •                     write(x);

  •                     puts("");

  •                     break;

  •                 }

  •             }

  •         }

  •         return;

  •     }

  • } // namespace

E. Gojou and Matrix Game 展开目录

随便手玩一下会发现，游戏可以被转化到有限步内，也就是要求下一步走到格子的点数应该比上一步大。

假如玩家 A 走到了某个格子，玩家 B 无法找到点数更大的合法格子了，那么 B 就只能选择一个更小的格子，下一步 A 再走回原来的位置，这样循环下去也就必然是 A 获胜。

接下来是博弈题的常规做法，点数最大的格子为必胜态，接下来按照点数从大到小遍历所有格子，只能走到必败态的格子是必胜态，否则是必败态，dp 即可。

难点在于如何判断「只能走到必败态」，转换一下也就是，所有必胜态到当前位置的曼哈顿距离都 ≤k，似乎很难处理。这里需要的技巧就是曼哈顿距离转化为切比雪夫距离，也就是：

|xi−xj|+|yi−yj|=max{|(xi+yi)−(xj+yj)|,|(xi−yi)−(xj−yj)|}

实际上就是讨论了曼哈顿距离中两个绝对值开出来后是同号还是异号。

那么维护 xi+yi 和 xi−yi 的最大值与最小值即可。

最后的转化是技巧性的，前面其实都很常规。

Code 

  • namespace Main{

  •     const int N = 2005;

  •     int n, k, l, r, u, d;

  •     vector<array<int, 3>> a;

  •     bool f[N][N];

  •     void Main(){

  •         input(n, k);

  •         for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) a.push_back({i, j, read<int>()});

  •         sort(a.begin(), a.end(), [](array<int, 3> a, array<int, 3> b){

  •             return a[2] > b[2];

  •         });

  •         l = a[0][0] + a[0][1]; r = a[0][0] + a[0][1];

  •         u = a[0][0] - a[0][1]; d = a[0][0] - a[0][1];

  •         for(array<int, 3> x: a){

  •             if(abs((x[0] + x[1]) - l) <= k && abs(r - (x[0] + x[1])) <= k && 

  •                abs((x[0] - x[1]) - d) <= k && abs(u - (x[0] - x[1])) <= k){

  •                 f[x[0]][x[1]] = true;

  •                 l = min(l, x[0] + x[1]); r = max(r, x[0] + x[1]);

  •                 u = max(u, x[0] - x[1]); d = min(d, x[0] - x[1]);

  •             }

  •         }

  •         for(int i = 0; i < n; i++){

  •             for(int j = 0; j < n; j++) putchar(f[i][j] ? 'M' : 'G');

  •             puts("");

  •         }

  •         return;

  •     }

  • } // namespace

F. Juju and Binary String 展开目录

CF 上原本这题的 Editorial 非常的 confusing & cryptic，虽然我认为并没有到完全无法理解的程度。这篇博客写到这里的时候官方题解已经进行了修改，修改过后篇幅长了不止一倍，所以我没有太过仔细的阅读修改过后的题解。
如果你希望去阅读官方题解，建议你略过 Hint 2 中的 Author's Proof，那里大概率是使用了大量篇幅来证明「离散型中间值定理」，不妨去看看 Contestant's Proof，也就是 smax 给出的证明，那应该和接下来的内容基本一致。

首先为了保证选出的长度为 m 的串拥有与原串相等的可爱程度，我们需要保证 t=m⋅onen 为整数，其中 one 为原串中 1 的个数，t 即为我们需要选出的串中 1 的个数。

我们将原串放在环上考虑，接下来证明我们只需要选取一段子串就能够满足题目要求，如果放到原串上考虑，由于选取的子串可能会被环的连接处截断，我们证明的即是 k≤2。

我们令从 i 开始长度为 m 的子串中 1 的个数为 ci，感性理解一下不难发我们有 min{ci}≤t≤max{ci}(1)，如果需要严格证明也很简单。

我们将所有的 ci 加在一起，在环上考虑所有长度为 m 的子串时，每个元素都被恰好考虑了 m 次，于是有 ∑ci=m⋅one=n⋅t，自然也就不可能存在 ∀ci,ci>t 或 ∀ci,ci<t 的情况。◼

另外容易发现的是，|ci−ci−1|≤1(2)，因为删除的对 c 的贡献是 0 或 −1，添加对 c 的贡献是 0 或 1。

结合 (1)(2)，通过离散型中间值定理（Discrete Intermediate Value Theorem，DIVT），我们容易得到 ∃k,ck=t。

关于离散型中间值定理，务必区别于中值定理 Mean Value Theorem，中文的魅力 /fad。
这里的中间值定理指的就是通常说的勘根定理，离散情况下仍然成立，我们可以类似的认为是离散变量「穿过」了某条界线，在本题中就是从 min 「穿过」 t 到达了 max。

那么只需要维护在环上维护一个长度为 m 的窗口，或着直接使用前缀和，检查其中 1 的个数是否为 t 即可，请注意优先检查不越过环连接处的子串，即优先判断是否存在 k=1 的答案。

Code 

  • namespace Main{

  •     const int N = 200005;

  •     int t, n, m, s[N<<1];

  •     char a[N<<1];

  •     void Main(){

  •         input(t);

  •         while(t--){

  •             input(n, m); scanf("%s", a + 1);

  •             for(int i = n + 1; i <= (n << 1); i++) a[i] = a[i-n];

  •             for(int i = 1; i <= (n << 1); i++) s[i] = s[i-1] + (a[i] == '1');

  •             if(1ll * m * s[n] % n != 0) { puts("-1"); continue; }

  •             int k = 1ll * m * s[n] / n;

  •             for(int i = 0; i < n; i++){

  •                 if(s[i+m] - s[i] == k){

  •                     if(i + m > n){

  •                         puts("2");

  •                         write(1), putchar(' '), write(i + m - n), puts("");

  •                         write(i + 1), putchar(' '), write(n), puts("");

  •                     }

  •                     else{

  •                         puts("1");

  •                         write(i + 1), putchar(' '), write(i + m), puts("");

  •                     }

  •                     break;

  •                 }

  •             }

  •         }

  •         return;

  •     }

  • } // namespace

本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。

博弈论构造Codeforces RoundTrie
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment