Codechef [June Long Two 2022] 题解

Codechef月赛的时间很友好，一共有三天而且不拼手速。缺点就是题解有的很难懂，而且好像这次数学+构造题偏多（个人不太喜欢hhh） 。题目质量难度设置的不错。

Complementary Strand in a DNA

给定一个规则，求一个字符串的补串。

简单字符串模拟。

Count the ACs

给出一个数组，每次操作可以把一个数字变成数组中的另外一个数字，求把所有数字变成同一个的最小操作数。

哈希+贪心即可。

Reversal Sorting

给定一个数组，每次操作可以把不超过X的子数组翻转，求是否能够通过有限操作把数组排序（升序）。

由于没有次数限制，每次可贪心只翻转两个数字。对于每个a_i，如果存在一个a_j(j<i)使得a_j>a_i，那么a_j至少要和a_i翻转一次（否则不能排序）。所以只需要确认左边最大的值和当前值的和是否超过X即可。

WA：不超过X应该是>=，手残写了>

Strong Elements

给定一个数组。对于一个数字，如果可以通过改变数字改变整个数组的gcd，那么这个数字就是Strong Elements。问这个数组中有多少个a_i是Strong Elements。

2<= N <= 3*10^5; 1<= a_i <= 10^9

数学+构造题。如果整个数组GCD不是1，那么把任意数字改变成1就可以把数组的GCD变成1，所以所有元素都是Strong Elements。否则（此时数组GCD是1），对于一个元素a_i，如果除了它所有其他元素的GCD不是1（假设是x），那么可以把a_i变成x使得整个数组的GCD变成x。

WA：一直wa，纠结于怎么处理第一第二个元素。看了题解其实可以做个前缀和后缀的GCD，然后看看prefix_gcd[i-1]和suffix_gcd[i+1]即可

AP Grid

给定一系列规则：（1）每行每列都是等差数列（2）所有等差数列的公差都是不一样的（3）最小化矩阵中的最大值（4）矩阵的数字都是正整数。求矩阵最大值的最小可能。

1<=N,M<=10^5

数学+构造题。可以假定矩阵第一行第一列为1，最后一行最后一列为最大值。慢慢推可以得知d_i-d_{i+1} = c_{i+1}-c_i，其中d_i为第i行公差，c_i为第i列公差。为了使得最大值最小（这里假定行多于或等于列），d_i、c_i应该形如（1）{1, 2, 3 ..., n} {n+1, n+2, .., n+m}或者（2）{1, 3, 5 ..} {2, 4, 6 ...}。最终可以推出最大值的公式，比较两个方案即可。

Gcd and Lcm

给定N，求N以内，A^2+B^2+gcd(A,B)^2+lcm(A, B)^2 = N的(A,B)个数。

1<= A, B <=N <= 10^10

数学+构造题。题解是利用A*B=lcm(A,B)*GCD(A,B)来消掉GCD(A,B)，只用lcm(A, B)和A和N来表示B^2。然后可以尝试枚举A，对于每个A枚举LCM，检查B是否为整数且满足条件。

WA：我用了比较复杂的方法假定A=nk,B=mk（n,m互质），把原式变成(A+B)^2+(gcd-lcm)^2=N <=> (n+m)^2+(1-nm)^2 = N/k^2。由于都是整数，左边可以枚举平方和，用二元一次方程求出A、B最后的式子。没有题解优雅。

The Subarray XOR
给定一个数组和整数K，如果一个子数组的异或和大于K，那么这个子数组是好的。求好的子数组个数。

1<= N <= 10^5; 0<= A_i <= 2^30; 0<= K <= 2^31

数据结构。区间（异或）和可以联想到前缀和，但便利一次数组就要O(N)，数据范围提示了算法应该是O(NlogN)级别。困难就在于怎么在log时间使得XOR(a_j, a_{j+1}, ... a_i} = prefix[a_i]^prefix[a_j-1] >= K的个数。可以想到用一个字典树来维护前缀和，对于一些分支可以直接累计（比如prefix[a_i] = "10111" K = "00111" 那么所有 a_j="0????" 都满足条件，不用递归下去）。

WA：数字范围很大，需要动态建点。改了下模板就好了。

Counting Is Fun

数学题，化简到最后就是求 Q次（每次N，K不相同）。

2<= M <= 10^3; 1<= Q <= 10^5; 2 <= N_i <= 10^5; 0<= K_i <= N_i-1

数学题。这题题解没看懂，自己推了好久的二项式好像也没有化简的方法。似乎有一些性质会让模拟有一个上限。以后有空再看看。