CSP2025 油机

· · 生活·游记

省流：自己看完。

Day 0

甚至要到了体锻，但是不出所料，上高一后就很少人踢球了，爽但不太爽。

听到学弟问要不要背快读模板，感觉根本背不下来，而且大概也没用吧（伏笔

Day 1

终于不用早起了，但是还是睡到 8:00 就不想睡了。早上在复习板子，被教练看见了，于是就有了：

伏笔）

中午看了 J 的题目，为什么我不参加就这么简单，学长 AK 后玩 Ukraine 方块被抓包了？

中午直接睡到 14:10 才起来（为什么我的闹钟没响？）。问监考能不能带水杯进去，他说：《喝一口就行》，所以是怕我带炸药进考场？？？

密码输的最快的一次，开 T1，然后回了，但怎么有点像反悔贪心？写写写，本地跑 1s+？为什么 5\times10^5 个整数不给快读？把堆改成排序就更快了，现在是真怕 T1/T2 被卡常。

开 T2，直接保留最小生成树做就行了，先写了 \mathcal O(n2^k\log n\alpha(n))，要跑 1.6s。为什么 3\times 10^6,1s 都不下发快读？？？CCF 不会默认大家都会 fread 吧。再看一下归并可以少一只 log，写写写，为什么少一只 log 还要跑 1s？丢了。

开 T3，感觉不太会做，推了一下性质发现只要会快速做两个有多少个 x_i\in A,y_i\in B 即可，但这很明显不能快速做吧。然后就开始乱想了，中途甚至会根号分治做 \mathcal O(L\sqrt n)，但是为什么这和 \mathcal O(Ln) 一个分？？？计算后发现 \mathcal O(n\sqrt L) 可以过，然后就磕了一场的根号，然后就寄了。AB 性质一共打了 7kb+，考场直接被调红温了。

T4 提前看了，排列计数一看就不会做，最后 15min 极限拿下 24pts。虚拟机过编后都来不及测大样例就结束了。（为什么 14:30 发的密码监考员说 14：27 就开始了，一定要 18:27 结束，CCF 是差 3min 赶晚高峰吗？？？）

赛后遇见 yhm 问 zlt 2h 有没有 AK，直接自闭了。mlk 觉得自己好帅，然后就 AK 了。

估分：100+100+70+24=294。

Day 5

T3 没判 |t_1|\ne |t_2|，自闭了。

申诉查分？？？

## Day 6 T3 $|t_1|\ne |t_2|$ 没被卡，但是 $\operatorname{maxl}$ 开成 $\operatorname{maxn}$ 了，坠。 原来 T3 放到两棵 Trie 上就从 $x_i \in A,y_i \in B$ 变成 $x_i\in [l_1,r_1],y_i\in [l_2,r_2]$，就可以二维数点了，这么笨可以滚了。 无敌坦克手贝塔获得成就：$\max(\text{CSP-S 2025})-\min(\text{CSP-S 2025})=3$。 ### replace 题解： 手玩一下可以证明，将 $(s_{i,1},s_{i,2})$ 定义成 $(a_i,b_i,b'_i,c_i)$，其中 $a_i$ 为 $LCP(s_{i,1},s_{i,2})$，$c_i$ 为 $LCS(s_{i,1},s_{i,2})$，$a_i+b_i+c_i=s_{i,1},a_i+b'_i+c_i=s_{i,2}$，同理将 $(t_{i,1},t_{i,2})$ 定义成 $(A_i,B_i,B'_i,C_i)$，则能将 $t_{j,1}$ 通过 $(s_{i,1},s_{i,2})$ 替换成 $t_{j,2}$ 当且仅当 $a_i$ 为 $A_j$ 的后缀，$b_i=B_j,b'_i=B'_j$，$c_i$ 为 $C_j$ 的前缀。 $b_i=B_j,b'_i=B'_j$ 的限制好做，直接将所有 $(b_i,b'_i)$ 哈希后存在一起，查询时找到对应的集合即可。剩下两个限制不能直接做，前缀后缀可以考虑建出两棵 Trie 树，限制就变为了求有多少个位置在第一棵 Trie 上一个子树内，在第二棵 Trie 上为当前点的祖先，然后使用 dfs 序即可转成二维数点，在第二棵 Trie 上 dfs，用树状数组记录第一棵的区间点数。时间复杂度为 $\mathcal O(L1+L2+(n+q)\log n)$，空间 $\mathcal O((L1+L2)|\sum|)$. ### employ 题解： 对排列计数肯定不能直接做，先记录 $f_{i,j}$ 表示面试了 $i$ 个人有 $j$ 个人没有录用的方案数，则目前的人可以分成 $c_i\le j$ 和 $c_i>j$ 的人，尝试直接记录在状态内。重设状态 $f_{i,j,k}$ 表示面试了 $i$ 个人有 $j$ 个没有录用，$c_p>j$ 的共有 $k$ 个人的方案数（$c_p>j$ 的无需记录位置和具体取的值，即延后钦定，这里后面会解释）。 若 $s_{i+1}=0$，此时的 $j\gets j+1$，$k$ 会减去前面选中的 $c=j+1$ 的个数，这里考虑直接枚举 $l$ 表示前面的人中有 $l$ 个 $c_p=j+1$。这里就解释了为什么要延后钦定，因为如果直接在加入时就选择他的位置和值，现在就会算重和算错。这里需要给 $l$ 个人钦定位置和值，所以乘上 $\binom{cnt_{j+1}}{l}\binom{k}{l}l!$ 的系数，转移如下： $$ \begin{cases} f_{i+1,j+1,k-l+1}\gets f_{i,j,k}\binom{cnt_{j+1}}{l}\binom{k}{l}l! & \text{当前 }i+1\text{ 选择 } c>j+1\\ f_{i+1,j+1,k-l} \gets f_{i,j,k}\binom{cnt_{j+1}}{l}\binom{k}{l}l!(pre_{j+1}-i+k-l) & \text{当前 }i+1\text{ 选择 }c\le j+1 \end{cases} $$ 然后 $s_{i+1}=1$ 的就类似了，注意若选择的 $c>j'$ 时不用记录当前选数的方案数。 $$ \begin{cases} f_{i+1,j,k+1} \gets f_{i,j,k} & \text{当前 } i+1 \text{ 选择 } c>j \\ f_{i+1,j,k+1} \gets f_{i,j,k}\binom{cnt_{j+1}}{l}\binom{k}{l}l!(pre_j-i+k) & \text{当前 } i+1 \text{ 选择 } c\le j \end{cases} $$ 最后记得求答案时需要给剩余的选定位置和值： $$ ans=\sum_{i=0}^{n-m}f_{n,i,n-pre_i}(n-pre_i)! $$