专栏文章
【CSP2025游记】第一篇也是最后一篇CSP游记
生活·游记参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @minfbc1h
- 此快照首次捕获于
- 2025/12/02 01:28 3 个月前
- 此快照最后确认于
- 2025/12/02 01:28 3 个月前
如标题所述，本人今年高二。
我其实很少会有写游记的冲动，但是刷luogu的时候刚好刷到游记的征集，想起这大抵是最后一次参加OI，便随手写一篇吧。
2025/11/6 更新：在题目后附加了最终成绩；新增了 “当初听我的现在S早就两百分了” 这一章节。
J-T3的启发：程序状态^肠胃状态==1
坐标福建福州，考点十八中，和往年一样，考前晚上打印好准考证，让妈妈从抽屉的深处拿出身份证，准备好一包餐巾纸和一瓶水，放进袋子里就行了。是的，今年我连笔都懒得带了哈哈。
在这里，劝年轻气盛的小朋友们，一定要带好纸巾。因为你永远不知道你的程序和你的肠胃哪个先崩......
是的孩子们，早上吃的稀饭配土豆，做J-T3的时候，我的肚子已经开始翻江倒海了，再加上本来就紧张，最后向老师报告去厕所了。还好纸巾有带够。（不过大家实在忍不住还是得打报告上厕所的，没带够纸巾也可以向老师要哦，我只是有点社恐qwq）。
好了好了不聊这么有味道的话题了。
保安是TLE大佬orz
八点二十二分，准时到达考场门口，熟练的掏出准考证和身份证让保安放我进去。
“现在考试都开始了，你进去干嘛，你迟到了。”
....？
刹那间，天地倒转星河日月仿佛永无边际的向外流去，独留我一人留在这浩瀚宇宙，约两秒后，这种懵圈的感觉消散，我拿起准考证，确认是八点半而不是八点开考。
老实说，有那么一瞬间，我真以为我记错时间了。如果高二OIer记错考试时间的话，那OI生涯应该也要烂尾了罢（悲）。
对话继续。
“不对啊，八点半才开考啊，现在二十二分”
“不都是提前十分钟开考吗？”
.......？？？？？？
我这两年来都在这考的，怎么到今年就改了。
“你要不先放我进去，如果不准我入考场我再出来...”
放行了。
当我飞奔至五楼机房时，哈哈！大家都还在排队检入！排老长了！
那我问你，什么叫做提前十分钟开考但是大家都还在排队检入.jpg不过无所谓，反正明年我也不来了，不计较。但是这事的印象挺深刻的，不知道有没有人有这种突然发现自己记错时间的共鸣~
总之，差点在考场门口TLE了...
“当初听我的现在S早就两百分了”
如图所示，本人其实是押题大手子。
考前一天：
考完当天：
当初群友们要是听我的，现在早就J组300分、S组200分了哈哈哈。
J组：8:30~12:00
开Frc，建文件夹，打个hello world练练手感（顺便测试一下键盘坏没坏，这很重要）......
插个题外话，大伙的压缩包密码也是#拼音+数字+拼音+数字的格式吗？求压缩密码解读喵。好奇喵。
T1&T2 字符串找数字&根据名次蛇形排座位（AC）
全是水题，绝对不是我水平进步了。
意思就是，T3、T4才会是决定一等还是二等的关键题目。
T1思路：双重循环，第一层i=9...0，第二层j=0...text.size()，满足text[j]==i+'0'就输出text[j]。
T2的排座位其实让我思考了十几分钟，对题目拥有轻微强迫症的我一直在找一个优美的算式能够一步到位的，后放弃。注意到最多就一百个座位，遂选用循环。
难绷的是，出考场，看到别人用的桶排，把座位全部排序一遍，然后再统计成绩比自己高的，然后再排座位....他甚至局部设置了一万个桶，bro的CSP笔试成绩有几千分orz。
在此敬告各位朋友：CSP-J的第一题和第二题绝对能在30行代码内完成，因此请认真读题，并牢记CSP笔试成绩最多只有100分。
T2思路：输入时直接比较并得出所求的排位，将排位R一直递减行数N（同时列数C从0开始不断自增），直到R<=N为止。此时C+1就是当前列。如果当前是奇数列，则正数排，否则倒着排（题目要求蛇形排位）
T3 求最多个异或和均为k的不重复区间（60pts）
我去，我真是个OI天才口牙！妈妈，我要AK IOI哩！ ——某位想出异或也能用于前缀和的选手，在考场上的内心惊呼
惊呼后，是思路卡住的沉默。
其实我对位运算不熟，就连异或的真值表也是用Python现场算的，不过这次记很牢了，同值为0，异值为1。
在花费两分钟再次暴力枚举推导出：
由此可设异或前缀和：
综上可得：
因此，求出区间
[l..r]的异或和是的。后面不会，我用的记忆化搜索，不保证AC。
T4 求若干条边组合成多边形的方案数（40pts）
令人意想不到的是，我只花了5分钟就搞定了T4，
的部分分。
是的，我用的深搜，由于写T4的时候剩下最后几分钟，我甚至来不及优化，但是小样例应该能过。
S组：14:30~18:30
鉴于考场的保安熟练掌握TLE技术（见上文），我下午17分就到了（好吧也不是特别早但是保安没拦我o.O）。
T1 社团社员太多了!!!（AC）
标题源于《败犬女主太多了！》，强烈推荐这部动漫qwq
一个人性化的社团，需要把社员调剂至三个部门，求一个能让所有社员尽可能满意的方案，且调剂后每个部门的人数不超过总人数的一半。
一眼贪心。
二眼动规。
三眼蒙圈。
在认真研究了十几分钟之后，从“每个部门的人数不超过总人数的一半”这个条件看出来是贪心。果然直觉很重要啊~
T1核心推论：
- 不可能有两个部门的人数都超过了总人数的一半。
- 如果有一个部门的人数超半，则把该部门人数调整至刚好半数，就能保证所有部门不超过半数。
T1思路：
- 统计一个员工“如果无法去最喜欢的部门，那么去哪个部门所损失的满意度最小”，损失的满意度即最大满意度和第二大满意度的差值。
- 先无视“每个部门的人数不超过总人数的一半”这个条件，让所有社员去他们最想去的社团。由核心推论得：此时最多会有一个部门的人员爆满。如果都没爆满则一切安好，出现爆满就要开始调整了。
- 调整的过程：从爆满部门的社员中筛选，从损失的满意度最小的社员开始，依次调动到其他部门（即该社员的满意度从最大变成第二大，这会尽可能小的影响总满意度）知道部门刚刚好满员为止。
这道题挺迷惑人的，出了考场之后，一堆人用什么最小生成树。最迷惑人的地方莫过于题面给的这组数据：
CPP10 9 8
4 0 0
很多人看到这个样例就默认要动态规划之类的了，但其实调走第一个社员，损失的满意度仅为1，调走第二个社员，损失的满意度高达4。该样例从损失的角度出发，依旧可以用贪心算法来解释。
谁说贪心一定要贪“我得到了多少”呢？
我尽可能损失的小不也是贪心吗？
T2 我们的老熟人road（0pts）
往年CSP也出过一道题，也叫road。没想到在这还能碰到他。
我和road真是一对苦命鸳鸯。
本题是图论，本质上求的是用最小的代价连边，使得图是连通的。并且可以动态加点加边。
不会。我依旧用的深搜。因为我只会无脑深搜哈哈哈。
T3&T4 题都看不懂qwq（0pts）
T3不会，T4无脑输出0。
尾声 - 回忆
事实上，作为高二的“老人”，和我同龄的人已经能做到在CSP-S中怒考两三百分“炸鱼”了。
但是我的编程是自学的，没有花钱报名过任何培训班。免费的课程也只有初中有每周一节的校OI课，以及国庆的公开集训课之类。
我也没有脱离学校的课程，我将来肯定正常高考，我没有很强的OI天赋，也没有对OI非常热爱（事实上，我有时很讨厌算法），但是我不得不承认，OI俨然成为了我生活中的一部分。
如果运气好，我会踩线晋级NOIP，然后拿个三等奖，或者什么都没拿。我不会觉得遗憾，因为我忘不了....
忘不了，初中时，坐在妈妈的电动车后面，手捧《一本通》，仔细研读着记忆化搜索。
忘不了，机房中，和我的前桌女同学不听课光聊天，强忍着困意，度过中午的时光。
忘不了，测试时，我直接默写高精度模板，第一个AC，被同学刮目相看。
忘不了，老师说，小弟，好好学习，不要浪费你的天赋。
忘不了，初复赛，做出题目时的喜悦心情，和面对难题的紧张忐忑。
忘不了，出考场，立马兴奋的打开手机，和同学，老师，网友分享题目做法和心得趣事。
忘不了，我当初玩OI，其实只是单纯的拿奖炫耀耍帅。
这些细节，比站在领奖台上更令人印象深刻。
没想到写着写着竟然升华了哈哈哈！
写到这里，已经是考完当天的傍晚了，我也该去睡觉了，如果有机会，以后我会更新一些CSP遇到的小趣事（其实还有很多没分享哦）。
这是第一篇也是最后一篇CSP游记。拜拜！
相关推荐
评论
共 1 条评论，欢迎与作者交流。
正在加载评论...