附:出题组题解(繁中)。
A(不可做)
B
递归贪心地构造,若当前点有未走的相邻点,且没有 \(p_{i+1}\),那么当前点就要连 \(p_{i+1}\),递归 \(p_{i+1}\)。否则我们可以先回溯。
C
发现其中有一个人每次都只能选偶数。
- 当 \(l\) 为奇数时:
- 若 \(r<2l\) 则怎么选都不会影响另一个人,判断 \(r-l\) 的奇偶性即可。
- 否则先手可以开始选 \(2l\) 必胜。
- 当 \(l\) 为偶数时:
- 若 \(r<2(l+1)\) 则怎么选都不会影响另一个人。
- 否则后手可以开始选 \(2(l+1)\) 而获胜。
D
目标是把 \(a_{n-1}\) 和 \(a_n\) 都变成 \(0\)。同时发现连续的一段 1111000
可以变成 1010101
,这意味着可以把前面的 1 往后移。
需要细致地分类讨论。
- 若 \(a_{n-1}=1\)。
- 要使 \(a_{n-3}=1\)。也可以使 \(a_{n-4}=1\) 且 \(a_{n-2}=1\)。
- 若 \(a_{n-1}=0\) 且 \(a_n=1\)。
- 要使 \(a_{n-4}=1\land a_{n-3}=1\) 或 \(a_{n-4}=1\land a_{n-2}=1\) 或 \(a_{n-3}=1\land a_{n-2}=1\)。
把前面的 1 往后移时,要限制移到的位置,然后才能 check 以上条件。移的时候要一位一位移。
E(未过)
在点双上考虑合法的图长什么样。
F(未过)
分治 FFT。
G
二分答案。每条直线可以贡献一个前缀或后缀,贪心地选即可。
H
把 \(n=2,3,4\) 的玩出来,然后每次消掉最后三行归约成 \(n-3\) 的问题,具体构造看题解。
I
每次合并相当于连 \(k-1\) 条边,那么 \(p\) 从后一定是 \(p(k-1)+1\) 个点的乘积。找到最大的 \(p\) 使得乘积非 \(0\) 即可。注意 \(p=0\) 要对 \(a_1\) 取模。
J
首先建树,可以扫描线后用线段树加底层 set
维护。
然后每次修改,考虑与两个 DFS 序相邻的关键点 LCA 的最深哪个,那么 \(x\) 到这个 LCA 上所有点贡献都会改变。用 BIT 维护 \(s_i\) 表示深度为 \(i\) 的合法点数,每次修改都是区间加。
K
对于每个左部点,保留最大 \(K\) 条边,然后再在此基础上每个右部点保留最多 \(K\) 条边。这是因为如果匹配了被一条扔掉的边 \((u,v)\),那么 \(u\) 还有权值更优的至少 \(K\) 条边,此时一定能替换使得更优。
然后在这 \(O(nK)\) 条边保留最大的 \((2k-1)(k-1)+1\) 条边即可,这是因为每匹配一条边,就会阻挡 \(2k-1\) 条边,\(k-1\) 轮都是如此,最后一轮还需一条边。
对这 \(O(K^2)\) 条边用 SPFA 跑费用流,复杂度 \(O(K^4)\)。
L(未过)
DP 题。
M(未过)
\(Z\) 最大和 \(Z=0\) 的点一定在圆内,记组成集合 \(S\)。而其他点就没有区分了,它们都在圆上,记组成集合 \(P\)。
- \(|P|=0\),找一个无限大的圆即可。
- \(|P|=1\),要求存在一条直线,使得 \(S\) 中所有点都在直线的一侧。
- \(|P|\ge3\),圆是确定的。
- \(|P|=2\),假设 \(P=\{X,Y\}\),线段 \(XY\) 一定是一条弦,找到弦两侧分别使得圆周角最小的 \(S\) 中的点,此时圆会最大,对这两个圆分别 check 即可。