NOIP 2022 被T2创死记

· · 个人记录

Day0

想和妹子贴贴，但是没有妹子捏。

只能打戴森球计划捏。

Day1

同学都在背模板只有我在摆烂！

进考场发现右边是hzy，再右边是myh，对面是skc，萌新只能瑟瑟发抖。

左边的老哥好像知道我但是我不认识他捏。

8:30开始比赛。pdf还要密码才能打开有点厉害。solo@2022是什么意思捏？

花了大概十分钟看完了四道题。

T1 是要种 CCF？想了想直接枚举 C 和 F 的顶点随便统计一下贡献就可以了。秒了。。

然后看了 T2。喵喵喵？没有看数据范围以为用两个栈就能解决。我认为我会了，然后就去开了下一题。

T3 这个题看了就会做了。感觉和 T1 差不多难度。就先边双缩点，然后相当于树上选若干个点，如果一条边两边都有选的点权值是 \frac 12 否则是 1，然后直接在树上dp就行了。6。

然后看了 T4，数据结构啊。看完了题意没有想。

然后花了 15 分钟打完了模板和 T1。现在是 8:55。我感觉很稳。

然后开了 T2，发现刚刚的做法假了？没有思路啊。看了数据范围，发现 k=2n-2 或 k=2n-1。然后发现 k=2n-2 只需要一直空着一个栈就可以了。很感动。

然后我就一直试图扩展到 k=2n-1。不太会，完全没有思路。不会吧我不会连 T2 都过不去吧？很害怕。试图去想 n=2,k=3 的做法。

然后我发现一个序列如果 a_i 和 a_{i+1} 相同，那么可以直接删去这两个，如果 a_i 和 a_{i+2} 相同，也可以直接删去这两个。然后最后的序列一定是 123123123123 的形式。我感觉这个结论很厉害。（虽然最后挂了）

然后我开始考虑怎么做 k=2n-1 的情况。但是不太会扩展，无法保证最后一个栈一定是空的，然后就跑不了。

已经 10:30 了捏。我还是没啥思路。于是只好放弃 T2 去开T3。

开始慌了，怕我 T3 也假了。但是冷静了一下发现并没有假。于是直接默了一个边双，然后随便写了一个 dp 就过大数据了。很厉害。大概是 11:00。去看T4。

观察了一下数据范围发现有一个数据随机的部分分。有什么用捏？

我不太懂，但是我先写了一个 \mathcal O(n^2) 的垃圾算法。

然后想了一下 Q 很小的情况，我思考了一下一组询问怎么做。发现只要 i 从 n 枚举到 1，用单调栈维护最大值，就能知道 [i,j] 的权值是多少了。

然后感觉可以扩展到多组询问，还是单调栈，还要枚举 i，然后在每个 j 维护所有 [x,j](x\ge i) 的权值和，然后就相当于问 i=l 时 j\ge r 的 j 当前的值的和。

然后我发现这个相当于一开始时 a\times b，然后会变成 a'\times b，然后就是乘 \frac{a'}a。然后维护和就是在加一个 c。一种时 a\times b\to a'\times b，一种时 c\to c+a\times b。直接拿矩阵维护。很靠谱。对了，模数是多少捏？2^{64} 啊，那没事了，寄了。

但是这个数据随机更改的 a,b 不会太多，所以可以直接暴力维护！写了一手。

然后我冷静了一下，发现如果只是赋值的话，不需要求逆。可以对每一段维护 \sum a,\sum b,\sum ab,\sum c，然后打 tag，必定可以写成矩阵乘法的形式所以肯定是可以做的。感觉很稳。此时已经 11:30，我权衡了一下，发现 T2 没啥希望，于是直接开始冲这个做法。

感觉矩阵常数有点大于是我还是写的传统tag。花了大概 40 分钟写完，差不多是 12:10，但是样例二就过不去。我以为是我tag合并写挂了了，一直在观察tag合并，结果最后发现是线段树写挂了，标记下传的时候只更新了值没有合并tag。挺小丑的。

已经 12:35 了。但是我文件夹完全没建，freopen 一个也没打。

冷静了一下，发现 T2 还有一个 m\le 14 的暴力没有打。赶紧冲了一个暴力出来。花了 10 分钟，然后文件夹和文件操作花了大概 5 分钟。

还剩下 10 分钟。我尝试用 Atbiter 评了一下。这个【】建比赛好麻烦！！！但是 T3 MLE了？？？还有 1 分钟，心跳骤停。意识到我开了一堆 10^6 的数组，于是把几个换成了 5\times 10^5。感觉没啥大问题。

出了考场，尝试联系pigstd但是他没有理我。但是我看到了wyh并且他会T2。非常惊讶。感觉我比去年菜多了。

晚上在infoj上评了一下发现 T2 挂成了 20，其他都没有挂。

和pigstd聊天知道他没调出来T2心情很糟糕。于是我又去复习了一下 论OIer谈恋爱的必要性。

但是他有妹子可以聊天但是我没有捏。

我被T2创死了。我也很自闭。我也想要妹子。

什么时候能有妹子捏？？