2023-12-30

收集的是原题。 ## 题解： ### T1：【树上异或】题解 Source：ARC148C，洛谷绿 #### 测试点 1~3 显然一个点只会操作一次，要不然操作就抵消了。 爆搜，枚举每个点是否操作，时间复杂度 $O(2^nq)$，可得 15 分。 #### 测试点 4~6 考虑 $O(nq)$ 的做法。考虑从上到下 dfs 每个点，如果这个点还是开着的就对子树进行一次操作。直接做是 $O(n^2q)$ 的还是 15 分，可以考虑记录一个向下的操作次数奇偶性就可以知道这个点是否被操作过了。可得 30 分。 另一种想法是，设 $f(i,0/1)$ 表示 $i$ 子树内全部设为 0 的最小次数，进行树形 DP，但这做法显然是没前途的。 #### 测试点 7~8 $sz_i=1$ 时考虑按照上面的操作过程是怎么样的：对这个点 $x$ 要进行一次操作，然后 $x$ 的所有子节点都要进行一次操作（因为本来是 0，被异或成为 1 了），再往下就被抵消了，不需要进行操作。答案就是 $1+(x$ 的子节点个数$)$，即这个点的度数。结合上述做法可得 40 分。 #### 测试点 9~11 上一个部分分中，可以发现一个点的操作只会影响它和它的子节点，再往下就抵消了。当不存在父子关系时，答案即为每个点的答案之和。结合上述做法可得 55 分。 #### 测试点 12~20 直接给出结论：把集合内连通的点看作一个点，则答案为缩点后所有点的度数之和。 在部分分引导下这是比较好想的。显然最上面的那个点会进行操作，再往下到一个没有标记的点再操作一次来抵消上面的操作。 如果写得好可以做到 $O(n+\sum sz_i)$。但是放过了所有带 log 的维护方法，时间限制是 map + vector 实现的 std 的 2.5 倍。 性质 CD 留给不会维护的人。 最后两个点是菊花，如果 T 了可能复杂度有问题。 ### T3：【加了个加】题解 Source：ARC122C，洛谷蓝 ### 测试点 1~2 输出 $n$ 个 1 的构造。可以获得 8 分。 ### 测试点 1~7 考虑操作次数根号。先让 $B + 1$ 加 $\sqrt n$ 次，让 A 先加上 B 加 $\lfloor \dfrac{n}{B}\rfloor$ 次，再加上若干次 1 即可。 操作次数在 $3 \sqrt n$ 以内，可以得到 28 分（实际 32 分）。 ### 测试点 1~? 暴力 DP，设 $f(i,j)$ 表示 $A=i,B=j$ 是否可行，以及若可行的上一个操作。时间复杂度 $O(n^2)$，操作次数可以达到最优，可以得到 36 分。 进一步地乱搞，可以枚举一个 B，用记忆化搜索拆分，优先用操作 3 和 4 直到有一个 0 再用 1 和 2。可以得到 36~44 分。 有一种神奇的乱搞做法（第一篇题解）：令 B 在 $\dfrac{\sqrt5-1}{2}a$ 周围枚举，或者在 $\dfrac{n}{\text{a}}$ 周围随便枚举几个，可以直接获得 100 分，出题人也不知道为什么捏。 ### 中间的那些测试点 给奇怪算法，我没想到。 ### 测试点 14~19 正解的重要暗示。先让 $A=B=1$，考虑每次要叠加 $A,B$ 就是交替进行 3,4 操作。 ``` 0 0 1 0 1 1 2 1 2 3 5 3 5 8 13 8 ``` 就可以构造出来。可以获得额外的 24 分。 ### 正解 **考虑使用若干个斐波那契数加起来，构造出来 $n$。** 这是比较符合直觉的，同时也可以证明：任意正整数都可以被表示为若干个斐波那契数之和，并且这些数互不相等，互不相邻。 这个定理叫做 Zeckendorf 定理。我们使用数学归纳法证明它： **定理** 对于任意正整数 $n$，存在若干个数 $a_1,a_2,\cdots,a_m$，使得：$a_i$ 互不相等、相邻，且有：$n=\sum_{i=1}^mf(a_i)$，其中 $f(i)$ 表示斐波那契数列的第 $i$ 项。 证明：数学归纳法。 $n=1$ 时显然成立。 接下来假设 $n\le k$ 成立，我们要证明 $n=k+1$ 答案成立。 否则： - 当 $k+1$ 为斐波那契数时，成立。 - 当 $k+1$ 不是斐波那契数时，存在正整数 $t$ 使得 $f(t) < k+1 < f(t+1)$。则 $k+1$ 可以被表示为 $k+1-f(t)$ 与 $f(t)$ 之和。注意到 $k+1-f(t) \le k$ 一定能被表示，则 $k+1$ 也能被表示。 在这里，注意到我们有 $k+1-f(t) < f(t)$，则 $k+1-f(t)$ 的表示中一定不含有 $f(t)$ 这项，也就是说这些数字互不相同。同时，假设 $f(i)$ 和 $f(i+1)$ 都选了。那可以直接选 $f(i+2)。$ 也就是互不相邻。 证毕！ **推论** 贪心地对 $N$ 分解，只需从大到小枚举斐波那契数，如果这个数小于等于 $N$ 就让 $N$ 减去它，直到分解完毕。 这个构造就是数学归纳法的过程。 --- 接下来的任务是：怎么构造出来加？ 整个操作序列也不怎么能动。那你只能考虑用 +1 操作，在这个操作过程中找一个数让它 +1。注意到这个 1 会被多次叠加影响，且**随层数增加，影响的变化量 $\Delta$ 也会构成斐波那契数列**。 设你要加上的是 $fib(x)$，你只需要在 $s-fib(x)+1$ 行刚刚操作完的那个数字 +1 就可以完成这个事情，其中 s 是总层数： 比如在上面那个例子的基础上，你想要让 $n=13+5=13+fib(5)$。 ``` 0 0 1 0 1 1 2 1 -> 3 1 2 3 -> 3 4 5 3 -> 7 4 5 8 -> 7 11 13 8 -> 18 11 ``` 那么只需让 $n$ 分解成若干个斐波那契数就完成了。只需要从大到小贪心地取就可以了。 计算可得 $10^{18}$ 以内最大的是 $fib(86)$，因此根据定理，构造最大的比 n 小的斐波那契数的操作次数不会超过 86；剩余的操作次数也不会大于 86。更进一步的，根据推论 1，同时取 $f(i-1)$ 和 $f(i-2)$ 不如取 $f(i)$，因此相邻两个只有一个会被取，剩余的操作次数 $\le 43$，总操作次数在 130 以内，这也是原题的范围，这里为了方便就允许了 200 次操作。 ### T2、T4