CQOI2020游记

gyh20 · 2020-06-20 19:49:12 · 个人记录

如果您想看大佬 AK 暴虐全场请移步

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:期望得分&实际得分：

期望：

实际：

Day1T1 常数过大被卡成暴力分了？？？？？？？？？？？SHIK！！！！！！！

Day2T3 为什么矩阵树写错了？？？？？？？？？？？SHIK！！！！！！！

好在 Day2T2 三只 \log 没有死的太惨，还有 80。

二次Update：

Day1T1和Day2T3 好像都是WA，不清楚原因。。

Day2T2是数组开小了本来可以A的啊啊啊啊啊啊！！！！！！！SHIK！！！！！！！

人生中的第一次省选，结束了！