云落碎碎念

1. 題面翻譯取自 luogu，本蒟蒻也會安置原題鏈接
2. 不保證文章中不出現“顯然”或者“注意到”，可能會出現“易證”
3. 有寫錯的地方歡迎各位神犇指正

前言

你在我的時間軸上，是一段有后效性的前綴

CF204A

題解

題目傳送門

前綴差分，直接做

細節處理

注意最高位不要溢出

CF204B

題解

題目傳送門

考慮對顏色開個桶，對于所有有能力成為絕對眾數的顏色，統計答案

細節處理

正反面顏色相同的部分在桶中只計算一次

CF204C

題解

題目傳送門

披著字符串題面的 DP 題

我們枚舉 \(i,j\)，并欽定 \(x_i=y_j\)，統計哪些子串會給出 \(x_i=y_j\) 的貢獻，形式化表示出來，有：

這玩意是 \(O(n^2)\) 的，然而可以維護前綴桶和后綴桶，即記錄 \(pre_{i,c}\) 表示前綴 \([1,i]\) 中所有滿足 \(x_i=c\) 的 \(i\) 的和，\(suf\) 同理

優化一下就 \(O(n)\) 了

細節處理

又是被 2000 分薄紗的一天

CF204D

題解

題目傳送門

簡單 DP，要是 NOIP 或者 CSP 出這種題就可以笑出來了

記 \(f_i\) 表示第 \([i-k+1,i]\) 為第一次出現連續的 B 的方案數

顯然 \([i-k+1,i]\) 的填法已經固定，所以考慮前綴 \([1,i-k]\) 的填法

正難則反，直接用隨便填的方案數刨去在前綴已經合法的。總方案數記為 \(tot_i\)，已經合法的記為 \(g_i\)，有轉移

其中 \([s_i = \texttt{X}]\) 表示字符串的第 \(i\) 位是否為字符 X

而 \(f\) 的轉移如果是簡單的 \(f_i=tot_{i-k} - g_{i-k}\) 就 WA 了

因為你還得保證對于 \(\forall j \in [i-k+1,i-1] ,\ s[j-k+1...j]\) 不是全 B

所以還需要刨去上述的方案，即 \(\sum_{j=i-k+1}^{i-1} f_j\)，結合前面的分析，\(f\) 的轉移形如

前綴和優化一下可以做到線性，對于 W 來說，反著做一遍類似的事情就可以了

答案也是好維護滴！

細節處理

感覺沒什么，需要什么信息就記錄，然后跟著 \(f\) 轉移就好了

CF204E

題解

題目傳送門

無聊題，廣姓算法加線段樹合并

細節處理

嘖

后記

考慮時光倒流，我可以維護你出現的時間戳

完結撒花！