CCF CSP-J/S 2025 游记

songxr111 · 2025-11-09 08:57:14 · 生活·游记

初赛

全部搞忘了。

脑海中只剩下了 You have no egg!。

复赛

Day -14

停课了。

日均 1 模测。

日均挂分 + \inf。

Day 0

参加 @for_fo_f 举办的“别样的模板大战IOI1146”，复习模板。

Day 1

Morning (-J)

6:50 起床（好困）

7:40 高速一路不堵。到达考场。冒雨拍照。

8:00 进入考场，打快读模板。

8:20 监考老师说不让提前写代码，笑死。

8:35 终于把密码搞到了，阅读题目。

T1

显然把所有数字字符搞下来从大到小排序输出即可。

T2

小模拟。但我不想模拟。我要 O(1) 计算坐标。

答案怎么不对？原来是 lower_bound 没传 cmp 计算了滚木的排名。

T3

什么异或。J组都要考异或了。

使用前缀异或配对把它转化成一大坨区间之后，按右端点排序。贪心计算答案。

与去年 S 组 T2 超速检测的做法呼应上了。

T4

一眼dp。为什么 a_i\le5000？因为我们要使用背包dp。

以上全部写完是 9:44。

接下来干什么呢？

写考场题解吧。

还以为能上迷惑行为大赏。

谁知这还不够抽象。

::::info[sol.md]

# CSP-J 2025 Solution (during the exam)

My English is not so good. So pardon me for my mistakes.

## T1 number
Take out all the number characters, sort them from the big one to the small one. Then output them directly character by character.

## T2 seat
First calc the rank of Mr.R's score. You can use `std::sort` and `std::lower_bound` to do this thing. Then calc the row number by dividing the rank by n. The rest part is the line number. If the row number is even, the line number should be reversed(`y=n+1-y`). Please pay attention to the result of dividing: you need to let the rank decrease 1 first before the dividing. Then the result should increase 1. By doing this way, you can get the correct result.

## T3 xor
First, you need to pay attention to that the xor sum of a segment [l, r] could be discribe as `s[l-1]^s[r]`, while `s[i]` score the xor sum of the segment [1, i]. Then, by reminding the place of the `s[i]` or `s[i]^k`, you can easily get the segments which its xor sum is k. Then it becomes a very tradtional Tanxin problem: choose the segments as more as possible to make them don't have any part in common with each other. Sort the segments by the rightest point. If now the segment's leftest point is bigger than the rightest point of the chosen segments, you can choose this segment. Get the answer by counting the chosen segments.

## T4 polygon
It's easy to find this problem has to do with Dynamic Programming. Sort the numbers first. If we want a number `a[i]` to be the biggest, we need to find the ways of choosing numbers which smaller than `a[i]` to make their sum bigger than `a[i]`. It is too difficult, so we can try to calc the ways of choosing numbers which smaller than `a[i]` to make their sum smaller than `a[i]`. Then we can design DP: `f[i][j]` shows the number of ways to choose the numbers from `a[1]` to `a[i]` and their sum equals to `j`. It is an easy 01-backpack DP problem. Let `g[i]` equals to the sum from `f[i-1][0]` to `f[i-1][a[i]]`. If we let `a[i]` is the biggest number among the chosen numbers, the answer will be $2^{i-1}-g[i]$. The final answer is calced by adding all the answers of letting `a[i]` is the biggest number among the chosen numbers.

:::: 考场 Windows 下居然没有一个像样的 markdown 编辑器，唯一的 VSCode 还在虚拟机里。

结果写到一半虚拟机死机了。后一半只能在记事本里写了。

以上全部写完是 10:45。（大概吧）

接下来干什么呢？

写对拍吧！

使用 O(n2^n) 枚举子集的暴力做法拍了拍 T4，拍了大概 30000 组。没出锅。

以上全部写完是 11:20。（大概吧）

接下来干什么呢？

edge://surf？ 根本加载不出来。太慢了。

小恐龙？ 我懒得开 Chrome。

Linux下Python神秘游戏？ 我搞不来。

开始发神。

11:55 发现 T1 完全不用 std::sort，直接桶排不就完了。为了让代码跑得更快，还是匆匆改了一下交了上去。还好没出锅。

Afternoon (-S)

12:15 中午照例光顾冒菜馆（不知道为啥每次出来考试我妈都要吃冒菜）

13:00 睡觉。根本睡不着。丸弹了。

14:00 进考场。没敢打快读模板。只因进了考场想出去上厕所，于是进行了两次身份验证。

14:28 解压压缩包。看来 €€£ 为了补偿 J 组密码发晚了的失误， S 组就提前发了密码。

14:30 打快读模板。

T1

按 €€£ 的尿性应该是贪心吧。

非常直白的想法：每个人都先选最大的。如果有某个社团有超过 \dfrac n2 个人，就考虑修补，按这些人的“修改代价”排序，把多的那一部分修改到剩下两个社团去。由于限制是 \dfrac n2 个人，所以修改一定合法。

考完才知道这叫什么“反悔贪心”。不管了。

以上写完大概是 15:10。

T2

原来是图论题。

先想到了枚举要开发的乡村的子集，并跑最小生成树的 O(2^km) 做法。

不过话说 €€£ 的评测姬到底多快呢？没有人知道 10^9 能否闯过去。

（事实上真的有人就这样闯过去了）

想了半天优化，好像只有原图最小生成树中的边才有用罢。没找出反例。

于是优化到了 O(2^knk)。

手写了 maker.cpp 造数据测试，这两份代码好像都 1.05s。改了跟改了一样。

不管了。

以上写完大概是 16:15。

T3

氖龙串串题。

作为资深蒟蒻，只能想办法写暴力 。

先找出每个替换串的“最小替换单元”（其左右两侧没有多余的字符是一样的），存储每个替换串的“最小替换单元”和其左右两边多余的公共字符。每次查询就遍历一遍所有替换串，判断“最小替换单元”、左右两边多余的公共字符是否和当前的一样。拿出了陈年 hash，复杂度 O(nq)。

尝试特殊性质：“最小替换单元”相当于将 \texttt b 左移或右移几个位置。左右的公共字符相当于限制长度。长得有点像二位偏序。

于是又写了不少于 200 行的 s**t mountain。

一跑样例。小的都对。大的全 WA。还以为是 hash 太弱，换了几个底数后依然全部炸飞。调滚木。

突然发现，题目说 “两种 s 的替换不同当且仅当子串 y 的位置不同或用于替换的二元组 (s_{i,1}, s_{i,2}) 不同，即 x, z 不同或 i 不同。”。

丸弹了。这个做法只管了“用于替换的二元组”不同，没管“子串 y 的位置不同”。甚至还举出了反例。

做法甲烷了。

特殊性质 99.999\% 挂了。还是删了吧。于是特殊性质写了和写了似的。

不想管了。直接交吧。

做到这里已经 17:30。

已而夕阳在山，思绪散乱，无人可归而无人从也。

T4

排列计数题。

显然不会。状压dp && 特殊性质跑路。

以为所有题都是水题的特殊性质一样输出 n!，没想到还有 c_i=0 的 CS （不管题多水你都要走，那你**来面试个*）。

所以考场上把得分算错了。以为这个能拿 40\text{pts}。实际只有 24 \text{pts}。

做到这里已经 18:00。

接下来开始对拍吧。T2 1.05s 太危险了，还是加个 fread 吧。满格数据 0.3s。两种做法对拍 3000 组没出锅。大喜。

考完之后以为自己 T4 写完特殊性质后没有编译运行过就交上去导致 CE。自己吓自己。

Day 2

当然是在家划水啦！！！

自测根本没测。我懒得再打一遍。

预估分数：J：100+100+100+100=400，S：100+100+\mathrm{rand()}+44。

Day 3-5

恶补文化课。

Day 6-7

氖龙半期考试。丸弹了，没有一道题会。不想看分。看分影响考试心情。

（此处省略 114514 字）

Day 8

看分。写游记。

J： 100+100+95+100=395。T3 挂分，死因是没特判没有合法区间的情况。

S：100+100+25+24=249。除 T4 场上算错分之外，没挂分。大喜。

怎么 1 \;\rm mol 的人用 AC 自动机切掉了 S 组 T3。看来只有我一个人不会。丸弹了。

大佬们告诉我：S 组 T3 “两种 s 的替换不同当且仅当子串 y 的位置不同或用于替换的二元组 (s_{i,1}, s_{i,2}) 不同，即 x, z 不同或 i 不同。” 是诈骗。同一个替换二元组最多只有一种方法来替换询问串。我才发现考场上举出的“反例”没有任何问题。

所以我的 T3 没假！

2025/11/9 upd： T3 真没假，只是代码有一个小 bug。考场上没造小样例自测。改对之后也是成功拿到了 O(nq) 做法的 50 \text{pts}，记录。这么说下来，T3 算是挂了 25\text{pts}。感极而悲者矣。

太搞笑了。

后记

我常常追忆过去。

…………

我该在哪里停留？我问我自己。

噫！微斯人，吾谁与归？

时乙巳年冬月九日。