CF 瞎写记录

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\)，具体步骤如下：

1. 询问集合 \(\{a_1, a_2\}\)，
   • 如果回答是 NO，那么我们就认为 \(x = a_3\)，提交一次答案，
     • 如果猜中了，游戏结束。
     • 如果猜错了，我们的范围就缩小至 \(\{a_1, a_2\}\) 中。同时，我们知道上一次的回答在 Joking，下一次询问就必定会说真话！接下来就很容易了，询问集合 \(\{a_1\}\) 便能知道 \(x\)，提交答案，游戏结束。
   • 如果回答是 YES，请继续向下看，
2. 再次询问集合 \(\{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\) 的期望步数，可以推出转移方程：

提交记录

【D. The Beach】

待填坑…

Codeforces Round #832 (Div. 2)

比赛传送门

【D. Yet Another Problem】

分类讨论题，和 CSP-S 2022 T2 有的一拼。

1. 如果区间内全为 \(0\)，则答案为 \(0\)。
2. 如果区间 \(\operatorname{xor}\) 不为 \(0\)，则答案为 \(-1\)。
3. 其余情况中，如果区间长度为奇数，则答案为 \(1\)。
4. 其余情况中，如果 \(a_l = 0\) 或 \(a_r = 0\)，则答案为 \(1\)。
5. 其余情况中，存在 \(i \in [l, r]\)，使得区间 \([l, i]\) 符合题目中的条件，则答案为 \(2\)。
6. 其余情况中，答案为 \(-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 的充要条件任意两天选取的商铺集合都有交集。

提交记录

原文地址：http://www.cnblogs.com/SparkleZH-Blog/p/16858733.html