NOIP 2021 白给爆零记

· · 个人记录

Day-1:

周四的时候，我模拟赛又爆零了。于是到了晚上，我和 @Zjl37 打算分析去年命题规律，通过排除法来判断今年可能会考什么，但不知道为什么后来变成了查看大纲，检查自己不会的知识点。通过这个检查，我发现自己忘记了很多数学的东西，决定复习 tarjan，Euler路等。

Day0:

要出发了！但是机房里充满了颓废的气息。几乎整个机房都在打 G 题。我不为所动地进行了十来盘观战，同时断断续续地打完了欧拉路，点双，边双的板子。这是要爆零的节奏啊！

大巴不让人头晕。

为了防止和 Joury 同一个房间，我马上寻找了 @wolfind，还好不是一个房间，否则可能将半夜被吵醒。

Day1:

5:10 就醒了。

6:30 到楼下，没看见 scp，胡乱找了家葱油饼店。吃完后 scp 找完正经的两家早餐店归来，大家都都吃上了热腾腾的早饭，除了我和 Zjl37。

开题了！！！

T1 筛法显然，但我码力过逊，调了 1.5 h 才过了大样例。有点小慌。

T2 看着难度，不想打暴力，观摩 T3。

发现 T3 的操作等价于交换差分数组 d，且差分数组先减后增优。

还有 3h，不慌，思考 T3 正解。

怒推式子 1h，除了 2^n 暴力没有想法，危！

若打暴力，至少 0.5h，很可能无法写出 T2，成败在此一举，转战 T2！

没有思路！！！

马上将枚举 a_i 换成枚举 c_i，c_i=\sum_{j=1}^n[a_j=i]。

化式子为：

n!\sum_{c}\prod_{i=0}^{...}\dfrac{v_i^{c_i}}{c_i!}

想了 1h，才想出 dp 方程：

则转移时 $$g(i+1,j+z,x+[y+z\&1],(y+z)/2)\ +=\ g(i,j,x,y)$$ 时间复杂度 $O(nm^4)$，常数 $\dfrac1 8$，可过。 打完后时间只剩 10min，无力回天。