CSP-S 2025 神秘游记
Bismuth_Sulfate
·
·
生活·游记
第一次考 S 组，之前考过三次 J 组。坐标 BJ。
复赛开始前
初赛结束后
哦我的天哪看看这是什么，我 CSP-S 组初赛过了。我已经退信竞转化竞半年了，没想到还能过。
哦我的天哪，11 月 1 日劲爆复赛。报名看一看。
哦我的天哪，把我一个住西三环外边的人扔到东北五环的考点吗，有点意思。行吧。
复赛开始前 3 天
我：我不能这么颓废了，我要刷 S 组真题。
（看着 2020 年的公历 10^9 年和可以收容 1.8\times10^{19} 个生物的动物园陷入了沉思。）
（看着 2021 年的 DP 题陷入了更深的沉思。）
（看着 2022 年的不可以总司令陷入了第三层沉思。）
（看着前年的神秘密码锁，去年的决斗游戏陷入了第四层沉思。）
我：S 组难度变化这么大？看看同班同学在打什么。
我于是看到了同学在打括号序列。
我：这个……这是啥。
同学：区间 DP。
我看着那个 DP 题被吓哭了。决心发愤图强学点 DP。
（注：实际上再也没动过 DP 题）
复赛当天早上
我：哦我的天哪我的那些化竞朋友们估计会想念我的。（我们今天要上竞赛课，但是信竞因为要打 CSP 不上）
同学：你在哪个考场。
我：东坝。
同学：巧了我也在。
我：我不考 J 组。
同学：请输入文本。
总之是到了下午，进了机房，开了虚拟机，进了程序回收系统。
---
## 考场上
### 读题环节
哦我的天哪让我们嘟嘟题。
[T1](https://www.luogu.com.cn/problem/P14361):
> 有 $n$ （保证 $n$ 是偶数）个人被发配到 $3$ 个部门，每个人对每个部门有个满意度，你的目标是让满意度最大。特别的，你不能让某个部门有多于 $\lfloor \frac{n}{2}\rfloor$ 个人。
[T2](https://www.luogu.com.cn/problem/P14362):
> 有 $n$ 个城市 $m$ 条路，保证所有城市连通。现在 CCF 的大手让这些路都断掉，修复每一条路有个权值，最小化权值。
我：这不就是最小生成树板子。
> 但是，有 $k$ 个乡村想要城市化。城市化需要花费一些权值，从这些乡村可以和已有的城市修路，修路仍然有权值。（只有城市化之后才可以修路）
>
> 问你怎样可以在花费最小的同时让所有**原来的城市**连通。（乡村可以不连通）
我：我可以收回刚才那个最小生成树吗？
[T3](https://www.luogu.com.cn/problem/P14363):
> CCF 让我们去学语言学竞赛。
>
> 有 $n$ 组对应关系，每组从这个字符串对应到那个字符串。
>
> 然后有 $q$ 个问题，每次给你俩字符串，问你第一个字符串能否通过一次对应到另一个字符串。
我：这是什么？
[T4](https://www.luogu.com.cn/problem/P14364):
> 你是一个公司，有 $n$ 个人过来应聘。每天面试一个人。每天的面试结果是固定的，不会因人改变。
>
> 蛋！每个人有一个耐心值，如果在他前面有至少 $c$ 个人面试不通过或主动放弃，那么他会主动放弃。
>
> 问你有多少种排列方式可以使得有至少 $m$ 个人被录取，答案对 $998244353$ 驱魔。
我：嘶……
读下来发现一道题都不会。完蛋了要爆零了。
这时我注意到 T4 有一个部分分是每天的面试都可以通过。
来吧，我们看看数据。
你等会，什么叫耐心值为 $0$？
*高管：放心！我们精心设计了题目，使得每个人都能通过！*
*面试者 A：不行！只要我前面有至少 $0$ 个人面试不通过，我就退出以示抗议！*
*面试者 B：只要我们不是第一个面试的人，我们就绝不屈服于你们的排序黑幕！*
上面是发生在 CCF 总部的真实影像。确信。
克服万难，我终于……没写出部分分来。
算了算了，输出 $0$ 混一点分吧。万一[总司令](https://www.luogu.com.cn/problem/P8819)的亡魂庇佑我们呢。
第四题离开吧，真的。
等等，我想上迷惑代码大赏，我要在第四题的代码里整点活。就写下考场心路历程吧。
---
### 按顺序切题 T1
回去看 T1。看不懂。
我：这个 $\lfloor \frac{n}{2}\rfloor$ 就很难受，这就没办法贪心了。看起来是个 DP。
写写状态……定义 `d[i][j][k]`...
我突然发现我能想到的唯一状态定义是：
*看到第 $i$ 个人，前面部门 $1$ 有 $j$ 人，部门 $2$ 有 $k$ 人，部门 $3$ 有 $l$ 人，状态为当前满意度最大值。*
这个四次方定义肯定不行。$1 \times 10^{15}$ 个 `int`。被吓哭了。
所以这题一定不能是 DP。
那也就是更高阶的算法。
那这还能是 T1 吗？T1 就搞这么难吗？
我捡回了贪心。因为我注意到 $\lfloor \frac{n}{2}\rfloor$ 是个提示。
---
说下贪心思路。
我们贪心两遍。第一遍是个人都想得到，就是按照每个人最喜欢什么去安排。
这样可以最大化满意度，但问题在于会有部门超过 $\lfloor \frac{n}{2}\rfloor$ 个人。
怎么办呢？第 $2$ 次贪心：
**按照最喜欢 $-$ 次喜欢的值的差值从小到大排序，逐渐挪走所有在超限部门里的人，直到超限部门的人正好 $\lfloor \frac{n}{2}\rfloor$ 个。**
有人可能会疑惑，这真的能行吗？就问一个，你在挪走一个超限部门的人的时候，会不会有其他部门超限呢？
不会。原因很简单。
$\lfloor \frac{n}{2}\rfloor$ 就注定了只能有一个部门超限，不会有两个部门同时超限。
同时也注定了在把超限部门员工挪走的过程中，没有其他部门会超限。
证明很简单，如果上述两件事情会发生，就说明有两个部门人数都 $> \lfloor \frac{n}{2}\rfloor$，这不可能。（两个大于 $\frac{1}{2}$ 的数加起来一定大于 $1$）。
嗯对就这样暴力。
应该能拿满。
---
### T2
怎么说呢……直接上最小生成树当然也能做。不过只能拿 $16$ 分。惨烈。
我想到了这么一种方法：
暴力遍历全部 $2^k$ 种乡村振兴方案，对于每种情况建一个图，在图上跑最小生成树，然后在答案里额外加上城市化需要的代价。
我是这么写的，但是经过我的测试，测试点 $2$ 就已经干到 $27$ 秒去了。
但是往好处想，他至少在 $100$ 秒内得到了答案，说明我们压缩一下可以让他压缩到 $1$ 秒。
于是我就开始各种邪门优化，比如“建图的时候就看乡村振兴的代价是否已经太大”，“跑最小生成树的时候看代价是否太大”，“快读”这样的。
最后压缩进 $700$ ms。
希望能得点分。理论最多 $48$，期望 $30$。
### T3
呜呜呜考场上想到的部分分方法居然是错的……
简单讲就是看从前一个字符串到后一个字符串的变化有什么。
然后拿着这个变化去那 $n$ 个二元组里找。再带入看看这个二元组在不在这个字符串里。
然而这个做法是错的。hack：
```plains
input:
1 1
abcd aefd
abcabcd aefabcd
std output:
0
my output:
1
```
简单讲就是只看前一个字符串在不在里面，不看具体位置。
算了，能拿多少是多少。理论最多 $30$，期望 $10$。
### T4
总司令之后，再无总司令。
理论最多 $100$（出题人发癫答案全是 $0$），期望 $0\sim4$。
## 后记
第一次写游记，算是练练手了。
而且写游记可以让我发现自己的问题，就比如说我发现我的 T1 中可能存在一个致命错误导致 T1 爆零。少掉 $100$ 分就真的彻底没戏唱了。
有没有大佬告诉我 BJ 1= 分数线会是多少。
本文 Markdown 共有 $3836$ 个字符。