CQOI2020游记

如果您想看大佬 AK 暴虐全场请[移步](https://www.luogu.com.cn/blog/feecle6418/xing-xuan-lian-kao-2020-you-ji) ## Day -1 & Day 0 打了很多板子，复习了很多例题，但没有复习多项式（反正考了也不会）。由于 CSP 丑陋的分数，我不可能进省队。这也好，我的压力没有那么大，但我还是想尽力考一次。 ~~然而我整整有半个下午在和 Fee_cle6418 比赛卡常。~~ ## Day 1 早上 $7:30$ 到了考场， $8:10$ 进考场，本来想打个后缀数组热身的结果看到有 Lemon 一直去研究怎么用（以前没用过，但的确很好用）。大概 $8:32$ 左右，还没有人说话，我很迷茫，结果发现密码已经发下来了。 发下来，随便看了看题，感觉 T3 最可做（，T2 看到多项式三个字直接放弃。 还是先看 T1。 先一眼看了个 $Qx$ 的做法，即每次插入树状数组然后枚举值，我发现这个东西很好优化，因为这个函数是一个中间高两边低的，于是敲了个三分。 结果发现，样例都过不了，因为它是一个阶梯状的，所以三分会有错，于是想了半个小时怎么做（简直就是 sb），然后想到的解决方案是三分第几个冰（更 sb）。 然后更 sb 的事情：我看到 $x\leq 2\times 10^9$ 我没有想到离散化反而想的是动态开点线段树。 中途有很多值算了很多遍，但我不想改了，想等最后再改。 大概两个小时左右，过了两个样例，然后做了一个 $Q\leq 2\times 10^5$ 的样例，我一直认为这个能随便过。 结果：15s ？？？ 常数真的大，虽然是两个 log，但一个是动态开点的 log，一个是三分的 log。 卡了一会常，还要跑 7s，Lemon 上跑 3.5s。 然后我把求和的线段树换成了树状数组，但求 k 大还是用的线段树（sb），结果本地 5s Lemon 2s？？？ 树状数组好。 大概得了 $60$ 就走人了（菜），此时已经 $11:30$ 了。 开始看 T2。 一眼 $30$，先打了一个 $20$ 的暴力，觉得 $30$ 有点丢人，去想 $m=0$ 的情况，~~经过打表~~得出是 $a_0\times (x+1)^n$。觉得很不错。 其他情况我直接输出了 $0$。（万一对了呢） 此时还有 1h。 看 T3: 最大子集不存在异或为 $0$？不是裸的线性基吗？ 然后这个调整是什么鬼玩意？ 突然想了一个建图方法：依次看每个数能否代替 A 或 B 中的一个数，从小的向大的连边。感觉这样是对的，复杂度也是对的，但也只是感觉。 之后缩环变成了一个 DAG，然后想怎么拓扑 DP，写了一个 $Nv$ 的调到 $12:50$，结果小样例输出了 $7$。 我发现：这样是错的，算重了。 怎么办呢？爆零了。 还是太菜了。 预计得分 $60+40+0=100$ 百分之百 $60$ 会炸掉。 赛后 zzw4257 说 T3 如果是这样可以网络流，具体不清楚。 ## Day 2 Day 1 死得如此惨烈，Day 2 没有报什么希望。 开场觉得 T1 可能是状压，但完全不知道压什么，放弃。 T2 仿佛没思路。跳过。 ~~于是 T3 又成了最可做的一道~~。 生成树之和？？从来没听说过，只听说过生成树个数。 仿佛有 $30$ 是爆搜，$50$ 是矩阵树。 矩阵树是怎么写的来着？？ 试了几遍，全输出 $0$，最后隔了好久才看出来我写的是一个 $n\times (n+1)$ 的高斯消元的矩阵。。。。 试了几个，仿佛都是对的。 期望得分：$50$。 回去看 T1： 这**是什么东西？？？ 这个部分分是什么鬼？？？？ 先打了个 $m!\times m^2$ 的暴力。 突然想起了一个东西！模拟退火！ 迅速的打了一个，然而大样例始终过不去，一直输出五千万零几，自己随便造了几个小样例，跑了很多次都不一样。搞了一个多小时贪心策略还是没有进展。直接交了。 万一我 RP 不错呢（想 peach）。 期望得分：$30$。 然后看到了最开始感觉最不可做的 T2。 主要难在进位。 记得之前自己出过一道区间加区间异或和的数据结构，当时用的桶+分块做到 $O(\sqrt n\log w_i w_i)$，然而连部分分都没有。 但我突然觉得桶这个思想很妙，可以处理进位问题。 然后这个距离其实是一个差分，可以用下减上然后减去当前节点的 dep 来做，然后处理某一位有值的情况即可。这个桶还可以用 DSU 的思想！ 妙啊！！ 打完之后调了一会过了小样例，之后马上又过了大样例。 难道我要 A 题了吗？？？ 结果造了一个随机的满的样例，跑了 $8s$。 仔细分析一下，复杂度是 $n\times$ 按位 $\times$ DSU $\times$ 树状数组前缀和 $= n\log^3 n$。 至于 $n=500000$ emmmmm 看来还是 too young too simple。 想用 Lemon 测一下链发现不会用 Lemon 开栈。。。但本地还是跑得出来，因为链是严格 $n \log^2 n$ 的且树状数组常数小。 本地 $1.7s$ 就跑出来了，应该问题不大。 测了一下 $v_i=1$ 的，仿佛也能过？ 至于随机数据，就跑了一个 $\sum dep$ 的暴力。 希望不要被卡。 期望得分：$60$（十分依赖数据的形态，不会被纯随机卡，但会被奇怪的数据卡） 希望我 RP 爆发，考试之前地上的两毛钱我都没贪小便宜捡，给我过了吧。 Day2:$30+60+50=140$ 总期望： $100+140=240$ 总结：@Fee_cle6418 比我小还比我强，Day2 T2 直接用之前做过的某一次 AT 的 C 题的 Trie 树方法 $O(n \log n)$ AC，Orz！！！不愧是我的女神。 至于我，还是太菜了，明年努力！ Update:期望得分&实际得分： 期望： $60+40+0+30+60+50=240$ 实际： $30+40+0+30+80+30=210$ Day1T1 常数过大被卡成暴力分了？？？？？？？？？？？SHIK！！！！！！！ Day2T3 为什么矩阵树写错了？？？？？？？？？？？SHIK！！！！！！！ 好在 Day2T2 三只 $\log$ 没有死的太惨，还有 $80$。 二次Update： Day1T1和Day2T3 好像都是WA，不清楚原因。。 Day2T2是数组开小了本来可以A的啊啊啊啊啊啊！！！！！！！SHIK！！！！！！！ 人生中的第一次省选，结束了！