NOIP2024 & CACC2024区域赛 游记

· · 生活·游记

前言：这次NOIP考前一直在停课，因为这是我第一次考得好就能参加省选的机会，虽然水了一堆蓝题紫题，但是不看题解和思路的话也就只能场切绿题，模拟赛也从来没场切出过蓝题以上的（当然你谷评级没什么参考价值）。

另外，这是蒟蒻第一篇外出正式比赛游记，编写不易，求个赞 qwq。

Day -5

洛谷梦熊NOIP模拟赛。

开场后先看 T1（我以为这场模拟赛跟近几次CCF的比赛一样 T1 很水），感觉三带一的情况很难处理，好像跟每种牌张数模 4 的余数有关系，就开始玩一些情况，发现如果模 4 的余数为 1 或 3 时就能考虑出三带一，于是有了一个做法，代码才写了不到 20 行就发现假了。。。

然后 T2 感觉是典题，发现最终的收益跟路径上一点向外连出的链有关，设点 u 向外连出的所有链的终点收益减去这条链上总过路费的两倍的最大值为 val_u，路径的起点为 st，终点为 ed，答案即为：

c_{st}+c_{ed}-从st到ed路径上过路费总和+\max_{u \in 从st到ed路径上的一点}val_u 然后继续想 $T1$，想了几个策略发现都是假的，去看 $T3T4$，可能是因为我的心还在 $T1$ 上，所以 $T3T4$ 并没想出一些骗分的方法，于是继续死攻 $T1$，比赛结束前打了个 $30pts$ 的暴力，最后只有 $30+100+0+0=130pts$。只能告诉自己正式比赛的时候一定要注意时间安排。 后来发现 $T2$ 评了绿，发现是我想复杂了。。。 ## Day -4~-3 练一些真题。 ## Day -2 上午练题，下午打了个云斗的模拟赛，本来想打的好一点，结果 $AB$ 题一点不会（我浪费了 $1h$ 多想这两个题，尤其 $A$），只好看后四题（云斗说前两题是奖励题，大概是 $csp-j$ 难度，后四题可以当成 $NOIP$ 模拟赛），果然 $C$ 题是一眼题，排个序就解决了，很有CCF近几次比赛的感觉，$D$ 题数据范围很怪，感觉一定是个 $O(nm)$ 的算法，于是就想 $DP$，发现直接 $DP$ 是 $O(n^2)$ 的，如果在 $n$ 比较大 $m$ 比较小的情况下会被卡爆，于是把值域加进状态，空间上用滚动数组解决，时间上能发现每次转移的值域只有两种取值，所以也可以优化，于是有了一个 $O(nm)$ 的做法，感觉挺对的，但是不太好写。 然后看 $E$，想了一会发现可以用两棵 $Kruskal$ 重构树解决掉，但是也不是很好写。$F$ 题完全不会，而且感觉部分分给的很敷衍。中间跟 kbx 去买了一杯蜜雪，回来决定先写 $D$，然后就一直调到了比赛结束前 $1$ 分钟，最后大样例仍然有一个点一直出问题，没办法，就交上去了，没想到竟然能有 $90$，感觉数据比大样例水。 最后 $0+0+100+90+0+0=190$，后四题一共 $190pts$，还是时间安排上的问题，如果早一点放弃 $D$ 题其实是可以拿到后面的不少分的。 这是我赛前最后一场模拟赛，感觉要废了，我今年的目标是 $100+100+[0,100]+[0,100] \ge 250pts$，但是近几场模拟赛都没上 $200$。 老师安慰我说模拟赛一般都是偏难的。 ## Day -1 上午跟着老师系统地复习了一下NOIP的各种策略和知识点，过了一些例题，下午就是做一些简单题。 ## Day 0 上午看了一些如 $tarjan$，数据结构，$KMP$ 之类的模板，希望不要考字符串和数学，也不要出太难写和调的题。 下午去学校取了承诺书，稍微押了一下题，这是我押的： ![](https://cdn.luogu.com.cn/upload/image_hosting/1hpla1va.png) （这是后来在洛谷犇犇发的，下午就在微信上押了） 然后开摆，B站，phi，推了一个多小时基本没涨，就是 IS at 会打了。 晚上六点多坐快车去太原，七点多就到了，真的挺快的。 晚上吃的烧烤，今年一月来太原的时候吃过的一家，竟然就在酒店旁边。 ## Day 1 早上 $7$ 点多起来的，在酒店点的外卖，包子和皮蛋瘦肉粥，然后去山大考场。 听说这次 windows 系统上的 Dev-c++ 有 $bug$，去试了试，果然，$Ctrl+z$ 后再 $Ctrl+y$ 就会出现乱码，不过我很少用 $Ctrl+y$。 开考之前看了看四道题的大样例，盲猜 $query$ 是树上数据结构或 $DP$，比如树剖一类的。 $8:30$ 发了 $pdf$ 密码，开始看题，想起前几场模拟赛的教训，先把所有题都看了一遍，竟然有两道计数，感觉要寄了。令我有些慌的是 $T1$ 没有特别快想到做法，但当时确实没想到 $T1$ 能有蓝。 读完题以后想了想 $T2$ 和 $T4$，发现 $T4$ 的 $52$ 分好像可以拿，不过后来发现 $A$ 性质好像想不到一个复杂度特别正确的算法，于是从 $52pts$ 直线跌到了 $20pts$。 然后去想 $T1$，感觉是有策略的，然后就想到可以逐位讨论（两个 $01$ 数列下文称为 $A$ 数列和 $B$ 数列）： - 如果 $A$ 数列和 $B$ 数列的这一位都不能交换，那么直接统计答案。 - 如果只有其中一个数列能交换，且这个能交换的“连通块”内剩余的 $0$ 或 $1$ 能匹配上另一个数列的这一位，就贪心的直接匹配。 - 如果两个数列的这一位都能交换，就尽可能把两个数列的这一位匹配成 $0$ 和 $0$ 或 $1$ 和 $1$。 理性证明也不太会，但是 $OI$ 是个感性的学科！经过我的一番感性思考后，感觉这个策略十分的正确，于是开始写代码，难写的地方在于如何统计每一位属于哪个能交换的“连通块”中和每个这样的“连通块”内还剩多少个未被使用的 $0$ 和 $1$，但是也在 $9:30$ 左右完成了，大样例没怎么调就过了，时间复杂度 $\operatorname O(n)$，应该没问题。 然后去想 $T2$ 根据我对题面的理解和数据范围，感觉像是矩阵快速幂优化 $DP$，于是去想一个可行的 $DP$ 方式。先想了一个 $f_{i,0/1}$，表示第 $i$ 位有没有固定的选值的方案数，然后就可以转移了，再然后就发现假了。 想起老师说过要先想一个朴素的 $DP$，于是想到可以设 $f_{i,j}$ 表示考虑到第 $i$ 位，第 $i$ 位选 $j$ 的合法方案数，但是好像会算重。后来我又想了一两种奇葩的 $DP$ 状态，但是每次不到 $10min$ 就发现是假的。这中间我也简单想了想 $T4$，感觉 $20pts$ 还是好拿的，但是再多的就不太好拿了。 上了个厕所，大概 $10:20$，一看时间有点慌了。重新计算了下时间，感觉要给后两题的部分分留 $90min$ 左右的时间，即 $11:30$ 无论如何我都要开始拿后两题的部分分。 重新审视了我列的几个 $DP$ 状态，发现状态的重点好像错了，我前几个状态都主要想记录最后一位填了什么，能满足多少种限制，但是重新读一遍题，会发现题目强调的是有多少种限制使得至少有一种填数的方案可行，状态的设计应该跟限制有更大的关系！ 又画了画，发现如果没有第二种限制，那么所有可能性都一定有可行的方案，所以一个地方是否能自由选择限制跟是否与上一个第二类限制“相连”有关系，如果“不相连”，那么接下来的任意一个第一类限制都能使当前位置的值不等于这个限制二元组的第一个值，这样的话限制是一定能被满足的。设 $f_{i,0/1}$ 表示第 $i$ 位是否与上一个第二类限制“相连”的情况下放置第一类限制的方案数，于是可以得出转移方程： $$ f_{i,0}=f_{i-1,0} \times v^2+f_{i-1, 1} \times (v-1)v $$ $$ f_{i,1}=f_{i-1,1} \times v $$ 如果当前位置有第二类限制，那么令： $$ f_{i,0}=0 $$ $$ f_{i,1}=f_{i-1,0} \times v^2+f_{i-1,1} \times [(v-1)v+1] $$ 然后矩阵快速幂优化一下，分段转移就好了。 先码完了不带矩阵快速幂优化的代码，开始测大样例，有一个点答案是 $0$，我的输出不是 $0$，于是特判掉了第二类限制“重合”的情况，终于是过了，当时的时间是 $11:15$ 左右。我觉得时间应该够用，于是继续根据转移方程推了一个矩阵，开始实现，加上优化后大概是 $11:30$，但是大样例有两个数据范围比较小的点 WA 掉了，又加了个特判，想起之前做 [P6772 [NOI2020] 美食家](https://www.luogu.com.cn/problem/P6772) 时有一个预处理矩阵 $2^i$ 次幂的优化，也加上了，跑了遍大样例，过了，用时大概 $0.1s$，感觉 $100pts$ 应该稳了。 这时大概 $11:40$，我上了个厕所，回来想 $T3$ 的特殊性质，发现菊花图或者链应该还是好做的，菊花图的方案数应该是 $k \times (n-1)!$，然后发现死活过不掉对应的样例，又推了几个看着挺正确的式子，但是都不对。想着 $T4$ 还能拿点分，就果断地把 $T3$ 抛了。然后就忘了还有个链的特殊性质，比赛结束才想起来。开始写 $T4$ 的 $8$ 分暴力以及 $12$ 分特殊性质（我在前三个小时不止一次回想过怎么做 $\operatorname O(1)LCA$，最后也没想起来），写着写着发现可以预处理每个连续区间的 $LCA$，是可以 $\operatorname O(n^2\log n)$ 做到的，然后发现区间越短 $LCA$ 深度越大，于是枚举区间内所有长度为 $k$ 的子区间，总复杂度 $\operatorname O(n^2\log n)$，这样应该能过掉 $20pts$。$B$ 性质相当于每次询问区间 $LCA$，发现这个东西好像有交换律和结合律，于是直接上线段树，因为不会 $\operatorname O(1) LCA$，最终复杂度为 $\operatorname O(n\log^2 n)$，因为没有多测且 $2s$ 时间限制，自认为应该不会出问题。 这时比赛已经快结束了，最后十几分钟去看 $T3$，我前面有一个神奇的状压 $DP$ 做法，可以拿到 $12$ 分，于是果断开写，成功在比赛结束前 $2min$ 过掉小样例，没来得及测大样例，赶紧加上 $\operatorname {freopen}$，用 $NOIhelper.exe$ 生成了校验文件，提了上去。然后我长松一口气，大脑放松下来，不到 $30s$ 就发现 $T3$ 我就没读懂题，写假了。。。 期望得分：$100+100+0+[20,32]=[220,232]pts

比完以后发现大家都觉得难，那就没事啦！竟然 har，zzj，nzr 等一众大佬没切出 T2，感觉很惊奇。这时在提醒下才想起了 T3 还有一个链的特殊性质，虽然只有 4pts，但依旧觉得可惜。但那又怎么样呢？比赛已经结束了，输赢已成定局，也许我从一开始就没读懂 T3，再加上最后没多长时间了，打出一个假的做法也算是必然的。对比那些在这场比赛中失利而退役，永远离开的学长学姐，我已经算很幸运了，至少我才初一，前方的路很长，可以不留下遗憾。

总结：时间安排方面还是有一些问题，还好最后成功切出了 T2，对比之前有了不少的进步。

刚走出山大的校门 zzh 大佬就口胡出了 T4，感觉恍然大悟，%%%%%。

中午（或者说下午？）吃了火锅，感觉挺实惠的，吃撑了。貌似这个成绩在 SX 还是蛮不错的，感觉比 CSP-S 发挥得更好，想起我当初刚学 OI 时输入输出都搞不清楚，到现在能在 NOIP 的赛场上做出前两题，真的算是有很大的进步了。

后来发现洛谷把 T1 评蓝了，T2 评绿了，啊？果然洛谷的评级并没有什么参考价值，我感觉 T1 逐位考虑的思路不算太难想，反倒是 T2 绕了我一会，但是想到洛谷对贪心题的评级普遍虚高，这么评似乎也在预料之内，而且 T2 好像有不用矩阵的做法（反正会写矩阵的情况下还是直接套矩阵爽）。

下午在酒店开摆，打开phi，疯狂推分。

晚上出去吃饭，吃饭时随便水了水 QQ，然后 12pts 就没了。。

这才想起来我过分相信了西西弗评测机的速度，而且没有特殊性质 B 的大样例，可能会挂掉。

于是，232→220。（这个分数好熟悉呀

晚上很晚才睡，还好第二天 CACC 9:30 才开考。

Day 2

早上没吃早饭，拿了一大包零食进考场，很疑惑西西弗的午餐包里有啥。

看题，发现赛制基本是 IOI 和乐多的融合体，好在前十次提交是没有惩罚的，工程题最多能交三次。 本来参加这个比赛就是来 ~~混吃混喝~~ 体验一下的，具体工程题怎么做都不太清楚，想着做做前四题就好了，第五题可以看一下是什么模式。 前两题都是一眼题，但是没有大样例，差评，只有三档部分分，差评，唯一的小样例及其水且走心，差评！ 用了大概 $40min$ 切出了前两题，开始看 $T3$，很明显是数据结构，就开始试着做一下，想了一些方法用线段树维护每个区间内奇数和偶数的数量，写完后小样例轻松过掉，提交后直接 $0pts$。 瞪了一会代码，开始准备对拍。其实我在正式比赛中好几次想用对拍保证正确性，包括昨天的 $T1$，但是怕时间不够一直没尝试过。而这次比赛有整整 $8h$，可以好好拍一拍了。于是我写了一份造数据程序和一份暴力代码，提交了一下，发现正确性是没问题的，就开始拍了。 这时西西弗的午餐包来了，一人一包，~~想多吃也没有了~~，竟然是麦当劳！有一个汉堡和一个芋头派，汉堡虽然不大但也够吃了（甚至在麦当劳的一系列汉堡里算大的）。芋头派外面很酥脆，还有股焦香，里面的馅也挺甜的，汉堡也很不错，里面有一片牛肉，感觉很鲜很香，是那种属于牛肉特有的香。感觉西西弗还是挺大气的。 吃完饭，程序也拍出来了一组错误数据，开始调，果然，标记下传的部分出了问题，于是反复地交换顺序，拆成两个函数······最后也没有完全解决问题，打了个 $30pts$ 的 $\operatorname O(nq)$ 暴力，结果过掉了 $70pts$，突然就对昨天的 $T4$ 有了信心。 $T4$ 像是打磨你或者酚类逃抡，感觉很复杂，一点不会，看着CCF给的生硬的部分分，甚至一个特殊性质没有，我选择了直接输出 $0$，后来发现，直接输出 $0$ 或者 $2$ 都能有 $5pts$。 这时才用了 $3$ 个多小时，开始钻研从来没见过的工程题，读了两遍题，大概懂了要怎么提交以及要干啥，想到一个优先队列的做法但是无法准确的确定两个决策那个更优，就直接最裸地把每次询问添加到最靠后的位置。 本来准备码代码了，结果发现CCF下发的 $main.cpp$ CE了！关键是考场上的 Dev-c++ 不知道设置了什么，会报错，但不会告诉你在哪一行，于是，我做这道题的第一步变成了调试CCF下发的 $main.cpp$。 调了 $20min$ 左右，发现 Dev-c++ 底部其实是会显示在哪一行哪一列 CE 的，只是没有显示出来，也算是学到了。开始码代码，很好写，写完后用 $main.cpp$ 估分，大概 $63$，提交上去果然 $60$ 多，开始想优化（满分 $200$）。 后来用了一个很神奇的乱搞方法，就是每次枚举刚用完的后 $1000$ 个物理机，然后选择其中一个放进去，再把每次删除操作对应的物理机加到一个 $vector$ 里，每次枚举后加进去的 $1000$ 个机子并判断（真的好神奇）。瞎改了一会代码后估分就到了 $126$ 分左右，自信提交，我记得好像是获得了 $127.11$ 分。 后面也不会优化了，$T3$ 也调不出来了，再加上“玩的目的达成了”，就提前出来了，最后 $100+100+70+5+127.11=402.11$，不知道能不能嫖个奖。