526互联

2022 Jiangsu Collegiate Programming Contest

发布时间 2024-01-12 15:31:33作者: Smallbasic

A. PENTA KILL!

简单模拟。

B. Prime Ring Plus

大于 \(2\) 的素数只可能是奇数，因此相邻两个数一定是一奇一偶，容易想到二分图。

但是环上每个点有两个相邻的点，网络流求匹配是将与源汇点相连的边流量设为 \(2\) 即可。

C. Jump and Treasure

单次 dp 可以显然的用单调队列优化。

对于每个关都跑一遍，总点数是调和级数，可以通过。

D. Finding Pairs

能一起选的点 \(\bmod k\) 意义下都相同，我们按 \(\bmod k\) 的结果分类。

容易想到莫队，对于每个同余类，维护一个数组 \(f_{0/1.0/1}\) 表示当前左右两边有没有被选的情况的最大值。加入数是好做的，但是不能支持删除，回滚即可。

E. Playing Cards

我们把题意做转化：Alice 每次能用魔法选择 Bob 的一张牌使它的数字减去 \(k\)，或者选择自己的一张牌匹配 Bob 的一张更小的牌。要求使用魔法的次数最少。

不难想到贪心策略，当要匹配时，Alice 最大的牌一定会匹配 Bob 的最大的牌。我们每次取出 Alice 和 Bob 的最大牌，能匹配就匹配，否则就是用魔法将 Bob 的牌减去 \(k\) 后放回去。

注意直接维护这个过程是 \(O(n^2\log n)\) 的，需要使用数据结构维护。

F. Pockets

显然的生成函数。

设 \(f(x)=\sum v_ix^{w_i}\)，一开始会想到将所有物品的 \(w_i\) 减去 \(1\)，但是会出现 \(x^{-1}\) 项，它是没有意义的，所以考虑老实写式子，枚举购买次数：

\[\sum_{i=0}^m [x^{k+i}]{1\over 1-x} f^i(x) \]

很容易想到乘上 \(x^{-i}\) :

\[\sum_{i=0}^m [x^k]{1\over 1-x} {f^i(x)\over x^i} \]

但是如同之前所说，\(f(x)\over x\) 是没有意义的，我们考虑乘上 \(x^mf^m(x)\) 来消去分母上的 \(x\):

\[[x^{m+k}] {f^m(x)\over 1-x}\sum_{i=0}^m \left({x\over f(x)}\right)^{m-i}=[x^{m+k}] {x^{m+1}-f^{m+1}(x)\over (1-x)(x-f(x))} \]

多项式快速幂即可。

G. GCD on Bipartite Graph

条件等价于对于任意一个质数，一定有一边它的倍数的出现次数小于 \(2\)。

不妨设 \(n\le m\)，那么显然对于所有 \(\le {4\over 4}\) 的质数，第一个集合中至多只能出现一次它的倍数。可以推出当 \(n+m\) 充分大的时候，任意一个质数的倍数在第一个集合中只会出现 \(1\) 次。

于是对于 \(max(n,m)\le 30\) 的情况暴力搜索，其它情况在第一个集合放素数即可。

H. Super Gray Pony

这个构造方式就是格雷码，根据经典结论，\(a_x=x\oplus (x>>1)\)，题意转化为给你一个 \(n\) 位二进制数，进行 \(k\) 次 \(x\oplus (x>>1)\) 后的结果。

显然，最后 \(x_{i+j}\) 会在 \(x_{i}\) 异或上 \(\binom{k}{j}\) 次，显然只有它为奇数才有用。也就是说有贡献的 \(j\) 一定是 \(k\) 的子集。

设 \(f_i\) 表示考虑了 \(k\) 的后 \(i\) 位的结果，如果第 \(i\) 位是 \(0\) 那么无事发生，否则可以观察到 \(f_i = f_i\oplus (f_{i-1}>>2^i)\)，bitset 即可。

I. Cutting Suffix

有两个字母不同，可以构造方案使得答案为 \(0\)。否则所有字母都相同，答案显然为 \(n-1\)。

J. Balanced Tree

设 \(f_x\) 表示大小为 \(x\) 的 super balanced tree 的个数，如果 \(x\) 是奇数，则 \(f_x = f_{{x-1\over 2}}^2\)，否则 \(f_x = 2f_{x\over 2}f_{{x\over 2}-1}\)。

发现 \(f_x\) 一定是 \(2\) 的次幂，考虑求出指数。设 \(g_{i,0/1,0/1}\) 表示从下往上考虑到第 \(i\) 位，第 \(i\) 位为 \(0/1\)，下面是否有借位的次幂个数，dp 即可。

K. aaaaaaaaaaA heH heH nuN

简单构造。

L.Collecting Diamonds

显然可以按中间的 B 讲串分成若干组，每组形如 AAABCCC。

我们发现，只有删除 B 的操作会影响后面的奇偶性。所以我们尽量让每个组都删除一次 B，并在删除 B 之前删除尽可能多的 AC。

策略是显然的：先从后往前删去一次能删的 AC 数大于 \(1\) 的组。然后从前往后扫，记录在前面删了几次 B 即可。