NOIP2022 游记

· · 个人记录

Day -7

中午 1 点出发去平邑，网课直接翘掉，高兴到爆炸。下午 4 点到的酒店，和 xzy 一个房间（%%%xzy）。

到酒店后没啥事，把今年 CSP T2 写过了，晚上写了写去年 NOIP T2，发现除了暴力毫无思路。

晚上 10 点就睡了，明天有模拟赛，但和 xzy 聊到了 12 点多······

有种出狱的感觉。

Day -6

NOIP 模拟赛 1。

开 T2，是个基于冒泡排序的计数 DP，想出来了 $a$ 序列是普通排列的做法，$50$ 分到手。圆排列的情况很棘手，完全不知道怎么处理。 T3 正解感觉是快速求割边之类的东西，但是不会，直接写了一发暴搜走人。 比赛快结束时发现 T2 排列数如果暴力算的话会超时！赶紧想怎么优化，发现要先用数组预处理。结果写挂了，只好交原来代码了。 期望得分 $100 + 45 + 30 + 0 = 175$，实际得分 $20 + 45 + 0 + 0 = 65$，挂分挂惨了。T1 做法假了，T3 暴搜写挂，就守住了一个 T2（悲。 理所当然地颓了一下午。xzy 给我演示了一个很好玩的飞车游戏，有些上瘾（但玩得很拉。zz 戏称我玩的是 QQ 碰碰车。 晚上听讲评，T3 正解离谱出天际。随后把昨晚的暴力打了。 ## Day -5 NOIP 模拟赛 2。 又是 $10:00$ 写完了 T1。T1 正解是线段树，但蒟蒻码力不够，写了发暴力。感觉比昨天更加艰难，思路很混乱。 开 T2。又是计数 DP。推了个有模有样的方程，但是假了。顷刻不想打了，12 点就和 xzy 一块吃饭了。 吃饭时听歌，《天气の子》。很好听，感觉心灵受到了洗涤。 结果模拟赛只有 $8$ 分，T1 爆 0。xzy $90$+，%%% 下午休息了会儿，之后修了修昨天写挂的暴力，发现自己脑抽得有一批。 晚上看电影《星际穿越》，没看完，但好评。 ## Day -4 ~ -3 被迫听 whk 网课，没啥好写的。值得一提的是，晚上切了道分块题，快速求 $\sum_{i = 1}^n k\mod i$。 飞车玩儿得有点水平了······ ## Day -2 NOIP 模拟赛 3。 用的 NOIP 2020 原题。T1 显然的拓扑排序，但我到了 $10:30$ 才写完，调错调干呕了，心态有些爆炸。 剩下时间就光码 T2 暴力了。码码码码到最后发现样例不过的原因是题看错了，改了改暴力就过了。总得分勉强 $60 + 48 = 108$，2 = 了。。 终于晴天了，浑身舒爽。 晚上把昨天分块题写过了。随后看了场世界杯球赛，德国对日本，比分 1 ：2，离谱。 ## Day -1 上午和 xzy vp CF。F 题 Conditional Mix，极其恶心的计数 DP，死磕了俩小时没想出来，翻开题解发现那人设的状态巨离谱。 下午模板大闯关，15 个模板，打了一下午一晚上，发现基础算法知识遗忘得挺快。又看了场球赛，瑞士对喀麦隆，0 : 0。 ## Day 0 一觉醒来发现明天就 NOIP 了，有些小慌。 早上吃完饭转移酒店，换了个据说是五星级的酒店，条件超好，还有个大阳台。 上午接着打模板。一直打到晚上吃饭前才打完。感觉再次学到了不少东西。 晚饭红烧肉极其好吃，好评。吃了一半去做核酸，差评。晚上没再碰 OI，和 xzy 打了两局红警，然后就睡觉了。 晚上有蚊子，没大睡好。 ## Day 1 NOIP 日。$6:00$ 就起了，早饭不是太好。 大约 $7:40$ 到了平邑一中。在第 $5$ 考场，结果一进场就得知自己电脑死机，换了个座位，rp--。 $8:00$ ~ $8:30$ 试机。打了棵线段树，自己造了造样例，一遍就过了，状态还不错。 $8:30$ 开题。看 T1。题面挺吓人，然后发现是签到题，$45\min$ 写完。时间复杂度 $O(n^3)$，因为我写了`break`，就没再想进一步优化。一次性过了所有大样例，最后一个是 114 514，差点笑出来。 此时是 $9:15$。直接开 T2，感觉自己很勇。从头到尾读了一遍题目，好像没啥思路，感觉很不可做，准备写一发暴搜走人。 这时我看见了 $k = 2n - 2$ 和 $k = 2n - 1$ 那两个条件。好像鸽巢原理和均摊做有点性质。如果均摊，所有栈中加不到两层就一定会出现重复的元素。对于一个新元素，如果有空栈就可以直接与其他元素配对；如果没有空栈，一定会存在一个元素数为 1 的栈，那么就将这个栈中原有的元素挪走，重新定义到另一个栈中，那么又会形成一个空栈，就可以配对了。随后赶紧写代码，在 $10:50$ 时终于写完了。 然后战术上厕所。这时我感觉我赢了，但很快发现 T2 做法好像不太对，开始构造数据疯狂调代码。改了亿万个地方，又糊上了个优先队列，一直干到了 $12:00$。但感觉还是不对，小样例却都过了。 也没有多少时间考虑了，赶紧开 T3，计数 DP，没时间想正解了。数据范围中有 $10$ 分链的部分分，果断开始打，感觉是个简单递推，后来发现不是。我设的 $f_{i,1/0}$ 为链上第 $i$ 个点是否驻扎军营的方案数，但不好转移，胡乱写了一发交上去了。 T4 直接摆烂，最后延时 $10\min$ 检查了下 T2 的输出结果，和 T1 的多测，就结束了。 下了考场 xzy 说他 T1 炸了，但大样例都过了，顿时感觉很慌。他说 T3 的骗链部分是组合数学找规律，不理解。zz 和他 T4 均骗了 $8$ 分。 坐车回酒店时一直在担心自己的 T1。花这么时间在 T2 上确实挺亏，但应该能冲过几组测试点。T3，T4 就不指望了。 中午草草吃了个饭，就赶车回家。走之前我们三个还拍了张合照（doge 结果下高速的时候给堵上了，整整堵了三个小时。在车上没啥事干，睡了会儿觉，看了会 xzy 玩音游，又水了会儿洛谷。好像今年挂在 T1 上的人挺多，然后特别担心，疯狂回想自己是不是犯了一些脑残错误。 晚上快 $8$ 点才到的家，好消息是明天放假。 ## Day 2 搞到了选手代码，在洛谷上自测了下，$80 + 20 + 0 + 0 = 100$。T1 $O(n^3)$ 超时，卡掉了 $20$ pts。后来仔细想了想只需要再维护一个前缀和的前缀和就行了，复杂度 $O(n^2)$，血亏。T2 由于各种原因只过了 $20$ pts 的小测试点，其余超时。由于算法假掉了，不是太亏。 确实输在 T2 上了，导致 T3、T4 一分没拿到。做题策略急需调整啊啊啊······ ## Day ？（12.5） 出分日。官方数据 $100 + 20 + 0 + 0 = 120$。T1 因为常数小给过了（乐。 好像能混个 SD 1=？RP 是加到位了的。 ## Day ？？ 1= 了。 今年第一年参加 NOIP，水平还是太菜了，但结果是好的。 以后的路还很长。明年 NOIP 我们再见！