专栏文章

题解：P11629 [WC2025] Nim 游戏（暂无数据）

ww4p3r
P11629题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqdcua0
此快照首次捕获于
2025/12/04 02:57
3 个月前
此快照最后确认于
2025/12/04 02:57
3 个月前
查看原文
已经倒闭了，本题出的锅包括但不限于：
  • 第一问是 Topcoder 原题。
  • chk.cpp 会错误地返回 fail（输出 k=0,m′=0k =0 ,m' = 0 会让 chk.cpp 错误地认为 std.cpp 错误导致返回 fail）。
幽默的是，CTS 期间没有选手对此提出异议。因为在比赛 OJ fail 的返回也是 WA。
  • 数据水，导致原本应该 TLE/WA 的代码能够通过题目。
  • 赛后被发现出题人的 std.cpp 是错误的！
需要说明的是，只是我唐氏写错了，并不代表题目和赛时数据有任何问题（参见上一条）。验题人的 std.cpp 是至始至终完全正确的。
  • 题解中时间复杂度分析写错了。
本人对以上错误负有 100% 的责任，在这里向所有受到影响的选手致歉。
不过至少题目和赛时数据都是完全正确的。虽然存在原题和数据水的问题，但是考虑到极低的 AC 率（WC 2 人，CTS 0 人），基本上也可以将这两个问题忽略不计。
总体来说题目还是达到了比赛内一个正常题目的最低要求，再次对命题过程中出现的问题向各位致歉，也希望大家可以以此警戒。
本题解主要是对官方题解没有提及的严谨证明作一个补充。

思考思路

从高位到低位考虑。考虑到某位 ii 时，选择若干个位置 i1,i2,…,ilenii_{1}, i_{2}, \ldots,i_{len_i}，满足这些位置的 aixa_{i_x} 的第 ii 位为 00 （(a[i[x]] & (1 << i)) == 0），并将这些位置的 aixa_{i_x} 加至第 ii 位为 11（a[i[x]] += (1 << i) - (a[i[x]] & ((1 << i) - 1))）。
如果第 ii 位 11的数量为奇数，则 lenilen_i 应该为奇数，否则 lenilen_i 应该为偶数。如果该位全为 11 且 nn 是奇数返回 +∞+\infin。

贪心思路 I

若存在 xx 使得 axa_x 在 ii 及更低位为 00（(a[x] & ((1 << i + 1) - 1)) == 0），则有 leni≤1len_i \le 1 （取值取决于该位 11 的数量奇偶性）。
证明：
我们证明当前位 11 数量为偶数时一定有 leni=0len_i=0，其他情况实际等价。
反证法，不妨假设 leni=2len_i=2，我们选择了低位值分别为 pp 和 qq 将它们第 ii 位变成了 11。花费为 2i+1−p−q2^{i+1}-p-q。
这个操作对于低位的异或和影响至多为 p⊕qp \oplus q，而由于 ax=0a_x = 0 的存在，我们可以花费 p⊕qp \oplus q 的代价将异或和的影响消除，且存在 xx 满足 axa_x 在低位全为 00 的条件依旧存在（在对 p,qp,q 执行操作时会将低位清空）。
由于 p+q+(p⊕q)≤2×(2i−1)<2i+1p + q + (p \oplus q) \le 2 \times (2^i - 1) < 2^{i+1}，所以这个操作一定更劣。对于 lenilen_i 更大的情况可以递归证明，不再赘述。
leni≤1len_i \le 1 的反例出现在返回 +∞+\infin 的情况。即如果 nn 为奇数，且某位所有数都是 11，此时我们需要在更高位时执行至少一次 leni≥1len_i \ge 1。
而如果更高位都满足 leni=0len_i = 0，则必须选择某一位使其 leni=2len_i=2。具体哪一位可以暴力枚举选择。

贪心思路 II

对于 leni>1len_i > 1 的情况，选择 axa_x 在更低位的值 ((a[x] & ((1 << i) - 1))) 越大越优。
证明：
这个很简单，如果我们选择了一个更小的值 pp 而没有选择更大的值 qq 时得到了一个合法的方案，则可以交换 p,qp,q 在较低 ii 位的取值可以得到 kk 相同的方案。
一个类似的问题：
问：给定序列 a1,a2,…,ana_{1},a_{2},\ldots,a_{n} 和序列 b1,b2,…,bnb_{1},b_{2}, \ldots,b_{n}，是否能够重排 a,ba,b 使得 ∀1≤i≤n,ai≤bi\forall 1 \le i \le n, a_i \le b_i。
答：把 a,ba,b 从小到大排序，让小的 aia_i 去匹配小的 bib_i，大的 aia_i 去匹配大的 bib_i 即可。
具体做法参考 UOJ 群里面的官方题解吧。我懒得写了，本来我也只是来放个证明的。
最后正确的总时间复杂度应该为 O(nlog⁡nlog⁡V+mlog⁡3V)O(n\log n \log V + m \log ^3 V)。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...