 赛后总结)
和昨天一样的 CCDD 。
如果说昨天的三个小时很充实的话，那今天的三个小时可以说是相当空虚了，因为什么也不会。
题目在这里！
A 鲁的要塞
去年做过，比今年还高 30 ，我真的要回去上 whk 了。
指挥中心的坐标一定是取 \(n\) 个要塞的坐标凑成，但不一定来自一个要塞（我因为忘了这一点挂了 70 ）。所以两层循环枚举指挥中心的坐标，再将要塞按照与指挥中心坐标的曼哈顿距离从小到大排序，依次枚举取几个要塞，答案取最小值即可。
B gcd
写了个略带优化的暴力，试过可以通过 \(n<=8 \times 10^4\) 的数据，还以为可以多骗两个点的分呢。思路是设 \(c=gcd(a,b)=a \oplus b\) ,然后去枚举 \(c\) ，再找符合条件的 \((a,b)\) 数对（显然 \(a=b\) 时无解，故钦定 \(a>b\) ）。对 \(c\) 二进制所有为 \(0\) 的位，\(a\) 和 \(b\) 一定是相同的，\(c\) 该位为 \(1\) 的时候二者就不同，这样构造出来后再检查它们的最大公约数是否与 \(c\) 相等。
正解也是枚举 \(c\) .但首先要明确有关 \(a\) 和 \(b\) 的两个结论：
- \(gcd(a,b) \le a-b\) .
- \(a \oplus b \ge a-b\) .
对结论 1 证明：设 \(c=gcd(a,b)\) , \(c\) 是 \(a\) 和 \(b\) 的公因数，则有 \(a=k_1 \times c,b=k_2 \times c,a-b=(k_1-k_2) \times c\) （ \(k_1,k_2\) 是正整数）. 又因为 \(a>b\) ,所以 \(k_1>k_2\) . \(k_1,k_2\) 是正整数，则 \(k_1-k_2>=1\) .那么就有 \(c \le (k_1-k_2) \times c\) . 代入得 \(c \le a-b\) .
至于结论 2 的话我还不是很理解，暂且先记下来。
有了这两个结论，就可以得出当 \(c=gcd(a,b)=a \oplus b\) 时，\(c=a-b\) .
这样之后就可以从 \(1\) 到 \(n\) 来枚举 \(c\) , 然后枚举 \(c\) 的倍数 \(a\) ,就可以求出 \(b\) 来，按照题意检查之后统计答案即可。复杂度为 \(\mathcal{O}(n \times \log{n})\) .
C 能源晶体
高一两个学弟都做出来了,一代更比一代强吗，我更觉得自己该回去上 whk 了。TT
写了个 dfs ，加了一些剪枝，比暴力 DP 还要快。因为 \(k\) 个能量储存仓是没有区别的，所以分配晶体时可以保证每个储存仓的晶体数量非严格递增。并且每分配完一个位置，就要看看在后面尽可能少分配的情况下（也就是都分配和它一样的数量），剩余的晶体是否足够，否则就返回。
题解说和第二类斯特林数有点相似，第一次听说去学了一下，一开始还真觉得就是它，但是思考了很久感觉实际上关联性并不大啊。第二类斯特林数是求将 \(n\) 个元素划分为 \(k\) 个集合的方案数，集合内的元素之间是有区别的；而这道题是求将 \(n\) 分解为 \(k\) 个无序正整数之和的方案数，集合的属性只关注其和。
举个例子。当 \(n=3,k=2\) 时，前者有 \(3\) 种方案，分别取两个元素在一个集合。而后者所求的方案数只有一种，那就是 \(1+2\) .
使用递推求解。令 \(f_{i,j}\) 表示前 \(i\) 个数划分为 \(j\) 个集合的方案数，将方案分为含 \(1\) 的和不含 \(1\) 的，就有转移方程式： \(f_{i,j}=f_{i-1,j-1}+f_{i-j,j}\) ,注意第二种转移在已划分数量小于集合数量的时候是不成立的。
D 逆序对
不会。这是 J 组的吗，还是我 DP 学得太烂乐。
学校食堂为什么不卖玉米肠了。我要哭了。