CSP-J/S 2024 游记

Day 0.9

给 云斗初赛模拟 投了个 S 组阅读程序 2，顺便写了解析。

写完解析，以一种奇怪的方式首次 AK 了初赛模拟。

Day 0.99

出的题，发现第一小题就是 UB，被骂了。

写的解析，写挂了好多地方，被骂了。

谢罪。

Day 0.999

初赛前一天。

下载了准考证，BJ-J07477 / BJ-S02891，在北京市第十二中学。感觉今年人会好多。

复习了下 初赛知识点，睡大觉。

Day 1 (09.21 初赛)

08:00 起床，简单洗漱，吃早餐。

08:30 出发，车程 30min 左右。

08:40 在车上看了眼 梦熊初赛模拟，做了选择和程序阅读 T1 T2，荣获 42pts，遂懒得看了。其中有涉及 int 范围和排序算法时间复杂度，就去查了查。

09:11 到达考点，学校约的 09:00 在门口合照，没赶上，刚下车就看见他们进去了。

09:14 进了教室。看到了一群小学生，吊打我，被惊呆了。

09:30 开考。

09:40 看到前面的小孩已经涂完答题卡了，这么牛的吗？

10:10 闭除了完善程序 2 的部分。T4 格雷码没见过，根据考试技巧，选出现次数多的，蒙了 D。T28 T29 要不要考虑 int 溢出啊，还有栈空间呢，感觉出题人会考虑到吧，不然不会出 T30 这种题，应该是 False。

10:20 闭全部。手玩了好几遍完善程序 2，应该是没问题的。咋这么多 B 啊？有点吓人。算了下全选 B 能 50+。

10:30 无聊，观察旁边的人，玩手表。

10:50 旁边的人陆续写完了。使用四分之一斜眼法，观察到 09:40 写完的那个小孩跟我没一个一样的，鉴定为玩原神玩的。观察斜前方的小孩，差的好多，T7 都没对，应该是来玩的。有点慌了，咋没一个人跟我一样。

11:10 右边的人写完了。跟我基本上一样，放心了。

11:20 估分。如果格雷码能对的话，希望能 AK。

11:30 闭考。老师收卷好慢啊，别的考场都放了。

11:45 出了考场，跟学校的合影。突然发现今年校队好多人，全是小孩，穿着 rdfz 校服乌泱泱的。

12:15 去吃了附近的 KFC。周末自选四件套 29.9 RMB，好便宜啊！好次爱次多次。

13:00 在 KFC 闲坐，看各种群里的吐槽。

13:30 小图灵估分出来了，看了眼。怎么 TF 的？怎么扣 6pts 总共 76pts 的啊？垃圾。

13:40 懒得复习 S 组了，刷会 B 站，摆摆摆。

14:05 出发回考场。

14:15 进了教室。发现和 szx 上下午都在一个考场。

14:17 找不到水杯了？落在上午考场了，去找老师取了。

14:30 开考。

14:31 旁边老哥直接睡觉的？题都不写？看起来好像已经高二了。

14:45 闭选择。T10 一点不会啊，蒙的 C。开阅读程序 1。

15:30 闭阅读程序 1。瞪了一个小时终于看懂了，妈的破防了。遂开完善程序。

15:50 闭完善程序。好 easy 啊，普及难度吧，但咋全是 A？有了上午的经验这并不吓人。

16:10 闭全部。阅读程序 2 3 全靠蒙。就看懂一个 solve2() 还有救吗？

16:15 旁边老哥醒了？开始在草稿纸上写游记了？这么抽象。

16:20 突然觉悟想手玩一下阅读程序 3 的选择。模了 10min 发现蒙对了！

16:30 闭考。难受了，太差劲了，退役吗？

16:40 坐地铁回家喵。不敢估分，怕太差劲。

17:30 估分。感觉还行？

小图灵，J 组 94，S 组 73。

J 组。T24 手玩错了，我是傻逼。T28 T29 未知，争议巨大，感觉 int 溢出会炸吧。

S 组。T1 读错题了，看成切换当前工作路径了。T10 不会，看只有 C 选项跟 \alpha 有关，遂选之。T12 以为是 \binom{10}4，错麻了。T15 小学题，妈的只看到了 ((5,7),(6,7)) 和 ((2,5),(4,6))。T17 手玩错了。T23 蒙的 True，T24 到 T26 都蒙的 C，结果就 T24 错了，我是赌神。T28 把埃筛的复杂度记成 \mathcal{O}(n\log n) 了，当时还在由于为啥和 sort 都是瓶颈。T32 忘了蒙的 B 还是 C 了。T33 没想到是左闭右开区间二分，傻。T39 看错了。T40 没看到 inf，对于 memset 的机制不是很熟悉，衰。

Day 1.01

听说还能有泄题的。做干净的奥赛！

Day 1.1

出分了，J 组 97，S 组 70.5。

Day 1.9

考前一周停了课，去 MX 集训。基本上就是每天炼石模拟赛。

面积 cfz & willow & sheep & yt 等人，虽然之前都面过 /qq

期间 sheep 买了学校校服，成功打入内部，多次拿外卖与保安混熟，被本校同学询问「同学你是哪个年纪的」。

期间 willow 和 zzg 玩原，cfz 打五，我和 sheep 以及 qaz generals / hexanaut 交替游玩。

期间天天点外卖，最后几天连着吃了 6 顿华莱士。

Day 1.99

考前一天。

打了牢唐信心赛，切了 T1 T2 T4，真不是 J 组？T3 是神秘题。

晚上写了几道板子，板子大赛 1 & 2。剩下几个没写的板子留给明天中午。

Day 2 (10.26 复赛)

很好赛前打的板子一个没用上。

07:15 起床，打了一遍 Dij 板子，洗漱吃饭。

08:08 到达北工大，好多小朋友吊打我 /ll

08:30 开始考试。

08:39 T1 什么弱智题，直接开个 map，答案就是 52-\text{size}()。切掉。

09:03 T2 什么傻卵题，直接模拟即可，复杂度是 \mathcal{O}(k) 的。切掉。

09:29 读完了 T3 T4，会 T4 不会 T3？T3 不给大样例？

09:59 好像会 T3 了，分类讨论 n\bmod7，考虑构造 \tt xx888 的形式。会赢吗？

10:44 T3 什么规律题，打个表就做完了，跟我的 \mathcal{O}(10^{n/7}) 暴力拍了下，应该没问题。切掉。

11:20 发现 T4 是假的 /ll

11:58 交完了，T4 写个不知道多少分的暴力，遗憾离场。

12:00 考试结束。

12:30 跟亦中的同学吃了个饭，在餐厅打完了 SegTree & Kruskal & Tarjan & LCA 等板子。

13:45 前往考场。

14:00 在考点门口偶遇了学长学弟，可爱捏。

14:10 在考场门口用手机复习了下串串，包括 Kmp 和 Hash 啥的。

14:30 考试开始。

14:41 写完了 Judger，开 T1。

14:55 这么典的题？贪心即可。但我写的 i 从大往小枚举。

15:03 样例 #4 没过？思考许久，考虑用 set 维护。

15:43 突发奇想，把一开始的代码改成从小往大枚举，过了？我是宋词。切掉。

15:50 开 T2。

17:03 T2 经过一系列转化，变为给定 n 条线段，问最少需要多少个点使得每条线段至少覆盖了 1 个点。我不会了啊！只会 \mathcal{O}(n^2) 的暴力，拼个包就能有 90？爽！

17:23 会正解了！排序之后贪心即可。测了下大样例，除了 #3-9 都过了！注意到第一个答案是 0，不妨加个特判。赢啦！最大的点 1.13s！切掉。

17:29 开 T3 T4。

18:27 T3 T4 都不会啊，打个暴力走人 /ll

18:30 考试结束。

红橙橙绿，橙绿绿黑。

预估 J 组 300+，S 组 200+。

Day 2.001

听说已经已经了，洛谷估分 S 组 220。

很遗憾，您的《CSP-J/S 2024 游记》不符合推荐标准。原因是：游记中不应包含暴戾语言（包括但不限于“唐”）。

笑嘻了。

Day 2.01 (复赛题解)

口胡一下。

J 组 T1，红。由于保证合法，直接全部扔到 map / set 里，答案即为 52-\text{size}。复杂度 \mathcal{O}(n\log n)。

J 组 T2，橙。按题意模拟即可。复杂度 \mathcal{O}(k)。

J 组 T3，橙 / 黄。考虑性质 A 怎么做。有显然结论，位数少的数总比位数多的数要小。因此我们贪心的选择每位所需木棍数多的，眼睛瞪出 0\sim9 分别需要 \{6,2,5,5,4,5,6,3,7,6\} 根。注意到 8 所需要的木棍数是最多的，需要 7 根，而保证了 n=7k，直接放 k 个 8 是最优的。考虑性质 B 怎么做。根据 A 的启示，我们仍希望位数更小。考虑在 A 的基础上，选出若干个 8 替换成别的数字，以满足总棍数要求。发现可以将 8 替换成 10，恰好需要 8 根。这启发我们根据 n\bmod7 分类讨论，注意当 n\le14 时需要特判。复杂度 \mathcal{O}(n)。

J 组 T4，绿。考虑没有「连续两轮接龙的不能是同一个人」的限制怎么做。容易想到 dfs / dp，这里以 dp 为例，dfs 打 vis 标记本质上是一样的。用 f(r,d) 表示恰好经过 r 轮能否到 d。在第 s 个人的接龙序列中，对于每个 j\ge i+k-1，有转移 f(r,a_{s,i})\to f(r+1,a_{s,j})。有了限制后，我们发现，令

S 组 T1，橙。考虑什么时候是最优的，当 $a_1<a_2<\cdots<a_n$ 时，可依次让每个 $a_i$ 干掉 $a_{i-1}$，使得 $\text{ans}=1$。这启示我们，要尽可能让每个人充分发挥用处，即干掉一个人再被另一个人干掉。那容易有贪心策略，将其排序后，从小往大枚举 $i$，维护 $k$ 表示当前未被删除的编号最小的人，若 $a_i>a_k$，则用 $a_i$ 干掉 $a_k$，令 $k\gets k+1$，$\text{ans}\gets\text{ans}+1$。反之，若 $a_i=a_k$，无事发生。复杂度 $\mathcal{O}(n\log n)$。 S 组 T2，绿。容易发现，每辆车的速度是单调的，这也就是说，能检测其超速的摄像头组成了一个区间。我们可以用 $x-v$ 公式二分的处理出每辆车的超速区间。问题转化为，给定 $n$ 条线段，问最少需要多少个点使得每条线段至少覆盖了一个点。考虑贪心，我们希望用一个点能满足尽量多的线段，即将这些线段分成尽可能少的组，使得每组中所有线段的交不为空。因此，不难想到按左端点排序后，依次放入每个线段，维护当前的交，若加入后仍有交，则贪心的加入，显然不劣，否则新开一组。复杂度 $O(n\log n)$。  ### Day 2.1 出分了。 J 组 100 + 100 + 100 + 55 = 355。 S 组 100 + 100 + 20 + 0 = 220。 基本上不出所料吧，也是成功为群友垫底。就是 J T4 MLE 挂了许多。 主播明天有期中考试，所以咕咕咕了。