NOIP2025游记

jch123 · 2025-11-29 20:27:01 · 生活·游记

Day -4~-1

校内停课复习NOIP，在刷CF2300的DP标签，效率惊人，一下午AK板子赛（虽然一点用没有）。

Day 0

比较松弛，睡了会觉，随便找了几道组合数和概率的CF做了做（非常重要，为后文埋下了伏笔），本月通过91道。写了会whk，感觉全面退化了（数学被zhy单杀两道三角函数），晚上和同学玩mk48.io，太卡了，没上过5级，红温了，于是睡觉。新买了一个乒乓球拍，但是怎么没有弹力（还没地板好），差评。

Day 1

早上好困。到rdfz被dzd肘醒，rdf的厕所真好，有热水能唤醒冻僵的手。\ 8点半开题，密码好像是NOIPdream之类的，希望能如我所愿。先看T1，好像没什么难度，就直接开写，排序后枚举第一个选到哪里，然后贪心选性价比最高的，7分钟过掉。\ 然后T2，看这一坨题面应该没那么难，但是看到模数那一刻心就凉了（计数是我从来不会的），跳过去看T3，T4，都看起来很可做，一个是MEX，一个是数据结构，但T3的树高意义不明，T4暴力维护分不多，所以还是去直面T2（英明的决定）。玩了一下样例有些眉目，应该是形如121这样的结构，由于直接写风险很大先打暴力，但是过不了大样例，感觉完蛋了，指数暴力都不会，认真看了看改出来，此时是9点20，于是继续想，还是不会，以为是神秘DP，9点半时突然想到昨天写的CF660E，我可以枚举那个1和2，然后前面的可以解方程因为和为 m-1，后面能二分！！！感觉又行了，上了个厕所整理了一下感觉很对，开码！还是比较好写的，10点就写完了，一遍过第一个小样例，但是第二个就挂了，当时感觉天都塌了，只能一个一个玩（CCF第二个 n=5 好评），玩了一会还是不会，隐隐约约感觉是这个1，2直接好像有更多的方案数，但是我推不出来。\ 然后我悟了，中间可以有 2，但是不合法要和第一个算，j+1 和 j 应该有一点关系，然后继续改，死活推不出来，已经11点了，难道我的OI生涯要止步于此吗？不，我还可以拼暴力，直接再上一层循环枚举中间选几个，但依旧不对，哦，是后面二分的锅，贡献是 2^{g-1} 而不是 g，然后过了第二个！第三个，第四个，第五个，第六个，第七个！但是后面依旧不对，仔细观察一下差了 1，应该不是取模问题，估计是某个边界没写，把大样例输出了一下，但还是毫无头绪，已经11点20了，我当时定了11点40前过不了就去打后面的暴力，怎么办，哦，是有重复的啊，没判等，重构了一下就过了，一下过了前十个，可以拿到可观的80，但是有点慢，把一些continue换成break，再用本地的O2编译，0.5秒过了第九个和第十个，看这个式子应该能优化，但是已经11点50了，去写后面的吧。\ T3好像我做过（CF1292C）！但原题是边权且是排列，大胆猜测这个也是排列，但是暴力告诉我不对，毫无头绪。去写T4，我如果想拿到省一要至少凑出40分的暴力，那么T4的 O(q(r-l)^2) 势在必得，发现可以枚举出所有的区间然后使用单调队列维护，但是两个信息怎么办（其实这能拿到很多分）？完了不会，突然想到可以用set维护，写了一半发现直接线段树，改了一下输出格式直接过掉，但是怎么2.2秒，完了，不对，区间 \max 的范围是一段后缀，可以写一个倒过来的树状数组（一道二维偏序的2300题解告诉我的），太棒了，1.1秒，相信CCF神机。还有30分钟，T3势在必得，发现选的范围不会超过 n，那么可以状压，然后类似树形背包合并！10分钟打完怎么不对，哦，原来这个子树可以选超过这个子树大小的值，扩大一下范围就对了，但是好像没有时间复杂度保证？，试图提前预处理加速（但是更慢了），但CCF怎么没有 n=18 只有 n=13，算了就这了，应该有希望。\ 然后检查，感觉T2的式子有些眉目，但假了，写了几个特判加速，然后检查了一下文件读写。\ 估分：100+80+[16,24]+25=[221,229]\ 出了考场，大家考的都一般，ljh切了T2但是没时间暴力，心情好了一点，去和同学们吃巴奴，洛谷发难度黄黑黑黑！应该有救，买了个冰激凌奖励自己，然后去必胜客玩三国杀，军九被ltx的郭皇后无限南蛮上课，军五被数学家爵制变成无能的主公，但还是蛮开心的，晚上吃了披萨。

后记

CF2300的DP太有用了，学一些知识点该进军2600。收到消息12月要月考，下周数学物理周测，该补whk了，努力吧！\ 回家昨天不弹的乒乓球拍开始有弹力了，随着拍头的一上一下，球越飞越高，飞向遥远的梦想……\ 12.3出分，100+92+8+25=225。T2二分改成指针有8分，T3的MEX少处理了一次少8分，T4没拼暴力少15分，总计31分，北京rk52，省选如何翻盘？\