NOI2021游记
gyh20
·
·
个人记录
Day???
NOIP 裂开，但没有完全裂开，T1 没卡乱拓扑排序，捡了一条命，勉强上了 200。
省选 A 卷，打满了暴力&随机化，Day2 最后一个小时突然想出 D2T2， 464 分，苟进了省队。
之后的一段时间基本都在练题 + 模拟赛，天天被吊起来锤。
Day???
UNR 爆炸，两天得的分和挂的差不多，感觉自己像个伞兵。
Day -1
笔试，错了一道，多选 47 题。
选手在考前不得：
A.查看试题
B.登入系统
C.摸键盘
D.忘了
反正我没选摸键盘（（（
据说是去年原题。
Day 0
台风越来越靠近，上午在寝室里学习土块（天地癞子 + 明牌 + 超级加倍），本来以为考试推迟一天，但说晚上等通知，于是全部人祈祷不考。
晚上通知一出：明天 8:30 过去等着，等通知（（
整个人都不好了（（（
Day 1
9:00 还是正式开考了。
先大致浏览题目，感觉 T1 是简单数据结构，T2 是线性代数题，T3 是神仙图论。
先开 T1，最开始看错题以为是链 xor，仔细想了想发现不对，想了一会不是很会。但是树链剖分是万能的，直接考虑重儿子的变化情况即可做到一个基于 LCT 复杂度分析的一个 nlog^2 做法，想了想没问题就开写了，两个线段树可以维护。
9:40 过了编译，一次过了最小的样例，但大的样例始终差一些，发现有亿些细节没有写，补了很多东西，大概 10:30 过了大样例。
但是后两个大样例都跑了 1s。
很慌，卡了卡常数，11:00 卡进了 0.7s。
再检查时发现，在第四个大样例中，我实际的复杂度应该是 O(n\log n) 的，只不过因为做法问题有 12 次线段树操作，强行变成了 12n\log n。
本来还想卡的，但确实没有时间和精力了。
T2 先跳了，本人数学水平几乎为 0。
T3 感觉是分类讨论，分析了一下题目性质，发现 k=0 应该是缩点后根据 DAG 性质建树就可做了。
调到了 11:50 大概过了第 4 个大样例，但是其中有一些答案为 0 的我输出了东西，心里非常疑惑。
又调了 20 分钟发现输出的是 x-> y 或 y-> x 可达的点数，感觉我是个 sb，马上又拼了个暴力，期望得分 44，此时已经 12:20 了。
掉头看 T2，觉得自己怎么都不可能 0 分，感觉题目定义类似行列式，仔细推一推发现若所有 n 相同就是所有行列式的乘积，仿佛有 75？（由于我并不知道 |A|\times |B|=|AB|，没敢猜结论）。
此时已经 13:00 了，我的得分为 100+75+44（和省选的 Day1 完全一致），感觉应该比较满意了。（当时还没有意识到事情的严重性）
还有 1 小时，感觉 T3 分类讨论还有机会，去尝试做 k=1，先自己写了想到的情况，后来根据大样例调，增加了 114514 种情况，13:40 调过了大样例。
剩下的 20 分钟在检查，居然发现 T1 直接写了一个 T=3，其他没有发现什么不对劲，能过的大样例都过了。
期望 100+75+64=239，实际 100+75+64=239，T1 过了。
赛后问了下情况， crn 两个半小时 AK 了，据他的随机调查， 8 个人中有 7 个 AK。
但的确最后有 30 多个 AK，感觉自己菜的离谱 /kk
Day 2
娱乐。
伞兵嘉年华比较伞兵 /kk
Day 3(NOI Day 2)
想起去年的 Day2，感觉今天的题会比较难，尽量上三位数（（（
开场第一眼看到 384MB，感觉非常亲切（（（
发现三道题题面都比较长，大概浏览了一下题：
T1 感觉是一个乱搞题
T2 感觉是平衡树维护矩阵乘法之类的大数据结构。
T3 感觉不可做，打算就写个暴力。
还是看 T1
先花了大概二十分钟，总结了 5 个性质：
$2.$ $k_i\leq 15$。
$3.$ 强制在线是假的。
$4.$ 我们只需要判断是否存在，不需要计数。
$5.$ 原串是随机的，但询问不是。
大概 $8:30$ 时想出了 [做法](https://www.luogu.com.cn/blog/gyh20/solution-p7738)
花了 $20$ 分钟写完并过了大样例，测了测随机数据发现跑了 $2s$。
卡了卡常，用了上面题解中的优化，随机数据卡到了 $1.5s$，感觉还是很危。
发现 $9:30$ 了，赶紧看 T2.
过了 T1，想着一定要打完剩下两题的暴力。
先尝试推了一下式子，仿佛分别维护出了分子和分母，写了一下 $n^2$ 过了两个小样例，继续跑着第三个样例。
去尝试做 BC 性质的 $35$，发现十分有性质，只有往后插入，由于每一次操作对 $a$ 的影响是常数级别的，也就是想出办法维护出一个 $a_i$ 的贡献，推了一会仿佛推出来了，开始试。
突然发现暴力跑了 $2$ 分钟跑出来了，一看发现 WA 了。
心里害怕极了。。。。
仔细阅读题目，是约分后取模而不是取模后约分。。。
再分析了一下发现一定是互质的，直接输出就过了，又跑了一次过了样例。继续写 $35$ 分，最后 $11:00$ 左右写过了大样例。再看第一个 A 性质，发现 FLIP 和 REVERSE 操作贡献是一定的，可以直接维护正反两种情况再直接用 BC 那一部分就行了，于是改成了 $50$ 分做法，大概才 $11:10$。
马上去看 T3，感觉不可做，打了个暴力走人了，感觉剪剪枝有机会过 $16$，写了写，发现没机会，此时已经到 $12:00$ 了。
继续回去看 T2，但怎么都想不清楚，想了 $30$ 分钟还是没有任何进展，始终想不出 FLIP 和 REVERSE 对答案的影响，最后还是被迫放弃了。
害怕 T3 剪枝剪错，拍了一下，拍了 $50000$ 组居然拍出一个错，马上改了。
期望 $100+50+12=162$。
最后又检查一遍，发现 $99+239+162=500$ ~~非常吉利~~。
下午查分，没有挂，但听说 Au 线 $500+$，非常慌，害怕因为笔试挂掉 /kk
最后 Au 线 $498$，勉强苟住。
### 总结
其实 NOI 场上可怕的不是题有多难，而是你不知道题有多难，你完全不知道一道题的定位是怎么样的，你完全不知道一道题自己有没有想错，也不知道别人到底会不会某一道题，毕竟最后看的是排名，而不是分数，但的确，分析题目难度也是很重要的一个能力。
这一次打的比较苟，看到题都先写的暴力，没敢冲正解，所有题都先打的暴力，但也只打了暴力，但检查的很好。但由于这样，完全没有时间去想正解，除了 D2T3 以外其实都有机会，包括 D2T3 的 $28$ 分，稍微多一点时间就会发现其实还有想法。怎么说呢，冲刺银牌的选手如果采取这种策略应该非常稳，但冲刺金牌的选手还是需要多想正解，或许我也只是一个暴力选手。
祝同学们好运！