Codeforces Global Round 31 (Div. 1 + Div. 2) (#2180) 全解

Codeforces Global Round 31 (Div. 1 + Div. 2) (#2180) 全解

今天早上 VP 这场比赛，过了 ABCE。
A. Carnival Wheel

由于数据范围是 \(5000\)，我们暴力模拟即可。
开一个值域大小的标记数组，如果找到了环就直接退出，记录途中最大值即可。
Submission #356326001 - Codeforces。
B. Ashmal

容易发现如果当前得到了字符串 \(S\)，我们现在要加入字符串 \(A\)，那么无论 \(A\) 接在前面还是后面，都要求 \(S\) 最小即可。
于是我们按顺序插入 \(A\)，在两种方案里选字典序最小的即可。由于数据范围较小，可以用 std::string 快速实现。
Submission #356326086 - Codeforces
C. XOR-factorization

首先 \(K\) 为奇数时，就全部填 \(n\)。
考虑 \(K\) 为偶数时怎么做，一种天真的想法如下：

• 首先填 \(K-2\) 个 \(n\)，接下来只需考虑两个数 \(x,y\)，我们按位考虑。从高位到低位，如果 \(n\) 这一位为 \(1\)，那么可以让 \(x\) 赋 \(1\)，\(y\) 赋 \(0\)。而如果 \(n\) 这一位为 \(0\)，为了使和尽可能大，我们希望 \(x,y\) 都填 \(1\)，但前提是不超过 \(n\)。于是如果先后遇到两个 \(1\)，第一次就让 \(x\) 填 \(1\)，\(y\) 填 \(0\)，而第二次就让 \(x\) 填 \(0\)，\(y\) 填 \(1\)，这样之后 \(x,y\) 都必小于 \(n\) 了。
  

然而上面的做法会 WA。考虑为什么，因为前面的那 \(K-2\) 个数之中也有可能出现对于 \(n\) 为 \(0\) 的位，两个数填 \(1\)。
考虑扩展上面的做法，维护一个计数器 \(cnt\)，表示当前前 \(cnt\) 个数都必小于 \(n\)。遇到一个 \(1\)，我们就尝试让第 \(cnt+1\) 个数赋为 \(0\)，其他都赋为 \(1\)。而遇到 \(0\) 时，我们就取出前 \(cnt-(cnt\bmod 2)\)  个数填 \(1\)。
这样就通过了。复杂度 \(O(K+\log V)\)。
Submission #356327292 - Codeforces
D. Insolvable Disks

赛时没过，原因是不敢写贪心，以为不对。
考虑每次贪心选择一个尽量长的前缀，设 \(d_i=a_{i+1}-a_i\)，加入 \(r_1=x\)，则有 \(r_2=d_1-x\)，\(r3=d_2-d_1+x\)，\(r_4=d_3-d_2+d_1-x\dots\)。

那么前缀 \(i\) 合法的充要就是 \(\forall 1\le j\le i,0

很好很强大  我过来先占个楼 待编辑

感谢发布原创作品，程序园因你更精彩

分享、互助 让互联网精神温暖你我

不错，里面软件多更新就更好了

懂技术并乐意极积无私分享的人越来越少。珍惜

鼓励转贴优秀软件安全工具和文档！

分享、互助 让互联网精神温暖你我

谢谢分享，辛苦了

感谢，下载保存了

新版吗？好像是停更了吧。

东西不错很实用谢谢分享

谢谢分享，试用一下

收藏一下   不知道什么时候能用到

东西不错很实用谢谢分享

很好很强大  我过来先占个楼 待编辑

喜欢鼓捣这些软件，现在用得少，谢谢分享！

热心回复！

东西不错很实用谢谢分享

谢谢分享，试用一下