題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串，只包含前 $k$ 個小寫字母以及通配符 $?$，現在可以將通配符替換成任意的前 $k$ 個字母中的一個。設 $f[i]$ 為第 $i$ 個字母在字符串中，最長的連續子段的長度，現在要求所有 $f[i]$ 中最小值的最大值

題目分析：讀完題一下子根據復雜度把正解分析出來了，可是怎么也沒辦法往 $dp$ 上去靠。因為 $k\le 17$，又因為 $2^{17}\approx 2e5$，所以不難想到二分+狀壓dp，時間復雜度剛好是 $nlo{g}^{2}n$ 的

這個題更像是縫合怪，里面的模型之前都做過類似的題目，但是結合起來就不會分析了，可以參考：

CodeForces - 1303E

中石油訓練賽 - Watch Later

看完上面兩個題再回過頭來看這個題，可能會簡單很多。

首先題目要求最小值的最大值，不難想到二分，這個題的重點是如何去 $check$。

因為通過復雜度分析出來是狀壓dp了，我個人對狀壓dp的理解是，狀壓dp就是全排列問題的一種優化，所以狀壓dp可以解決的問題，全排列暴力枚舉肯定也是可以解決的。所以先將問題簡化，如果本題放開全排列，該如何去做呢？

全排列的本質是確定了 $n$ 的物品的一種順序，在 $check$ 函數中確定了順序后，該怎么去做呢。這里需要想到的一個點是，我們確定下來的這個順序，應該轉換為在字符串中的順序。舉個例子，假設二分的長度為 $len=4$，$k=3$，也就是說 “aaaa”,“bbbb”,“cccc” 這三個字符串應該作為子串出現在原串中，而我們確定的順序，就是從頭開始遍歷字符串，依次匹配到的順序。更具體的說，假如我們全排列枚舉的順序是 $3,1,2$，那么在原串中，應該先出現 “cccc”，再出現 “aaaa”，最后再出現 “bbbb”

所以對于某個全排列確定的順序來說，我們貪心去匹配一定是最優的，可以想象有一個 $end$ 指針一直在原串中后移，最后 $check=true$ 的條件一定是 $end$ 指針仍然在原串中

這個順序有什么用呢？類比于上面第一個題目的模型 CodeForces - 1303E，不難設計出狀壓dp的狀態了：$dp[i]$ 代表的是，滿足狀態 $i$ 下，$end$ 指針的最小值，如果 $dp[(1<<k)?1]$ 代表的位置仍在原串中，說明 $check=true$

轉移的話預處理一個序列自動機輔助轉移就可以了

其實這個題是一道不算難的題目，真的就是很多經典模型拼湊起來的，感覺自己分析題目的能力還是欠缺很多

代碼：

// Problem: E. Stringforces // Contest: Codeforces - Educational Codeforces Round 111 (Rated for Div. 2) // URL: https://codeforces.com/contest/1550/problem/E // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; char s[N]; int n,k,nt[N][17],dp[(1<<17)+100]; bool check(int len) {for(int i=0;i<17;i++) {nt[n+2][i]=nt[n+1][i]=n+2;}for(int c=0;c<k;c++) {int l=0;for(int i=n;i>=1;i--) {if(s[i]=='?'||s[i]-'a'==c) {l++;} else {l=0;}if(l>=len) {nt[i][c]=i+len;} else {nt[i][c]=nt[i+1][c];}}}for(int i=0;i<1<<k;i++) {dp[i]=n+2;}dp[0]=1;for(int i=0;i<1<<k;i++) {for(int j=0;j<k;j++) {if(((i>>j)&1)==0) {dp[i^(1<<j)]=min(dp[i^(1<<j)],nt[dp[i]][j]);}}}return dp[(1<<k)-1]<=n+1; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(k);scanf("%s",s+1);int l=0,r=n,ans=-1;while(l<=r) {int mid=(l+r)>>1;if(check(mid)) {ans=mid;l=mid+1;} else {r=mid-1;}}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1550E Stringforces(二分+状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。