ABC166F Solution

irris · 2024-04-01 16:36:03 · 题解

除非初始操作了两个 0，否则发现当 a + b + c \geq 3 时，答案一定为 Yes。这只需要为初始 a = b = c = 1 设计一个合法的策略即可，而这是容易的，每一次贪心地使得局面不存在两个 0 即可。

对于 a + b + c \leq 1，只需模拟。因此现在考虑 a+b+c = 2 的情况。我们需要避免在所有数字构成可重集 \lang 2, 0, 0\rang 时操作的两个数均为 0。

因此当构成可重集 \lang 1, 1, 0\rang 时，假设下一次操作了两个数均为 1，我们需要考虑再下一次操作，如果不同于此次操作，则把 2 放到一个恰当的位置，就能再回到 \lang 1, 1, 0\rang；如果相同于此次操作，则可以选择反复横跳。这说明，除初始操作两个 0 以外，这种情况同样一定有解。

因为题解区的许多代码给出的是直接暴搜，在这里说明一下暴搜的正确性（即调用 dfs() 的次数为 O(n)）：

• 某次搜索无法进入下一步当且仅当操作了两个 0。
• 如果原问题有解，则其中一个 0 一定是上一次操作产生的，只需回退一步即可向后搜索，且此分岔必然不会产生两个 0。
• 因此每一轮操作最多被回溯一次。