CSP-S 题解反思考场游记

前言：今后可能会考虑在noip时写个游记，csp实在太烂而且没啥好写的。

T1

签到小贪心

T2

第一眼这啥啊。后来想到枚举集合，然后写搜索，调半天发现是回溯的问题，接近两个小时才切，时间上输的很彻底，完全没给后面留出充足时间。

复盘时发现k=0会出错，真服了

没事你们 smr 学长说了csp考好的一般noip都炸，那我提前把该挂的挂了，noip可就不许挂了，去年河北队长的话我还是信的。

T3

被空间限制误导了，想了半天bitset，还想了半天建两个自动机一块跑。

不难发现建两个自动机一起匹配毫无前途。。。

目前会两种做法，好像还有奇怪哈希？

1. 发现如果将字符哈希掉再进行替换相当于加一个值再减一个值，那我们显然是可以提前把 \(hs1-hs2\) 的值预处理出来，在fail树上查符合条件的值，主席树即可。

2. 发现 s1,s2可以分别表示为 $ ABC,ADC $ ,同理t1,t2可以表示为 $ EFG，EHG $，能发现替换成功必须满足 $ B=F , D=H $,且A是E的后缀，C是G的前缀。
   把两种串分别压成 $ A|BD|C \ \ ,E|FH|G$ 跑多模匹配即可。

T4

考场上真没给T4 时间，必须练速度了。

一种贡献延后的trick。

考虑一个人能否被招聘成功只与他和前面拒绝几个人的大小恭喜有关。

我们仍然在 \(c_p==j\) 时加入贡献。

设计状态 $ f_{i\ ,\ j\ ,\ k}$ 表示已经填到了第i个位置，拒绝了j个人，之前填的位置里有k个满足 \(c_p > j\)

考虑转移，这里只列举 \(s_{i+1}==1\)：

$c >j $ ,只需要在后面随便选一个就行，因为是贡献延后，这里不乘系数:

\[ f_{i+1,j,k+1} \gets f_{i,j,k} \]

$c \le j $ ,此时j推到了j+1,我们这时就要处理贡献了，这里需要枚举一下前面钦定的数量

\[f_{i+1,j+1,k-z} \gets f_{i,j,k} \times {k \choose z} { cnt_{j+1} \choose z} \times z! \times (s_j-(i-k)) \]