CSP&NOIp2022 游寄
IvanZhang2009 · · 个人记录
说在前面
关于本文中的代码：
1、J 组代码并非考场代码，是出考场之后糊的。无 freopen。
2、S 组代码是考场代码。有 freopen。
3、NOIp 的懒得放代码了。
1.初赛
两年没进提高复赛了……考前直接 rp++ 保佑。
进考场前戏称考 J 是去虐场的，考 S 是去被场虐的。
关于 J 组，符合预期。出考场估分 93.5，最终成绩是 95 的高分，荣获无锡第一。
S 组的选择前六道稍有难度，错了 4 道，其它似乎不难（完善程序就是纯纯的送分）。出考场估分 86，最终成绩 87.5，无锡第十二。
于是就这么虐着场地进了复赛。。。
2.江苏的复赛
考前一两周，南京疫情。地点被迫移动至苏州。。。
考前 2 天，刚准备写请假条去苏州，突然说 特派员声称江苏复赛取消。。。
当天下午，突然又说 特派员声称江苏复赛恢复。。。
然后，就又能去苏州了。。。
3.复赛历程
J组
半个小时试机 = 研究电脑构造
先开 T1，原谅我忍不住笑了出来……
考完发现同机房有人快速幂判对 1000000001 和 1000000002 取模是否相同……
打 T3 的时候突然想到特判 a=1。
类似考场代码的东东
然后 T2。想到前两年 T2 排序题不会做，还是有点担心的，然后一看数学题？数据范围裸的提示啊 QWQ。
直接 m=n-d*e+2=p+q，然后就是七年级讲过的知二求二。考完发现一堆人代入硬算二次方程……
开根号没精度咋办？
int sq(int x){
int y=sqrt(x);
REP(i,max(0ll,y-2),y+3)
if(i*i==x)return i;
return -1;
}
懒得找自己的代码了，考完用自己的板子糊了一下代码，跟考场代码差别不大。 类似考场代码的东东
然后粗略地看了看 T3，T4。一看 T3，这不前年 T3 吗？觉得挺复杂的，看 T4 了。
T4 一眼二分？然后想到排序+树状数组。再一看数据范围。
"
打完 T4 想着是不是要求每 20min 存个盘？看一眼时间，甚至还没到 20min。
与考场代码极其相似的代码
然后就想着三个小时死磕 T3 了。
先花了 10min 跟着初步想法手算样例，然后看到优先级问题想都没想直接打括号。然后稍微想了想花了 20min 写了两个栈。短路的时候就往后跳掉一个合法扩号序列。
写着写着发现写栈只要用到栈顶元素，直接干掉原先的就好了啊！
花了 10min 又写了一个，数组啊栈啊什么的全扔了。
样例 1 过了。。。
样例 2 过了。。。
样例 3 过了。。。
样例 4 。。。 怎么那么大？复制不了？
样例 4。。。怎么感觉超时了呢。。。
又瞪了几下我的线性做法。发现对付优先级的时候打括号是
那后面的线性处理好像也没啥用……
一赌气直接把加括号这一步扔了。再测，挂了。。。
QWQ
小样例都过了，然而样例 4 WA 了。花了 30 min 考虑卡掉我的代码。
然后去上了个厕所，回来恍然大悟！
1|(0)&0
按优先级算应该等于 1，但是它会输出 0。
花了 10min 死磕怎么把这个问题干掉。。。
然后发现，当 1|... 短路往后跳的时候，把 & 也一起跳掉就行了。。。
10 min 改完，大样例终于过了！！！
与考场代码极其相似的代码
PS：看到一堆人建树啊，打栈啊，真的不理解。难道不是线性一遍就好了？
剩下一个半小时就罚坐了。。。出考场第一句话：AK 了啊啊啊啊啊啊啊啊啊啊啊！
一些趣事：
1、传说中的上厕所真的有用诶！
2、前两年摆烂就是在电脑上找扫雷玩。今年苏州垃圾电脑扫雷都没有，浅浅地自己写了一个玩，写 & 玩得有一个小时。。。
3、快结束的时候发现下午考提高，线段树好久没写了。写了个线段树玩玩。下午还真就用上了。。。
期望得分：400
民间测试得分：400
最终得分：400
S组
不敢像 J 组一样一题一题打。先全看了一遍。
初看体验：
T1：这个 SPFA 最短路捏？不会写 QWQ。
T2：博弈论？完蛋。然后发现就是求区间最小值的区间最大值，一眼数据结构题。上午复习线段树还挺有用的。
T3：一看题面有点懵。看到“从每个星球开始都能无穷地走下去”就慌了，感觉只能骗了。
T4：
初看之后感觉 T2 还有点把握。就先死磕了。手推一波发现要维护每个序列正负值的区间 RMQ。想了 10min 发现确实要维护 8 个东西。于是开始手写 8 个 ST 表。
然而 8 个 ST 表分别维护的东西把我彻底搞晕了。是维护最大值还是最小值？数组 a 还是数组 b？是维护正值还是负值？没有正/负值怎么办？0 应该放哪里？
浪费一个小时后彻底放弃。开了 ll 以后不知道 MLE 代价太大， 又因为不小心看到旁边有人打线段树， 坚决改打线段树。想了半天想清楚了所有问题，一个小时打掉了。其实很快就打完了，就是调了半个小时。
然后测大样例，感觉跑得好慢好慢。突然想到这个复杂度是 log。但是还是怕 ST 表爆空间交了线段树。
然后欣喜地在期望分数上加了
期望得分：
民间测试：
最终得分：
考场代码
然后继续干 T1。发现每次 SPFA。也不知道我怎么想的 SPFA。。。
然后想了 10min 才想到之前一直想烦了，把能
然后画了几个图考虑维护五元环。没去上厕所竟然灵机一动瞪出了 可以维护从 1 开始经过任意点到达一个点的最大美丽值。（对于每个 B，维护路径
40 min 想+写+调，测了样例 3，跑的贼慢。后来改成维护 3 个值，稍微快了一点。随机了一个 2500 的样例，竟然跑了 7 秒……这常数得多大。。。
然后欣喜地在期望分数上加了
期望得分：
民间测试：
最终得分：
考场代码
然后终于开 T3 了。画图想了 10min，发现这是诈骗题。如果每个点都有出度，那么显然可以一直走下去。然后就存反图写了个 ，然而这次上厕所没什么用。
真的，考试的时候完全没往哈希上面想。知道可以哈希之后半个小时就过了民间数据。。。当时还沾沾自喜觉得又骗到一点分了，反正能上 200，还剩 40 min 做“完全不可做的” T4 还是可以的。
期望得分：
民间测试：
最终得分：
考场代码
赛后得分：
赛后代码
然后看到 T4 数据范围，突然发现可以骗一点分。毕竟当初认为完全不可做是以为
期望得分：
民间测试：
最终得分：
考场代码
总结：
期望得分：
民间测试：
最终得分：
本人初二，也是第一次打提高组。自认为打得不错，只是 T3 过于可惜。
一些趣事和总结：
1、考完发现同机房的人都不会 T1，感到离谱。竟然是蓝？？？
我向来只做得出来绿题。
2、T2 的 ST 表好像不会爆空间 QWQ。。。
3、下午上厕所没啥用。。。
4、T3 没想到哈希实在可惜
5、竟然能在我们学校排第一……发挥不错，继续努力！
4.NOIp
（不放代码了 QWQ）
考前一天拼命复习，写了点简单线段树，SCC缩点，最短路，MST，LCA之类的，啥都没用上。
进考场，等到 8:35 才发题，看题第一眼 meow，整个人懵逼状态。
开 T1。初看不难，签到题。想到前缀和预处理。扫了眼数据范围，看到测试点不等分感到诧异，回去看了眼只有 T1 不等分。觉得至少能骗 80。
仔细想了想发现非常简单。二十分钟过了，测第三个“大”样例眼前一亮。114 514 果然精心构造。。。
看 T2。看到构造有点懵，然后看到数据范围，
T3 图论+数数我害怕极了直接跳过。后来才知道这是 T2 难度，寄。
T4 裸数据结构，但是不会。考前模拟赛还有过区间中区间求和的题来着，没补……打了 20 暴力跑路。我的评价：不会出题也不要板，不要搬！
然后死磕 T2。花了两个小时想了个错解，随机数据下来错误率极高。然后只剩一个小时，做了个错误的决定：死磕 T2 的 15 分！！！
稍微想了想别的做法，发现
最后想了想 T3，突然发现可以边双缩点+树形 dp，但是连暴力都来不及写了。而且，不会 BCC，只会 SCC！！！然后就觉得 T3才应该放 T2。当天回家恶补 BCC。
估分：100+30+0+20
民间：100+0+0+20
（T2 cout 改 printf 就有 30。。。）
评价：
1、T4 垃圾题，出题人出来挨打！
2、T2 T3 放反，组题人出来挨打！
3、T2 挺巧妙，但是你放什么构造啊。。。卡输出速度的话就真的恶心了。
4、T1 不错，送分到位。
5、考前复习的什么东西，我自己出来挨打！
6、总结一下就是寄，不过第一次 NOIp，也算给自己一点安慰和教训。解题策略还要仔细考虑，不能长时间死磕不值得的一点点部分分。