2025 ICPC 上海个人补题笔记，有哪些技巧分享？

赛事信息 题目链接：https://codeforces.com/gym/105992 赛事榜单：https://board.xcpcio.com/provincial-contest/2025/shanghai?group=official 这场打的有点倒闭，只出了3道题，感觉心态还是比较炸，唉，好好补题了。 D. 与或博弈 题意： gsh 与 AI 轮流操作两个非负整数 \(a\) 和 \(b\)，gsh 先手。 gsh 目标：将 \((a, b)\) 变为目标状态 \((x, y)\)，达成则获胜； AI 目标：阻止 gsh 达成目标，阻止成功则获胜。 gsh 操作（二选一） 按位与操作：\(a := a \& v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）； 按位或操作：\(b := b \mid v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）。 AI 操作（二选一） 按位或操作：\(a := a \mid v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）； 按位与操作：\(b := b \& v\)（\(v\) 为任意非负整数，满足 \(0 \le v < 2^{60}\)）。 双方均采取最优策略，若在 \(10^{100}\) 回合内，某一时刻满足 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则 AI 获胜。 思路+代码：   这道题可以大胆猜一个结论，然后来分析这个结论，那就是 gsh 的操作只要一次不能成功，那么之后就都不能成功。   接下来从证明的角度来证明为啥这个结论是对的，证明如下：     我们先假设能操作成功，那么这一步成功操作必然是 gsh 进行的，因为无论是什么结果 Ai都有能力保证操作至少不会向着成功方向靠近。由于 gsh 每一次操作只能操作 \(a\) 或 \(b\) 两个数字中的一个，所以最后一步必然要保证 \(a=x\) 或者 \(b=y\) 有一个成立，由于 AI 会进行干扰，所以对于出现最后一步这种情况就只有以下两种比较合理的可能： 刚开始的时候 \(a=x\) 或者 \(b=y\) 就有一个成立。 gsh 可以先满足 \(a=x\) 或者 \(b=y\) 有一个成立，且确保这种成立不会被 AI 改变，然后 gsh 再试图让另一个数字成立。   对于第一种情况而言，可以充分说明如果 gsh 的操作只要一次不能成功，因为 AI 可以让 gsh 不能成功的数保持不变，那么 gsh 无论如何都不会成功。   对于第二种情况而言，就需要好好思考 \(\&\) 和 \(|\) 运算了。从二进制的角度考虑，对于 \(\&\) 运算而言， \(\&\) 无法让 0 变成 1 ，而对于 \(|\) 运算而言，\(|\) 无法让 1 变成 0 。所以对于 \(a\) 和 \(x\) 而言，如果某一位 \(a\) 是 0 而 \(x\) 是 1 则本质上 \(a\) 就不能变成 \(x\) ，如果 某一位 \(a\) 是 1 而 \(x\) 是 0 那么 AI 仍可以让 0 变成 1 来使得 \(a ≠ x\)，然后退回到 \(a≠x\) 且 \(b≠y\) 的时候。 对于 \(b\) 和 \(y\) 而言，如果某一位 \(b\) 是 1 而 \(y\) 是 0 则本质上 \(b\) 就不能变成 \(y\) ，如果 某一位 \(b\) 是 0 而 \(y\) 是 1 那么 AI 仍可以让 1 变成 0 来使得 \(b ≠ y\)，然后退回到 \(a≠x\) 且 \(b≠y\) 的时候，因此第二种情况并不存在。   因此 gsh 的操作只要一次不能成功，那么之后就都不能成功。