A - Coprime Pair
给定区间，求区间中互质的两个数的差的最大值。
可以发现，很快可以发现答案，直接暴力做就是了。
查看代码
1 |
|
B - Count 1’s
给定一个 01 串，可以进行一次操作，使得一段区间的 $0 \to 1, 1 \to 0$ ，求 $1$ 的个数可能有多少个取值。
首先可以发现答案一定是连续的，即存在最小值 $mn$ 和最大值 $mx$ ，那么中间的任意 $x \in [mn, mx]$ ，都存在方案。
考虑如何求最大值和最小值，将 $1$ 的个数做前缀和。
如果翻转 $[l + 1, r]$ ，那么 $1$ 的个数为：
$$
\begin {aligned}
& s _ l + (r - l) - (s _ r - s _ l) + (s _ n - s _ r) \\
= & (s _ n - l + 2s _ l) + (r - 2 s _ r)
\end {aligned}
$$
当 $l$ 确定时，选择 $r - 2 s _ r$ 的最值即可。
查看代码
1 |
|
C - Distinct Numbers
结论：任何时候如果最大的两个数间隔大于 $1$ ，那么先手赢。
感性理解：前面有很多个空位，作为先手，可以选择补充一个前面的空位；也可以选择使得 $A _ n = A _ {n - 1} + 1$ ，令后手不得不去补前面一个空位。当没有空位的时候就输了，所以一直优势在我。
如果不存在这种情况，那么一定双方保证任意时候最大的两个数间隔不大于 $1$ ，那么最大值一定一次只能减少 $1$ ，当最大值为 $n - 1$ 的时候游戏结束，可以进行 $A _ n - (n - 1)$ 次操作，判断奇偶性即可。
查看代码
1 |
|
D - Prefix XORs
写出来几项找规律，发现一个数对答案有贡献当且仅当 $\binom {n - i + k - 1}{k - 1}$ 为奇数。
考虑卢卡斯定理，相当于对 $n - i + k - 1$ 和 $k - 1$ 二进制分解，考虑每一位乘起来，发现
$$
\binom {0}{0} = 1
$$
$$
\binom {0}{1} = 0
$$
$$
\binom {1}{0} = 1
$$
$$
\binom {1}{1} = 1
$$
也就是一旦出现某一位 $n - i + k - 1$ 为 $0$ 但是 $k - 1$ 为 $1$ 就没有贡献了，也就是 $k - 1$ 是 $n - i + k - 1$ 的子集，$n - i$ 是与 $k - 1$ 不相交的 $n - i + k - 1$ 的子集。如果将 $n - i$ 每一位取反，那么 $k - 1$ 是 $n - i$ 的子集 。记 $S$ 为一个所有位都是 $1$ 的数，那么 $k - 1 \subseteq S - (n - i)$ 。考虑 FMT ，用类似高维后缀和的方式可以快速地求出所有的答案。
查看代码
1 |
|
E - Bakery
看到题一下想到了 NOI2008 志愿者招募，基本一模一样。
多了一个放弃一个人 $D$ 的收益，相当于多一种人仅贡献当天，花费 $D$ 的代价。
——然而板子被卡了？？？
赛后将 spfa 换成 dijkstra 就过了。
分析复杂度：本题和志愿者招募不同的是这道题一个人只能用一次，那么流量上界为 $m$ 。那么 dijkstra 保证了复杂度为 $O(n ^ 2 \log n)$ ，用 spfa 大概为 $O(n ^ 3)$ 。其中 $n = 2 \times 10 ^ 3$ 。dijkstra 刚刚过，spfa 被卡飞。
查看代码
1 |
|