一些感想
感觉最近很不在状态，整场比赛不知道在干什么... 连 \(\rm C\) 这么水的暴力也没看出来...
真的应该改改自己想完就开码的坏习惯，不能因为是虚拟赛就这么随意。
\(\text{E - Stringforces}\)
解法
\(k\le 17\)，我们考虑状压。一个基本的转化是二分最大值 \(x\)，那么就只用检查每种字母是否均有长度为 \(x\) 的段。
令 \(dp_s\) 为满足的字母集合为 \(s\) 需要的最短前缀。考虑转移，需要计算在位置 \(i\) 之后构造出字母 \(j\) 的长度为 \(x\) 的 最靠前 段的右端点。
直接在 \(dp_s\) 转移时计算此信息会导致复杂度飙升，其实可以直接预处理，令它为 \(pos_{i,j}\)。
对于 \(pos_{i,j}\) 的转移，显然如果 \([i+1,i+x]\) 中没有其他字母就可以更新为 \(i+x\)，否则直接继承 \(pos_{i+1,j}\)。
关于判定 \([i+1,i+x]\) 中是否有其他字母，可以将字母正反都枚举一遍，具体可以看看代码；还可以直接对每个字母做一个出现次数的后缀和，再统计所有字母出现次数后缀和。反正都是 \(\mathcal O(nk)\) 的。
代码
#include <cstdio>
#include <iostream>
using namespace std;
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>‘9‘||s<‘0‘) if(s==‘-‘) f=-1;
while(s>=‘0‘&&s<=‘9‘) x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar(‘-‘),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=2e5+5;
int n,k,pos[maxn][18];
int dp[1<<17],las[18];
char s[maxn];
bool ok(int mid) {
for(int i=0;i<k;++i)
las[i]=n+1,
pos[n][i]=n+1;
for(int i=n-1;i>=0;--i) {
if(s[i]^‘?‘)
las[s[i]-‘a‘]=i+1;
int cur=n+1;
for(int j=0;j<k;++j) {
pos[i][j]=(i+mid<cur?i+mid:pos[i+1][j]);
cur=min(cur,las[j]);
}
cur=n+1;
for(int j=k-1;j>=0;--j) {
if(i+mid>=cur)
pos[i][j]=pos[i+1][j];
cur=min(cur,las[j]);
}
}
for(int s=0;s<(1<<k);++s) dp[s]=n+1;
dp[0]=0;
for(int s=0;s<(1<<k);++s)
if(dp[s]<n)
for(int i=0;i<k;++i)
if(!(s>>i&1))
dp[s|(1<<i)]=min(dp[s|(1<<i)],pos[dp[s]][i]);
return dp[(1<<k)-1]<=n;
}
int main() {
n=read(9),k=read(9);
scanf("%s",s);
int l=0,r=n,mid;
while(l^r) {
mid=l+r+1>>1;
if(ok(mid))
l=mid;
else r=mid-1;
}
print(l,‘\n‘);
return 0;
}