Codeforces Global Round 23
【E1. Joking (Easy Version)】
很有趣的一道题目！
\(\operatorname{Observation 1}\)：YES 和 NO 可以互相转化，对某个集合回答 YES 相当于对其补集回答 NO。
\(\operatorname{Observation 2}\)：两次回答中至少有一次在说真话，如果连续两次都对某个集合回答了 NO，我们就可以确定 \(x\) 必不在该集合中。
考虑将 \(n (n \geq 4)\) 个数的范围缩小。记 \(\operatorname{mid}\) 为 \(1 - n\) 的中点，考虑询问集合 \([1, \operatorname{mid}]\)，如下图所示：
如果答案为 YES，记 \(\operatorname{mid'}\) 为 \(\operatorname{mid} - n\) 的中点，询问集合 \([\operatorname{mid}, \operatorname{mid'}]\)：
这时，如果答案为 YES，由 \(\operatorname{Observation 2}\) 就可知道 \(x\) 必不在 \([\operatorname{mid'}, n]\) 当中！
对于其他情况类似讨论一下即可，我们能够很轻易写出如下的代码：
int mid = (l+r)>>1;
query(l, mid); cin >> s;
if (s == "YES") {
int mid2 = (mid+r)>>1;
query(mid+1, mid2); cin >> s;
if (s == "YES") {
change(mid2+1, r);
r -= (r-mid2+1);
} else {
change(mid+1, mid2);
r -= (mid2-mid);
}
} else {
int mid2 = (l+mid)>>1;
query(l, mid2); cin >> s;
if (s == "YES") {
change(mid2+1, mid);
r -= (mid-mid2);
} else {
change(l, mid2);
r -= (mid2-l+1);
}
}
（query 函数和 change 函数可以在下方的提交记录中查看）
这时，我们就用两次询问缩小了 \(\frac{1}{4}\) 的范围，这太妙了，递归下去就能解决这个问题......吗？
此时又出现了一个 bug，当范围缩小至 \(n = 3\) 时怎么做？这就有点难了，设三个数分别为 \(a_1, a_2, a_3\)，具体步骤如下：
- 询问集合 \(\{a_1, a_2\}\)，
- 如果回答是
NO，那么我们就认为 \(x = a_3\)，提交一次答案，- 如果猜中了，游戏结束。
- 如果猜错了，我们的范围就缩小至 \(\{a_1, a_2\}\) 中。同时，我们知道上一次的回答在
Joking，下一次询问就必定会说真话！接下来就很容易了，询问集合 \(\{a_1\}\) 便能知道 \(x\)，提交答案，游戏结束。
- 如果回答是
YES，请继续向下看，
- 如果回答是
- 再次询问集合 \(\{a_1, a_2\}\)，
- 如果回答是
NO，同上处理，不再赘述。 - 如果回答是
YES，由 \(\operatorname{Observation 2}\) 可知 \(x \neq a_3\)，于是我们的范围缩至了 \({a_1, a_2}\)！依次提交 \(a_1\)、\(a_2\) 作为 \(x\) 即可。
- 如果回答是
注意要特判 \(n = 1\) 哦！
【F. Kazaee】
神题。看上去像一道高级数据结构题，实际上解法很简单。
考虑给每个数赋一个随机值，准确来说是把每一个相同的数随机映射成另一个数，可以发现：
- 若区间内所有数的出现次数都为 \(k\) 的倍数，那么和也必定是 \(k\) 的倍数。
- 若区间内所有数的出现次数不为 \(k\) 的倍数，和也有可能是 \(k\) 的倍数。不过均摊下来，错误率大概只有 \(\frac{1}{k}\) 左右。
使用树状数组维护即可。
思考正确性：\(k\) 等于 \(1\) 时必定都为 YES，所以只需考虑 \(k \geq 2\) 的情况。可以随机映射 \(30\) 次，这样错误率最多只有 \(\frac{q}{2^{30}}\) 左右，可以通过。
具体实现上，如果使用 map 进行映射会被卡常。我的解决方案是写关于 \(x\) 和映射到的数 \(T\) 的一个伪随机式子，可以达到相同的效果。
实测，每次随机时可以取一个数 \(arg\)，对于每个数取 \(T = arg^{a_i}\) 正确率比较高，这样复杂度就是 \(O(kn \log n)\)，其中 \(k = 30\)。
这样做仍然被卡常了！所以可以先对 \(a_i\) 离散化，这样算幂的时候就不用快速幂了，直接预处理即可。复杂度仍然是 \(O(k n \log n)\)，不过这时瓶颈在于树状数组而不是快速幂了，常数很小，跑得飞快。
题外话：CSP 前没补这题，结果 CSP T3 就考到了与这题 几乎完全一致 的解法，亏大了 /ll
Codeforces Round #829 (Div. 1)
【C. Wish I Knew How to Sort】
\(\operatorname{Key Observation}\)：设序列中 \(0\) 的数量为 \(\operatorname{cnt}\)，只有前 \(\operatorname{cnt}\) 位中的 \(1\) 和后 \(n - \operatorname{cnt}\) 位中的 \(0\) 交换 有意义。
然后瞎 dp 就行啦。我们设 \(\operatorname{dp}_i\) 表示形成前 \(\operatorname{cnt}\) 位中有 \(i\) 个 \(0\) 的期望步数，可以推出转移方程：
\[\operatorname{dp}_{i+1} = \operatorname{dp}_i + \frac{n(n-1)}{2(\operatorname{cnt}-i)^2} \]【D. The Beach】
待填坑...
Codeforces Round #832 (Div. 2)
【D. Yet Another Problem】
分类讨论题，和 CSP-S 2022 T2 有的一拼。
- 如果区间内全为 \(0\)，则答案为 \(0\)。
- 如果区间 \(\operatorname{xor}\) 不为 \(0\)，则答案为 \(-1\)。
- 其余情况中，如果区间长度为奇数，则答案为 \(1\)。
- 其余情况中，如果 \(a_l = 0\) 或 \(a_r = 0\)，则答案为 \(1\)。
- 其余情况中，存在 \(i \in [l, r]\)，使得区间 \([l, i]\) 符合题目中的条件，则答案为 \(2\)。
- 其余情况中，答案为 \(-1\)。
如果暴力模拟复杂度是 \(O(nq)\)，瓶颈在第五步，需要优化。
考虑对前缀和（或者叫前缀 \(\operatorname{xor}\) ？）排序，把相同的位置拎出来，预处理对于每个位置 \(i\)，使 \([i, j]\) 满足条件的最小的 \(j\)，就可以达到 \(O(n \log n + q)\) 的优秀复杂度，可以通过。
【E. List Generation】
待填坑...
Codeforces Round #561 (Div. 2)
【D. Cute Sequences】
待填坑...
【E. The LCMs Must be Large】
结论题。
\(\operatorname{Key Observation}\)：答案为 possible 的充要条件任意两天选取的商铺集合都有交集。
必要性证明
假设两个集合 \(A, B\)，没有交集，这时我们可以发现 \(A \subseteq C_uB, B \subseteq C_uA\)，故 \(C_uB\) 集合的 \(\operatorname{lcm}\) 必不小于 \(A\) 集合的 \(\operatorname{lcm}\)，\(B\) 集合的 \(\operatorname{lcm}\) 必不大于 \(C_uA\) 集合的 \(\operatorname{lcm}\)。这时，如果 \(A\) 集合的 \(\operatorname{lcm}\) 大于 \(C_uA\) 集合的 \(\operatorname{lcm}\)，即可推出 \(B\) 集合的 \(\operatorname{lcm}\) 小于 \(C_uB\) 集合的 \(\operatorname{lcm}\)，矛盾，故任意两个集合间必定存在交集。
充分性证明
考虑这样一种构造，假设所有元素初始时全部为 \(1\)，每次把给定的第 \(i\) 个集合内所有数都乘上第 \(i\) 个质数即可。可以发现，当集合两两相交时，这种构造总是对的。