CSP-S集训刷题记录
$ CSP.S $ 集訓刷題記錄：
$ By~wcwcwch $
一、字符串專題：
1. 【模板】$ manacher $ 算法
模型：
求出字符串 $ S $ 中所有回文串的位置及長度。
$ solution $ ：
個人理解：解決這類問題，回文串的對稱性質最重要。
于復雜度最關鍵的一句話： $ f[i]=min~(~r-i~,~f[~mid\times2-i~]~)~ $ （實現不同，邊界可能不一樣）
這個 $ min $ 函數左邊 $ r-i $ 是當前位置到它所屬于的回文串邊界的距離，右邊 $ mid\times 2 -1 $ 是它在所屬于的回文串的另一邊的對應位置。如果取左邊，那么我用當前位置擴展（會超出當前回文串邊界）于是必然能夠使 $ r $ 向右擴展；如果取右邊，我們發現由于回文串的對稱性，這個位置必然不能繼續向外擴展，因為他最開始向外擴展必然還是在當前回文串邊界內（否則 $ min $ 函數肯定取的左邊），而如果它能在當前回文串內擴展，它的對稱位置 $ mid\times 2 -1 $ 也能，而 $ f[~mid\times2-i~] $ 已是擴展最大值，與之矛盾。
總結一下，如果 $ min $ 函數取左邊，那么 $ r $ 一定能向右擴展；如果取右邊，那么復雜度為 $ 1 $ （常數）。于是復雜度為 $ r $ 的值域和 $ 1 $ 的次數，兩者都不超過 $ n $ ，于是復雜度為 $ O(2\times n) $ ，就算再加上與處理時加“#”號，也是常數而已。
2. 【模板】擴展 $ KMP $
模型：
有一個字符串 $ a $ ，要求輸出【 $ a $ 本身】和【 $ a $ 的每一個后綴】的最長公共前綴 。
$ solution $ ：
$ KMP $ 和 $ Manacher $ 思想的結合產物。不過個人更傾向于 $ Manacher $ 。因為他的計算方法和 $ Manacher $ 神似，都是在某一個位置先根據之前的結果得到一個初始的公共前綴長度，就是“回文串”變成了最長公共前綴，回文串的中心 $ mid $ 變成了最長公共前綴的左端點 $ l $ ，最后 $ min $ 函數長的不一樣了。
我們對于 $ a $ 處理出它【每一位開始的后綴】和【 $ a $ 本身】的最長公共前綴 $ f[i] $ 。注意我們要從第二位開始 ，因為 $ f[1]=|a| $ 很特殊。我們用 $ l $ 記錄已經遍歷過的 $ i $ 中 $ i+f[i] $ 最大的 $ i $ ，同時用 $ r $ 記錄 $ i+f[i] $ ，這兩者初始均為 $ 0 $ 。然后： $ f[i]=min(~r-i~,~f[i-l+1]~) $ ，這個計算初始值的式子和 $ Manacher $ 很像， $ i $ 處于一個公共前綴里，那么 $ i $ 后面的字母一定和 $ f[i-l+1] $ 后面的字母在 $ r-i $ 范圍內保持一致，于是直接拿來作為初始值即可。復雜度證明和上面 $ Manacher $ 一樣！
$ code $ ：
int n,m; int f[2000005]; string s,a;int main(){cin>>a; n=a.size();cin>>s; m=s.size();s=' '+s+'#'+a; n+=m+2; //加到一起rg l=0,r=0; f[1]=m; //第一個不管for(rg i=2;i<=n;++i){if(i<=r) f[i]=min(r-i,f[i-l+1]); //確定初始值while(s[f[i]+1]==s[i+f[i]]) ++f[i]; //向后擴展if(i+f[i]-1>r) l=i,r=i+f[i]-1; //更新l和r的值}for(rg i=1;i<=m;++i) printf("%d%c",f[i],i==m?'\n':' ');for(rg i=m+2;i<n;++i) printf("%d%c",f[i],i==n-1?'\n':' ');return 0; }3. $ LOJ~3095 $ ： $ Snoi~2019 $ 字符串
題意概括：
給一個長度為 $ n $ 的字符串 $ S $ ，記 $ S′_i $ 表示 $ S $ 刪去第 $ i $ 個字符后得到的字符串，輸出：\(( S′_1 , 1)...(S′_n , n)\) 的字典序排序結果。 $ n\leq 10^6 $
$ solution $ ：
我們仔細觀察題目，手算分析樣例，可以發現一個性質：
于是我們開一個雙端加入的數組，記錄最后的答案。期望復雜度： $ O(n) $
$ code $ ：
n=qr(); cin>>a; a=' '+a; a[n+1]=')'; //防出界rg l=0,r=n+1; //記錄雙端指針for(rg i=1;i<=n;++i){ rg j=i;while(a[i]==a[i+1])++i; //找到連續相同串的右端點if(a[i+1]<a[i]) for(rg k=j;k<=i;++k) s[++l]=k; //這一段都必然比后面的串小else for(rg k=i;k>=j;--k) s[--r]=k; //這一段都必然比后面的串大}for(rg i=1;i<=n;++i) printf("%d ",s[i]);4. 洛谷 $ P5446 $ ： $ THUPC~2018 $ 綠綠和串串
題意概括：
對于字符串 $ S $ ，定義運算 $ f(S) $ 為將 $ S $ 的前 $ |S|-1 $ 個字符倒序接在 $ S $ 后面形成的長為 $ 2|S|-1 $ 的新字符串。現給出字符串 $ T $ ，詢問有哪些串長度不超過 $ |T| $ 的串 $ S $ 經過若干次 $ f $ 運算后得到的串包含 $ T $ 作為前綴。$ 1 \le |T| \le 5 \times 10^6. $
$ solution $ ：
很糾結的一道題，調了好一會才發現思維不夠嚴謹，判斷出錯了。
首先我們不難發現這是一道與回文串有關的題目，我們可以發現如果 $ S $ 串中存在一個位置 $ i $ 使得它的最長回文串能到達 $ S $ 串的末尾，那么對 $ [1,i] $ 這一段字符進行 $ f(1,i) $ 的操作一定可以得到一個合法新字符串使 $ S $ 為其前綴。然后我們還可以發現如果將這些位置標記，如果 $ S $ 串中還有一些位置 $ i $ 使得從 $ i $ 擴展的回文串可以到達 $ S $ 串的第一個字符且這個回文串的末尾字符是被標記了的，那么這個位置也是合法的！因為只要進行多次 $ f $ 操作即可。
$ code $ ：
t=qr();while(t--){cin>>s; n=s.size(); s=' '+s; //讀入rg mid=0,r=0; s[0]='('; s[n+1]=')'; //設邊界for(rg i=1;i<=n;++i){ f[i]=0;if(i<r) f[i]=min(r-i,f[(mid<<1)-i]); //manacher尋找初值while(s[i-f[i]-1]==s[i+f[i]+1]) ++f[i]; //擴展if(i+f[i]>r) mid=i,r=i+f[i]; //更新} k[n]=1;for(rg i=n;i>=1;--i) //如果轉一次就合法，或者能夠連轉多次if(i+f[i]==n||(i-f[i]==1&&k[i+f[i]])) k[i]=1;for(rg i=1;i<=n;++i)if(k[i])printf("%d ",i),k[i]=0; //輸出+清零puts("");}5. 洛谷 $ P4503 $ ：$ CTSC~2014~$ 企鵝 $~QQ $
題意概括：
給出一個帶通配符的字符串 $ S $ ，通配符分兩種，一種可以匹配恰好一個字符，另一種可以匹配任意個（包括 $ 0 $ 個）字符。再給出 $ n $ 個串 $ T_i $ ，詢問 $ T_i $ 能否與 $ S $ 匹配。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符個數 $ \le 10. $
$ solution $ ：
總算搞了一道 $ Hash $ 題了，應該算是第一道仔細調了細節的代碼。對于 $ Hash $ 我們有單哈希和多哈希，根據元素信息的維數來看。但是個人還是喜歡單哈希里的 $ long~long $ ，效果和雙 $ int $ 哈希差不多。 $ long~long $ 好寫，跑的飛快，但是模數太大容易溢出；雙 $ int $ 哈希（一般用 $ STL:pair $ ），跑的不快，但是正確性高很多。
這道題我們可以采取暴力措施，因為只有一位可以不同，所以我們干脆枚舉這一位是哪一位，然后將每個字符串除開這一位的前綴和后綴相互比較，如果相同那么就是合法的一對。前綴和后綴的比較可以預處理 $ Hash $ 得到。
期望復雜度： $ O(m\times n\times logn) $
$ code $ ：
const ll mod=20190816170251; //紀念CCF關門的日子是個質數 //小常識：1e18+3和1e18+9都是質數很好記，998244353和998244853和993244853也是。ll ans; int n,m,k; ll q[30005]; ll f[30003][202]; //前綴hash ll s[30003][202]; //后綴hash char a[30005];int main(){n=qr(); m=qr(); k=qr();for(rg i=1;i<=n;++i){scanf("%s",a+1); //scanf讀入快一點 //107這個數不要太大，防溢出for(rg j=1;j<=m;++j) f[i][j]=(f[i][j-1]*107+a[j])%mod; //前綴hashfor(rg j=m;j>=1;--j) s[i][j]=(s[i][j+1]*107+a[j])%mod; //后綴hash} ll x=1; //模數不能太大，否則這里會炸掉for(rg i=1;i<=m;++i){ //每個位置分開做會快些，正確性也高一些for(rg j=1;j<=n;++j)q[j]=f[j][i-1]*x+s[j][i+1]; //前后合并sort(q+1,q+n+1);for(rg j=1,o=1;j<=n;j=++o){while(q[j]==q[o+1]) ++o; //找到連續一段相同的ans+=((ll)(o-j+1)*(o-j))>>1; //注意答案貢獻為C[x][2]，從一段中取一對} x=x*107%mod;}printf("%lld\n",ans);return 0; }6. 洛谷 $ P3167 $ ： $ CQOI~2014 $ 通配符匹配
題意概括：
給出一個帶通配符的字符串 $ S $ ，通配符分兩種，一種可以匹配恰好一個字符，另一種可以匹配任意個（包括 $ 0 $ 個）字符。再給出 $ n $ 個串 $ T_i $ ，詢問 $ T_i $ 能否與 $ S $ 匹配。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符個數 $ \le 10. $
$ solution $ ：
想法頗多，但實現艱巨的一道題，寫了一晚上加一上午。
講課時和 $ Itst $ 討論覺得是 $ AC $ 自動機，結果大鴿鴿一講是 $ Hash $ ，題解第一篇居然也是 $ Hash $ ？！但是 $ AC $ 自動機本就和 $ Hash $ 完成的東西一樣，都要求兩段子串是否相等， $ AC $ 自動機預處理， $ Hash $ 在線 $ O(1) $ 求，所以同出一源。
首先這道題的突破口是通配符無疑！因為數量太少，我們可以根據通配符劃分模式串，得到不多于 $ 10 $ 個模式串。然后我們可以考慮在給的 $ n $ 個串中找到這些模式串的位置，然后想辦法合并這些位置以判斷是否合法。想法是好的，實現起來卻十分殘酷，首先 $ AC $ 自動機找串復雜度 $ |S|^2 $ ，直接撲街；但是我們很快發現模式串不多，而且只需要知道其是否在某個位置出現，我們考慮狀壓，每次不暴力訪問，直接位運算（期望復雜度 $ O(|S|) $ ）。
然后我們發現實現這個匹配是非常難的。但是我們也可以發現匹配是線性的按順序的匹配，和動態規劃很像，于是我們考慮動態規劃，對每一個位置記錄他可以匹配完哪一個的模式串。然后我們對于每一個狀態（某一個位置是某一個模式串的末尾）可以根據這個模式串之前是哪一個通配符來轉移，如果是 $ ? $ 那么直接找到模式串開頭前一個位置，看它是否匹配了上一個模式串；如果是 $ * $ 就找之前所有狀態，是否有匹配了上一個模式串的位置（用前綴或（位運算）和）。利用狀壓我們可以直接位運算解決所有轉移。
$ code $ ：
#include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #include<vector> #include<queue> #include<map> #include<set>#define ll long long #define db double #define rg register intusing namespace std;int n,m,t; int s[10005]; int b[10005]; int mx[100005]; int f[100005]; int k[100005]; char a[100005];struct AC{int tt;int end[100005];int fail[100005];int son[100005][26];inline void add(int l,int r,int v){rg now=0,*to;for(rg i=l;i<=r;++i){to=&son[now][a[i]-'a'];if(*to)now=*to;else now=*to=++tt;}end[now]|=(1<<v); //將這個模式串編號狀壓到自動機里面}inline void failed(){queue<int> q;for(rg i=0;i<26;++i)if(son[0][i]){end[son[0][i]]|=end[0]; //fail樹的應用，這個位置的字符串包含哪些模式串q.push(son[0][i]);}rg *to,next;while(!q.empty()){rg i=q.front(); q.pop(); next=fail[i];for(rg j=0;j<26;++j){to=&son[i][j];if(*to){ q.push(*to);fail[*to]=son[next][j];end[*to]|=end[son[next][j]]; //fail樹的應用，這個位置的字符串包含哪些模式串}else *to=son[next][j];}}}inline void find(int l){ //找到文本串里每個位置對應哪些模式串末尾rg now=0; f[0]=end[now];for(rg i=1;i<=l;++i){now=son[now][a[i]-'a'];f[i]=end[now]; //這個位置是那些模式串的末尾}} }T;inline int qr(){register char ch; register bool sign=0; rg res=0;while(!isdigit(ch=getchar()))if(ch=='-')sign=1;while(isdigit(ch))res=res*10+(ch^48),ch=getchar();if(sign)return -res; else return res; }int main(){scanf("%s",a+1); m=strlen(a+1); a[++m]='s'; //最后加個字符是為了防通配符在末尾for(rg i=1,j=1,x=0;i<=m;i=++j){while(j<=m&&a[j]>='a'&&a[j]<='z')++j; //以通配符為界，劃分為若干模式串T.add(i,j-1,++t); s[(1<<t)]=x; b[(1<<t)]=j-i; //記錄上一個通配符是哪一種，以及串長if(j<=m&&a[j]=='?') x=1; else x=2; //辨別這個通配符是哪一種}T.failed(); rg n=qr();for(rg i=1;i<=n;++i){ //每個待匹配串都視為文本串，跑AC自動機scanf("%s",a+1); m=strlen(a+1);a[++m]='s'; T.find(m); k[0]=mx[0]=1; //預處理+初始化for(rg j=1;j<=m;++j) k[j]=mx[j]=0; //初始化for(rg j=0;j<=m;++j){for(rg x=f[j];x;x-=x&-x){ //這層循環的復雜度為通配符個數rg y=x&-x;if(s[y]==0) k[j]|=y&(k[j-b[y]]<<1); //如果之前沒有通配符if(s[y]==1) k[j]|=y&(k[j-b[y]-1]<<1); //上一個通配符是?就直接看前面對應位置是否可以匹配if(s[y]==2) k[j]|=y&(mx[j-b[y]]<<1); //上一個通配符是*就直接看全局，因為中間字符可消mx[j]|=k[j]; //這個對于*操作很重要，記錄這個位置之前的最高匹配度} mx[j+1]=mx[j]; //這個對于*操作很重要，記錄這個位置之前的最高匹配度}if(k[m]&(1<<t))puts("YES"); //看最后一位的匹配度是否達到最高else puts("NO");}return 0; }7. 洛谷 $ P3193 $ ： $ HNOI~2008~GT $ 考試
題意概括：
給一個數字串 $ S $ ，求有多少長度為 $ n $ 的數字串 $ T $ 不包含 $ S $ 作為子串。 $ 1 \le |S| \le 100, 1 \le n \le 10^9. $
$ solution $ ：
并沒有想象中（上一道題）的這么難，唯獨就是要寫嚴格 $ O(1) $ 的 $ kmp $ 算法。感覺比普通的還好寫一點。
首先我們求的串中必須不包含 $ S $ ，這個我們其實不難想到動態規劃。設 $ F[i][j] $ 表示已經構造到第 $ i $ 個位置，在末尾最多有 $ j $ 個位置和 $ S $ 的前 $ j $ 個位置一致。之所以這樣設狀態是因為我們構造合法串時只需要知道串后面的字符和 $ S $ 的匹配程度，這樣可以知道我們放下一個字符會不會使得一段后綴變為 $ S $ （任何一個子串都可以表示為一個前綴的后綴）。然后我們就需要轉移方程，這個其實就是一個 $ kmp $ 的過程。但是為了快速轉移我們需要知道在當前串后面加入某個字符會使匹配轉移到哪一個位置！這個需要用嚴格 $ O(1) $ 的 $ kmp $ 算法。再然后我們就可以將這個轉移過程用矩陣來完成，通過改變矩陣系數使得一次轉移等同一次乘法。然后快速冪。
$ code $ ：
int n,m,k; int nx[105]; int f[105][10]; char a[105];struct su{ //矩陣int s[101][101];inline void operator *=(const su &x){ //矩陣乘法su res;for(rg i=0;i<m;++i){for(rg j=0;j<m;++j){rg y=0;for(rg k=0;k<m;++k)y+=s[i][k]*x.s[k][j];res.s[i][j]=y%k; //有時候將取模放外面會快些}} *this=res;}inline su operator ^(int y){ //矩陣快速冪su res,x=*this;for(rg i=0;i<m;++i) res.s[i][i]=1;while(y){if(y&1)res*=x;x*=x; y>>=1;}return res;} }ans,xx;int main(){n=qr(); m=qr(); k=qr();scanf("%s",a+1);ans.s[0][0]=1;for(rg i=1;i<=m;++i){nx[i]=f[i-1][a[i]-'0']; //似乎比不嚴格的好寫？f[i-1][a[i]-'0']=i; //f[i][j]表示從這一位在后面加字符j會匹配到哪個位置for(rg j=0;j<=9;++j) //復雜度比一般kmp高一點f[i][j]=f[nx[i]][j]; //就是嚴格O(1)的kmp}for(rg i=0;i<m;++i)for(rg j=0;j<=9;++j)++xx.s[i][f[i][j]]; //加入矩陣系數ans*=xx^n; int tot=0; //矩陣快速冪for(rg i=0;i<m;++i)tot+=ans.s[0][i]; //統計所有不含所給串的串的個數printf("%d\n",tot%k);return 0; }8. 洛谷 $ P2414 $ $ NOI~2011 $ 阿貍的打字機
題意概括：
給你一棵 $ n $ 個節點的 $ Trie $ 樹， $ q $ 次詢問 $ Trie $ 樹上 $ x $ 節點代表的字符串在 $ y $ 節點代表的字符串中出現了多少次。
$ 1 \le n, q \le 10^6. $
$ solution $ ：
很難的一道題，可以說是很多算法的結合： $ AC $ 自動機， $ fail $ 樹， $ dfs $ 序，樹狀數組
首先是讀入，一般讀入肯定超時，因為放進 $ AC $ 自動機的字符串很多很長，但是他們很多前綴相同。于是根據題意模擬，我們在 $ trie $ 數上跑操作序列，只要記錄每一個節點的父親，就可以支持加入字符后的撤銷操作，然后打印操作直接在當前 $ trie $ 的節點處打標機即可（詳細見代碼）
然后是關于 $ fail $ 樹，我們對于每一個 $ fail $ 指針件一條反向邊，因為一個節點只有一個 $ fail $ 指針，得到的圖一定是棵有根樹。然后我們思考這棵樹的意義：（假設每個節點對應一個從根到這個節點的字符串）我們在普通情況下從某個節點（對應字符串 $ S $ ）沿 $ fail $ 指針跑，遍歷的字符串都是 $ S $ 的子串且是后綴！于是反過來，我們在 $ fail $ 樹上從某個節點（對應 $ S $ ）遍歷其子樹，遍歷到的字符串都一定包含 $ S $ 作為子串，且 $ S $ 是它們后綴！
然后我們還知道，一個子串一定可以表示成母串的前綴的后綴。于是如果我們要在 $ trie $ 上找 $ x $ 節點代表的字符串在 $ y $ 節點代表的字符串中出現了多少次，我們只需要將 $ y $ 字符串的每一個前綴對應節點（在 $ trie $ 上為到根鏈）都標記，然后在 $ fail $ 樹上的 $ x $ 好節點開始遍歷子樹，有多少節點被標記那么 $ x $ 節點代表的字符串在 $ y $ 節點代表的字符串中出現了多少次。
但是我們發現詢問很多，字符串長度很大。但是我們可以離線：因為字符串的所有前綴對應節點在 $ trie $ 上為一條到根的鏈，我們馬上回憶到一種題型（在 $ dfs $ 一棵樹時維護節點到根路徑的信息：在遍歷到某一節點時加入節點貢獻，在離開節點時刪掉節點貢獻）。再聯想一下我們需要知道 $ fail $ 的子樹信息和，我們就可以想到先找到樹的 $ dfs $ 序，用樹狀數組維護以 $ dfs $ 序為對應位置的數組，然后遍歷整棵 $ trie $ 樹，在遍歷到某一節點時給樹狀數組對應位置加一，在離開節點時減一。然后如果遍歷 $ trie $ 樹時，當前節點為詢問中的 $ y $ 字符串（所有前綴都以標記），就到樹狀數組里找到對應詢問 $ x $ 字符串對應位置的子樹和。
$ code $ ：
#include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #include<vector> #include<queue> #include<map> #include<set>#define ll long long #define db double #define rg register intusing namespace std;int tim; int n,m,tot; int a[100005]; int tr[100005]; int dfn[100005]; int low[100005]; int ans[100005];struct bian{int to,next; }b[1000005]; int tou[100005],top;struct lian{int to,res,id,next; }q[100005]; int hd[100005],len;struct AC{int tt;int fa[100005];int end[100005];int fail[100005];int son[100005][26];bool vis[100005][26];inline void add(const string &ch){rg now=0,*to,l=ch.size();for(rg i=0;i<l;++i){if(ch[i]>='a'&&ch[i]<='z'){to=&son[now][ch[i]-'a'];if(*to) now=*to; else *to=++tt,fa[*to]=now,now=*to;}if(ch[i]=='B') now=fa[now]; //額外計一個父親用來撤銷if(ch[i]=='P') a[++n]=now;}}inline void failed(){queue<int> q;for(rg i=0;i<26;++i){if(son[0][i]){fail[son[0][i]]=0;q.push(son[0][i]);}}rg *to,next;while(!q.empty()){rg i=q.front(); q.pop(); next=fail[i];for(rg j=0;j<26;++j){to=&son[i][j];if(*to){ q.push(*to);fail[*to]=son[next][j];}else vis[i][j]=1,*to=son[next][j];} //因為之后需要遍歷原始字典樹，所以需要一個vis數組記錄更改}}inline void get_eg(){for(rg i=1;i<=tt;++i){ rg x=fail[i],y=i;b[++top]=bian{y,tou[x]}; tou[x]=top;} //根據fail指針建fail樹的邊（反邊）} }ac;inline int qr(){register char ch; register bool sign=0; rg res=0;while(!isdigit(ch=getchar()))if(ch=='-')sign=1;while(isdigit(ch))res=res*10+(ch^48),ch=getchar();if(sign)return -res; else return res; }inline void add(int x,int v){for(;x<=tim;x+=x&-x) tr[x]+=v; } //需要注意樹狀數組的范圍inline int ask(int x){ rg res=0;for(;x;x-=x&-x) res+=tr[x];return res; }inline void yu(int i){dfn[i]=++tim;for(rg j=tou[i];j;j=b[j].next) yu(b[j].to);low[i]=tim; } //有向樹的dfs序，dfn和low記錄子樹區間inline void dfs(int i){add(dfn[i],1);for(rg j=hd[i];j;j=q[j].next){q[j].res=ask(low[q[j].to])-ask(dfn[q[j].to]-1);} //用鏈式前向星記錄詢問for(rg j=0;j<26;++j)if(ac.son[i][j]&&!ac.vis[i][j])dfs(ac.son[i][j]);add(dfn[i],-1); } //遍歷原始字典樹是因為每一個子串都是前綴的后綴 //字典樹遍歷所有前綴，而fail樹的dfs序與前綴的后綴有關int main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);string ch; getline(cin,ch); ac.add(ch);ac.failed(); ac.get_eg();yu(0); m=qr();for(rg i=1;i<=m;++i){rg x=a[qr()],y=a[qr()]; //將詢問具體到哪個字符串q[i]=lian{x,0,i,hd[y]}; hd[y]=i;} dfs(0);for(rg i=1;i<=m;++i) ans[q[i].id]=q[i].res;for(rg i=1;i<=m;++i) printf("%d\n",ans[i]);return 0; }9. 拯救紫萱學姐（試題）
題意概括：
定義對于兩個字符串 $ a $ 和 $ b $ ，如果 $ a $ 既是 $ b $ 的前綴也是 $ b $ 的后綴，那么稱 $ a $ 和 $ b $ 相似（空字符串和任何字符串相似）。一個字符串可以通過編輯變換成一個比它短而且與它相似的字符串，付出的代價為這兩個字符串的長度之差的平方。兩個字符串通過編輯而變為同一個字符串所花費的最小代價被稱為最短編輯距離。現給定一個字符串，你需要知道這個字符串的每一對前綴的最短編輯距離中的最大值是多少。
$ 1 \le |S| \le 10^6 $
$ solution $ ：
其實看到 $ a $ 既是 $ b $ 的前綴也是 $ b $ 的后綴時，就可以想到 $ kmp $ 思想。然后我們就會發現每一次編輯變換，就是沿著 $ kmp $ 的 $ next $ 數組往前跳。然后為了代價最小，我們肯定每次只跳一步。于是可以得到一個結論，對于兩個前綴他們沿 $ next $ 數組向前跳，第一個相同的位置所對應的前綴就是最終狀態（類似于將 $ next $ 數組反向連邊，在樹上跑 $ LCA $ ）。于是我們根據 $ next $ 數組從后往前遍歷，每次用當前位置跟新它 $ next[] $ 對應位置的最大代價，同時記錄答案。
$ code $ ：
ll ans; int n; int f[2000005]; ll s[2000005]; char a[2000005];int main(){scanf("%s",a+1); n=strlen(a+1); f[1]=0;for(rg i=2,j=0;i<=n;++i){ //kmpwhile(j&&a[i]!=a[j+1]) j=f[j];if(a[i]==a[j+1]) f[i]=++j; //next數組}for(rg i=n;i>=1;--i){ll j=f[i];ll x=(ll)(i-j)*(i-j); //記錄這一步的代價ans=max(ans,s[i]+x+s[j]); //更新答案s[j]=max(s[j],s[i]+x); //更新最大代價}printf("%lld\n",ans);return 0; }10. 洛谷 $ P3279 $ ： $ SCOI~2013 $ 密碼
題意概括：
給出一個長度為 $ n $ 的數組 $ {p_i} $ 和一個長度為 $ n $ 的數組 $ { q_i } $ ，分別表示以字符串中每個字符以及每兩個相鄰字符的間隙為中心的最長回文串長度。你需要根據給出的 $ { p_i } $ 和 $ {q_i} $ ，構造出一個滿足條件的字符串 $ S $ 。 $ n \le 10^6 $
$ solution $ ：
將 $ manacher $ 倒著做一遍，從前往后構造字符串。
然后貪心放小的字符即可。
$ code $ ：
int n; int a[1000005]; int b[1000005]; int s[1000005]; bool f[1000005][27];int main(){n=qr(); rg r=1; s[0]=26;for(rg i=1;i<=n;++i)a[i]=qr()>>1; //注意for(rg i=1;i<n;++i) b[i]=qr()>>1;for(rg i=1;i<=n;++i){if(i>=r){ ++r; //貪心放最小的for(rg j=0;j<26;++j)if(!f[i][j]){s[i]=j; break;}} rg x=i-a[i],y=i+a[i]; //記錄邊界f[y+1][s[x-1]]=1; //后面第一個字符不能等于回文串前一個字符while(r<=y) s[r]=s[i*2-r],++r;x=i-b[i]+1,y=i+b[i]; //同上f[y+1][s[x-1]]=1;while(r<=y) s[r]=s[i*2-r+1],++r;}for(rg i=1;i<=n;++i)printf("%c",s[i]+'a');puts("");return 0; }11. \(LOJ~6187~Odd\)
題意概括：
有一個 $ n $ 個數的數組 $ A $ 。求有多少個子區間，滿足每個區間里出現過的數都只出現了奇數次。
$ n \leq 2 \times 10^5, a_i \leq 10^6 $
$ solution $ ：
很難調的一道題，細節很多，小技巧也很多。（似乎上一道我這么認為的題也是分塊？）
我們考慮這道題的“奇偶”二字，說明本題很可能和狀壓、位運算什么的有關。考場上以為狀壓一下、求個前綴異或和、再開個桶就可以解決，奈何數據范圍大、“出現過”三字太毒瘤！但是仔細摸索一番我們不難想到 $ Hash $ 。因為我們要求每個區間，所以很直接的想法就是枚舉一個端點，尋找合法的另一個端點。而要快速知道一個區間內數的奇偶性，我們只能依靠異或操作，和后綴和（通過異或操作，使得合法區間一定滿足異或和為 $ 0 $ ，這樣根據右端點后綴異或和就能得到左端點后綴異或和，然后查存后綴異或和的桶子就好）
為了能夠方便異或操作，我們給每個值隨機一個大數，這樣正確性會很高（總共后綴異或和的數量為 $ n $ 個，值域為 $ 2^{63} $ ，安全）。然后我們枚舉右端點 $ r $ 并實時維護后綴（顯然右端點以右的點的后綴異或和不需要管，因為兩次異或得0）。因為合法區間的異或和為 $ 0 $ 而區間里的數又是奇數次，所以我們可以忽略每一個數的最后一個。于是當我們右端點向右移時假設下一個數為 $ v_i $ ，那么對于前面所有后綴，它肯定是里面等于 $ v $ 的書中最后一個。（假設上一個 $ v $ 出現位置為 $ j $ ）于是從 $ [1,j] $ 的所有后綴均需要異或 $ v $ （ $ [j+1,i] $ 不需要！）。然后因為右端點后綴為 $ 0 $ ，合法區間異或和為零，我們只需要知道前面有多少位置的后綴異或和為 $ 0 $ 即可！
然后講一下實現，首先我們需要隨機 $ rand $ 大數。然后我們需要記錄每一個位置的后綴異或和，并支持區間（某個前綴區間）異或修改，以及區間（前綴區間）查詢 $ 0 $ 的出現次數！因為值域很大所以我們得考慮 $ Hash $ 表查詢，對于區間修改查詢我們可以線段樹，但是線段樹被卡內存了，僅分塊還活著！然后對于區間異或我們可用類似線段樹的 $ lazytag $ 一樣給每個塊打標記！查詢這個塊時有多少0，就是查詢有多少 $ 0~xor~lazytag $ ！（分塊操作有點繞，要仔細分析）
注意 $ Hash $ 表因為分塊的緣故需要支持刪除和加入，我們要鏈表刪除，回收空間！不能暴力更改，空間會爆！
$ code $ ：
ll ans; int n,m; int a[200005]; ll b[1000005]; //隨機化權值 ll s[1000005]; //后綴（隨著右端點向右移，會變化的后綴） int t[1000005]; //上一個出現位置 int f[200005]; //分塊struct Hash{int tt,top;ll vv[505]; //數值int da[505]; //數量int to[505]; //鏈表指向int stc[505]; //我刪掉的位置（回收棧）int hd[2005];inline void add(ll x,int v){rg y=x%2003; rg i=0; //先Hash一下for(rg j=hd[y];j;i=j,j=to[j]){ //鏈式前向星存儲if(vv[j]==x){da[j]+=v; //更新權值if(!da[j]){stc[++top]=j; //計入回收棧if(!i) hd[y]=to[j]; //鏈表刪除else to[i]=to[j];} return ;}}i=top?stc[top--]:(++tt); //找到一個沒用的位置vv[i]=x; da[i]=1; to[i]=hd[y]; hd[y]=i; //存儲}inline int ask(ll x){for(rg j=hd[x%2003];j;j=to[j]) //鏈式前向星訪問if(vv[j]==x) return da[j];return 0;} }ha[505]; ll lz[505];int main(){srand(time(NULL)); //隨機化n=qr(); m=sqrt(n-1)+1; //分塊的大小for(rg i=1;i<=n;++i) f[i]=(i-1)/m+1; //這個下標在哪個塊for(rg i=1;i<=n;++i) a[i]=qr(),b[a[i]]=rand()+((ll)rand()<<31); //隨機權值for(rg i=1;i<=n;++i){ha[f[i]].add(0,1); //加入初始值if(t[a[i]]){ rg x=f[t[a[i]]]; ll v=b[a[i]]; //上一個出現的位置；該位置的隨機權值for(rg j=1;j<x;++j) lz[j]^=v; //塊上打標記for(rg j=m*(x-1)+1;j<=t[a[i]];++j)ha[x].add(s[j],-1), s[j]^=v, ha[x].add(s[j],1); //先取出，后修改，再加入} t[a[i]]=i; //該位置變為最后一個出現位置for(rg j=1;j<=f[i];++j) ans+=ha[j].ask(lz[j]); //詢問（直接訪問大塊就可以了！）}printf("%lld\n",ans);return 0; }二、搜索專題：
$ hncpc~2019E~Numbers $
題意概括：
給一個數字串 $ S $ ，求將其劃分成 $ [0,99] z$ 不含前導零且互不相同的數的方案數。
$ solution $ ：
湖南師范大學的 $ ACM $ 比賽題，沒有 $ source $ 。反正比較簡單，直接口糊。
爆搜，枚舉每個位置是否是小于 $ 10 $ 的位置，其他位置的數就確定了。于是邊搜索邊 $ check $ 就好了！
題意概括：
$ solution $ ：
$ code $ ：
三、圖論專題：
題意概括：
$ solution $ ：
$ code $ ：
四、數據結構專題：
題意概括：
$ solution $ ：
$ code $ ：
轉載于:https://www.cnblogs.com/812-xiao-wen/p/11600101.html
總結
以上是生活随笔為你收集整理的CSP-S集训刷题记录的全部內容，希望文章能夠幫你解決所遇到的問題。
