NOIP 2023 游记

· · 生活·游记

Day 0

出发日。今天出发的很早，因为下午河北省搞了个颁奖典礼，比较神秘。

这次决定不带电脑了，有效防止我晚上颓到十二点。

上午看了个 fnaf 大电影，之前我没了解过 fnaf 的剧情，看了看感觉挺有意思的。不过可能因为手机看的屏幕很小加上周围很亮，感觉看起来一点也没有恐怖电影的感觉，我看的还挺乐呵的（

下午颁奖典礼，总之就是给各种单位学校老师教练颁发了一堆奖，然后请了几个往届学长来讲经验，总之就是坐了一下午。然后晚上吃了个饭。吃撑了。

晚上睡觉了，收手机收的很早，所以没啥可颓的，晚上把 uu 和 xuany 叫来 吃 橘 子。后续又引来一堆人，反正聊了会就睡觉了。

Day 1

起床，哈哈。早上醒的比叫的早，感觉状态还好。

吃了个饭。好久没吃过宾馆的早餐自助了。

然后就上考场了。哦哦哦哦哦。

开题！旧机房的电脑的虚拟机还是有点卡的，但是感觉问题不大，卡的还是比较有规律的，适应了一会就自我感觉良好了。

T1 第一眼以为是个比较麻烦的贪心，因为第一眼以为是交换任意两个字符串的字符，然后发现是同一个，那就很简单了，直接给字符串排个序就完了。带个 \log，感觉问题不大，懒得去 \log 了也。

8:50 完成了虚拟机配置和 T1，感觉还好，然后看 T2。看起来挺有意思的题？首先肯定模拟一遍确定一些等与不等关系，现在建张图，变成染色问题，然后咋做，找 dfs 树上分类讨论...？

然后突然意识到一共 n 条边，这不基环树吗，那就好讨论多了。基环树上如果环是偶数那么就能黑白染色，否则就得加个 U，但是固定值咋整？想了想意识到一个连通块内最多一个固定值，而且基环树不可能出现固定值，那就好说了，直接判奇环就完了。略微有点难写，我不是很喜欢写基环树，不过写了一会还是写完了。测样例过了。上个厕所先。

大约 10:00 开了 T3。看数据范围看起来不是要带修，应该就是个为了减少读入量的多测，算一下数据范围发现得有 O(n) 做法，那感觉应该就是个贪心了。

先钦定个 f_1<g_1，那如果 f_i \ge f_{i+1} 那选完 f_i 一定也可以选 f_{i+1}，那不就直接削成两个单调序列，那不是直接判一下就行了...？哦不对，我可以先把 f_i 整个比较小的点然后再让 g_i 过去，所以我不一定在最小值的位置。

那感觉应该是个 zig-zag 样子的过程，f 先变小给 g 留位置，然后 g 再变成一个更大的数，f 再变成一个更小的数...这样整应该就可以了。

那考虑找出来这样的东西吧，拿 f 考虑，每次找到下一个比它小的，然后记录一下中间的最大值，这样贪心选一下可能能行？感觉还是不太对，贪心不像是对的。发现如果有两个峰 i \nearrow j \searrow k \nearrow p \searrow q 满足 x_j > x_p ，那么在 k 停留是没啥意义的，你可以直接走到更小的 q 上去。那实际上我们可以只保留出最小值递减，最大值递增的序列，这样得到的一个 zig-zag 形状就是可以贪心的了，因为每次贪心向后选会使对方限制更松，自己限制更紧，这样贪心能选完就有解，选不出来就没解了。那就做完了？哦还有最后一部分，当 f 到全局最小值，g 到全局最大值后，最后相当于还有个峰，判一下哪个先走就行了。

然后就开始写了，写完之后第一个样例过了，大概已经 11:00 了，然后打算给 T4 两个小时时间看能不能冲出来，但是测第二个样例 WA 了一堆，直接恼了。还好是 n,m \le 6 的样例，手模了下发现是最后一部分假了，不一定一边先走到最后然后另一边再走。那完了，我心想应该 T4 是没啥机会做了，还是把 T3 努努力搞出来吧。

想了想感觉会不会是递归下去再跑上面的算法，因为此时结构好像是相同的。但是意识到好像这样我必须先钦定接下来一步先走哪里，此时有两种决策，构了一下发现确实有走一边有解但是走令一边无解的情况，那就没办法直接决策了，感觉寄了。（此时我没看特殊性质，并不知道我前面写的就是特殊性质，所以我以为我完全假了）

上了个厕所冷静了下，意识到现在有第一个数为全局最小值和全局最大值的优秀性质，一直保持同样性质能不能有办法？想了想，发现如果 f 变大之后一定变成一个尽可能小的数最优，因为这样既使指针往右移又能够尽可能减小另一边限制，而我们移动到的下一个点就是剩下的数中的最小值！也就是说此时性质是不变的！然后又想了想怎么判能不能移动，发现只需要满足移动完之后 g 的最小值仍然比 f 大即可，反之同理，因为此时每次操作后 f 增大，g 减小，这样贪心就一定能保证两边都满足条件，那么直接贪心的跑一跑就好了！

然后写了一会，把大样例过掉了，感觉比较开心，此时大概 11:40，寻思着 T4 开始写暴力吧，反正没时间了。

然后看了会 T4。感觉 DP 可做，写了写式子，感觉贡献函数像是有决策单调性的样子。但是推了推好像并不满足。DP 有一个转移的区间限制，时间上看应该一个 \log 可以接受，那么线段树维护一下..？然后突然意识到这个贡献函数极其容易维护，等等这就做完了？

我脑子挺懵的，感觉好像真的就做完了，不是很相信这是 T4 的难度，看了几遍题感觉确实没看错，然后上了个厕所之后就开写了。不过上厕所真的不应该洗手，洗完手手直接冻住了，反正光速敲了棵线段树，然后把 DP 写完了，第一个样例过了，第二个样例没过..？啥玩意，不会我真看错题了吧。又看了几遍题，感觉确实没看错，此时 12:10 左右，感觉干看着也调不出来，写个暴力拍拍。

然后开始写 O(n^2) 暴力，发现我高维前缀和写挂半天，于是决定写个屁，直接 O(n^3) 计算贡献函数，然后赶紧写完暴力，然后跑大样例...输出和我线段树一模一样？？？

有点怀疑人生，又去看了三遍题，确实没看出来有哪里假了，然后就瞪着 DP 想了半天，后来开始手模大样例前面的 DP 值。突然意识到我 DP 没取前缀 \max。哦那没事了，取了个之后暴力就过大样例了。

然后再回去看正解吧，改完之后还是 WA。又看了半天，感觉应该是线段树写错了，去看了眼发现有个地方没 pushUp。改完过了。

此时 12:40。内心有点激动其实，感觉此时把前面题多检查检查或者写个拍啥的保险点比较好，但是想了想还 20 分钟就是写半天真的拍完了拍出错来我也没空调了，于是决定不拍了直接静态查错。

然后等考试结束了。

因为下午三点的车，所以就赶紧出场上了大巴车去火车站了。

晚上回学校后颓一晚上。

Day 2

哈哈，小图灵说我 390。

T3 挂了十分，感觉有概率是我假了，但是我没手机看不了小图灵，并不知道哪挂了，突然想起来信友队还有个自测，然后去那交了一发，也是 90 分，n,m \le 6 的点 WA 了...???

然后写了个拍拍了会，发现拍十几组就拍出来了。发现是答案无解我输出有解，这咋可能的？？？感觉肯定是我写挂了，应该假的概率不高，翻了一会发现原来是我第二部分只判移动后对方合不合法了，没判断当前自己移动合不合法。感觉有点呃呃了，然后改了下就过了。

这下又开始祈祷 ccf 数据强度了。感觉如果多测卡满那 n,m \le 6 不太可能能过了，因为自己拍十几组都能挂一组，试了试 n, m \le 200 大概拍七八十组能掉，n, m \le 2000 貌似纯随机数据挂不了，感觉民间数据应该都是随的。但是这玩意感觉构一构好像挺容易挂的？不太懂，看 ccf 啥水平吧。

看了看部分分，此时才看到特殊性质就是我第一部分，那我起码特殊性质的分能拿到，那就有 45 分了，信仰一波 ccf 数据不是很强吧，毕竟大样例都过了...

等等我本机随 10 组就能挂，大样例 60 组都没死咋做到的？？？合着大样例又精心构造的弱？？？他妈的怎么每次写贪心题都能碰到这种逼情况。

摆了。

接下来您将收看的是：两周半冲五科学考（物理生物化学历史地理，历史地理是因为 THUSC 时间正好与学考冲突，导致我只赶上一科政治）

本文禁止 fzj 评论。

upd. 官方成绩出了，果然 ccf 数据还是很有保障，AK 了。