nnn233 の 2024 CSP 游记

week -3

初赛也是不出意外的过了，从放完国庆开始就全天停课刷题，停课的第一周把历年真题全刷了一遍，学了一下 01trie 和 可持久化01trie,补了一些比较基础的板子。

模拟赛1 10-12

一套绿蓝紫黑的题

场上估分是 100+100+0+0=200pts
但实际只有 55+100+0+0=155pts
校内 rk2

T1 T2 T3 T4

T1是一道很一眼的线段树，单点修改维护最大子段积，但是打挂了，一定是大样例太水的问题而不是我的问题。

T2也是一眼树形dp，但是一开始状态设的不对，导致转移困难，后来把状态改了，思考了一下转移顺序优化了一下上下界，大样例一遍过，爽。

T3其实剩下时间挺多的，但是比较累，大概推出来了有效数据很少暴搜应该很高分，但是没打，因为懒。 结果考完发现 @feropen 记忆化搜索+剪枝直接过了，场切紫题%%%。

T4就不用说了，考场上看都没看一眼，赛后倒是手玩了一下小数据发现能很轻松的骗15分，血亏。

week -2

这周还是把基础的板子做了一下练习，然后对着 noi 大纲补了一下图论，主要是 Tarjan 全家桶，还简单做了一下笔记。

模拟赛2 10-17

一套绿紫紫黑的题 （洛谷2023 NOIP 模拟赛）
（CSP-S模拟赛ljt你拿NOIP模拟赛过来，你可真看得起我们啊）
场上估分是 100+10+0+0=110pts
实际 100+10+0+0=110pts 校内 rk5

T1 T2 T3 T4

T1

贪心+数学题，研究质因数与因数个数之间关系，花了20min推出来然后打了个拍，场上一直觉得做法是假的但拍过了，索性就不管了。

T2

Ad-hoc 题不一定能区分最强的人，但一定能区分出谁最适合做出题人npy。

构造题，硬控我两个小时，死透了，最后打了个表豪取10pts。 赛后一看是道图论，用到了一个trick叫zig-zag pattern，也写了一个笔记。

T3

基本没看

T4

基本没看

模拟赛3 10-19

在lgj那里做的最良心的一场模拟赛(信心赛)。
一套橙蓝蓝黑的题
场上估分是 100+100+100+37=337pts
实际 100+100+0+37=237pts
不知道 rk几，但是有三个AKer，两个初三的和 @tallbanana ,%%%。

T1 T2 T3 T4没找到原题

T1

给出 n 个数求一个非负整数 x 对这 n 个数取模之和的最大值，就是

\sum_{i=1}^n(x\mod a_i)

的最大值。 一开始看成了求x，还准备打高精，硬控自己半小时。

T2

一道很套路的最短路，三遍 dijkstra 直接冲过去了。

T3

原题，n 个数，每次操作将区间内数变成它的因数个数，询问区间和，也是很套路的题，每个数经历过一定次数的操作后值为 1 或 2，之后再怎么操作值都不会再改变，如果一个区间所有的数值为 0 或 1 就进行标记，疑惑对这个区间的操作全部无视，用一个线段树很简单就能维护。但是我打挂了wwwww。

T4

没有原题所以放一下题目大意： 在一个无向图上计数长度为 5 条边 6 个点的路径，可以重复经过点，但不能重复经过某条边，数据范围是 n \le 500。

图论，正解是三元环计数和四元环计数然后分类讨论，总之我不太会，场上打了暴搜喜提 37pts

模拟赛 4 10-20

md，ljt 周日一大早把我叫回学校然后让我打 MX 模拟赛，原因是他懒得起床组题，蚌埠住了。

上午 MX-J

场上估分是 100+100+100+4=304pts
实际 100+100+55+0=255pts
洛谷 rk 29 , 校内 rk 1

比赛链接

T1

以标记点为中心记录一下左右段最大次大值最后组合一下就可以了，五分钟切掉。

T2

数学题，求一个多维体对角线上共有多少个单位，看起来挺抽象的，但是贴心的给了个式子

称位置

这不就数学题吗，想到枚举每个k，对于每一维只有可能是

#### T3 模拟题，对于每个树种下后尝试用类似洪水填充的算法向周围蔓延，并记录这个位置最早什么时候出现树，每种一棵树检查四联通位置就可以，但是考场上有一个一眼结论居然没看出来，导致多打了很多条件，最后超时了…… #### T4 没什么时间，考场上只看出来是个类似区间dp,但赛后有人说是错题?? 打了个特殊性质就结束了，然后还挂了。 ### 下午 MX-S 场上估分是 $100+0+0+0=100pts

实际 100+36+0+0=136pts
洛谷 rk 189 , 校内 rk 1

比赛链接

T1

一眼线段树，想了一会，先打了二分套线段树 O(n\log\log n) 的做法，先二分轮次，再二分第几个然后线段树区间查询，然后突然发现因为前缀和单调不减，我可以直接遍历线段树来找到第一个比某个数大的前缀和，O(n\log n)。

T2

没想到dp，盯着一个假算法调了3小时，最后还让我骗到 36pts，勉强还行。

T3,T4

没看（

week -1

最后一周刷了一些绿到紫的高质量题，经典题，思维题，感觉还可以。

周一学校组织去秋游，玩了一天机动游戏，跟同学打水仗很开心。

晚上回来发现估值比赛情况从个位数蹦到了98，直接把我从绿名抬上了红名，但没高兴多久就发现棕了，吓了一大跳，最后调查出来是帐号没管好被人赛时c了代码，没办法，自认倒霉吧。

模拟赛 5 10-24

ljt总算是放了一场信心赛啊

难度 绿蓝绿绿

场上估分是 100+100+100+100=400pts
实际 100+100+36+100=336pts
校内 rk 1

T1 T2 T3 T4

开场先被 ljt 的电脑镜像硬控半小时

T1 是一道dp，当我开题的时候旁边的 黄队 @steve_xh 已经过了大样例了，仔细想想是个很一眼的dp，但还是调了小半个小时。

这里提一嘴为什么叫黄队，原因是校长来信息室看我们的时候，问我们今年是不是能出一个省队，@steve_xh 由于带着耳机没听清不假思索地回答了是，想必一定是有省队实力，%%%。

T2 一眼数据结构，之前做过一道类似的，很快想到用线段树维护(,),(),)(的数量，操作的时候直接分别交换(,)和(),)(的数量就可以了。

T3 类似于表达式求值，不过换成了三目运算，挺套路的，由于都是 x>常数?常数表达式:常数表达式 这样的形式，x 在某个区间内产生的结果都是同一个常数，所以递归处理出每个常数对应的区间，排个序然后询问二分查找 x 在哪个区间就可以了。但我因为数组开小痛挂 64pts。

T4 换根dp 板子，设 dp_i 为所有节点到 i 的距离。第一遍 dfs 求出 dp_1，第二遍通过换根处理出所有 dp_i，用一个变量 sum 记录 \sum_{i=1}^ndp_i，对于每个询问输出 sum+2*(dp_k+w)。 结束前30分钟才看题，太一眼了直接一遍过了所有大样例，爽。

Day -1

最后一天没做什么题，主要是看了之前做的题和模拟赛总结了一下，还有写这篇游记（，机房其他同学几乎全在打 generals，被老师发现还以为无聊的在玩扫雷，一个格子周围几千颗雷这埋雷密度属实有点大啊（。

下午终于是吃到了教练承诺已久的校内rk前三奖励，点了一个麦当劳巨无霸汉堡，下午提前放学，五点就回家了，原本要上到七点半。晚上也是放松了一下跟朋友玩mc整合包。晚上11点半才睡。

Day 1

经过将近一个月紧张刺激的备考这一天还是来了，早上起晚了，7点半才起床差点迟到，还好家距离考场比较近，直线距离 600m 左右。

CSP-J

来到考场发现整个考场只认识同班同学 @caotianhao。提了瓶大可乐进考场，俩监考员商量半天能不能带可乐，差点以为带不进去。坐在考场最后一个位置，估计是没有多的椅子给我搬了个老师办公室那种椅子，巨舒服。但因为视力不好导致看不清压缩包和pdf 密码，硬控十分钟。

8:35~9:00

T1

水题，每张牌判断花色和点数并标记，最后全部遍历一遍所有花色和点数就行，三分钟秒了。

T2

小模拟？总之直接模拟能过，也是五分钟秒了，心想今年怎么这么简单。

T3

考场上一眼认为是一道dp，设 dp_i 为用 i 根火柴棍能拼成的最小数字。也是十分钟打完了。

9:00

开始看 T4，一开始看错题了，以为元素值域只有 1\le x \le 9，认为又是道 DP，打完发现不对，后来把什么数据结构图论贪心全想了一遍，最后认为还是 DP，但是不会转移，一度认为切不出来绿的我是个废物，但感觉这题应该不止绿能上蓝，算了休息一下下午准备打 S 组吧，打了个记忆化开始靠在舒服的椅子上睡觉。

11：55

快结束了突然发现 T3 要开字符串啊啊啊啊啊啊啊啊啊啊，手忙脚乱的打了个高精度大小比较，但是挂了过不了样例，最后改回了 long long，估计这题是挂了。

上午估计是 100+100+20+10=230pts，丸辣！ 一问同学全是 300+ ，寄。

中场休息

中午跟着同学一起出去吃饭，好好饱餐一顿。

得知黄队@steve_xh 可能没睡醒，把昨天ljt发的防爆零攻略和准考证一起带进了考场，还被监考员在赛时搜出来了，被拍了准考证，寄，防爆零攻略变成防不爆零攻略了。

CSP-S

下午准时回到考场，这回考场里认识的就多了，有一半都是我们学校的，@_sst_ 说我用的那台机试机工作是他完成的，应该也许大概不会有问题，到这我已经感觉不对劲了，有种不祥的预感。

2:27

开始了，T1一眼贪心题，排个序，尽可能先用小的去打小的就可以，用双指针扫一遍。五分钟切了，过了所有大样例，突然就很有信心。

3:00

诶呦我去，T2 什么东西啊，加速度？匀加速运动？即时速度？我才初二物理刚开始学啊，是不是还要考虑精度问题？跳了跳了。

3:10

开 T3，一看题感觉是道 dp，考前恰好做了一道状态有点相似的。很快设出了朴素 dp 的状态，设 dp_{i,c,j} 为第 i 个涂的颜色是 c，另一种颜色上一个是 j，开始推转移方程式子。

3:20

推出了式子然后开始敲朴素 dp，很轻松的敲出来然后开始调大样例，因为一点蠢错误调的有点久。

4:00

朴素 dp 调出来了，但是复杂度是 O(TnV) 的，V 是数的值域也就是 1e6。考虑优化，发现转移貌似都是查询区间最大值，区间加，单点修改之类的，马上想到线段树维护，打了一颗线段树并开始调试。

4:20

水母中学这老爷机什么时候能换换啊，电脑突然死机了，好烦，闹心，估计至少损失 10min，但我认为剩下时间肯定够我把 T3 调出来，当时认为 200 pts 也够本了，所以也不是很着急。

4:30

丸辣，说好的E盘不还原呢？？？我文件呢？？？下发的题目文件都没了？？？不是怎么测试的机器啊，啊啊啊啊啊，当时已经想好退役了要怎么好好学文化课了，但还是赶紧举手通知了监考员，监考员给我换了一台电脑。

5:30

重新把 T1 和 T3 朴素dp敲了出来，调试 T3 又因为一些很烦的小错误花了老半天时间。这时监考员过来跟我商量延时的问题，可以给我补 30min,可我损失了接近 2h 啊！！经过一番小拉扯最终要到了 1h 的延时，赶紧冷静下来继续打代码。

6:10

成功把 T3 调了出来，复杂度O(Tn \log V)这时候心里已经比较有底了，因为感觉自己保底也有个 200pts 左右，而且还有 1h20min ，看了一眼 T4，感觉很复杂，估计是个黑，而且暴力和特殊性质还给的很抠搜，于是回头冷静分析 T2。

6:25

发现 T2 O(nm) 暴力有60分，以及特殊性质A、B，加速度非负的话只用检测最后一个测速点时是否超速，直接开敲。

6:40

其他人都离开考场了，父母在考场外找不到人估计很着急，但没办法，本来想让同学跟父母打声招呼，但我还在考试啊，不敢说话，心有点乱。

7:00

暴力和特殊性质AB都调出来了，还有半个小时，开始思考性质 C 加速度为负，发现对于每辆车能检测到超速的测试仪必定是一个区间，于是把每辆车的区间二分出来，然后就是求若干个区间每个区间中都要至少包含一个被选中的点，很经典的贪心。

7:10

母亲带着哭腔找上考场来了，估计以为我失踪了，差点没急疯。

7:18

特殊性质 C 调出来了，再一合计把每个车的超速区间全都二分出来跑一遍不就是正解吗？赶紧开始改。

7:23

极限过掉了 T2 所有大样例，再检查了一下文件读写就结束了。出考场的时候整个人处于一种亢奋的状态，两只手都在抽，赶紧拿出手机给家里报个平安，家里好像都报警了。

估分 100+100+100+0=300pts

赛后

问了一圈我好像是学校最高的，但总感觉 T3 O(Tn\log V)有可能会被卡，而且还是多测。

Day 9

出分了。

J: 100+100+20+5=225pts S: 100+100+75+0=275pts