前言：今后可能會考慮在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 $ ,只需要在后面隨便選一個就行，因為是貢獻延后，這里不乘系數:

$c \le j $ ,此時j推到了j+1,我們這時就要處理貢獻了，這里需要枚舉一下前面欽定的數量