E - Stringforces
题目描述
给你一个包含?和前
k
k
k 个小写字母的字符串
s
s
s ，你需要把每个?替换为前
k
k
k 个小写字母中的一个，使得字符串
s
s
s 的
v
a
l
val
val 最大。
定义
f
i
f_i
fi 表示字符串
s
s
s 中最长的全由第
i
i
i 个字母组成的子串的长度，
v
a
l
=
min
1
≤
i
≤
k
f
i
val=\min_{1\le i\le k}f_i
val=1≤i≤kminfi
数据范围与提示
1 ≤ n ≤ 2 ⋅ 1 0 5 , 1 ≤ k ≤ 17 1\le n\le 2\cdot 10^5,1\le k\le 17 1≤n≤2⋅105,1≤k≤17 。
前言
这题想到二分和状压就跑路去做F了，没想到从正解门前溜过去。
思路
这题一看 k ≤ 17 k\le 17 k≤17 ，立马想到状态压缩。
由于子串长度不确定，又同时有取 max \max max 和取 min \min min ，不好直接想，但是显然如果 v a l val val 取不到 a a a ，那么也肯定取不到 a + 1 a+1 a+1 ，满足单调性，所以考虑二分答案。
二分答案后， v a l val val 确定，也就是最小的 f i f_i fi 确定了，相当于满足所有的 f i f_i fi 必须大于等于 v a l val val 。 f i f_i fi 大于等于 v a l val val 当且仅当 s s s 中存在一个长度为 v a l val val 的全由第 i i i 个字符构成的子串，所以我们把问题转化为每种字符 i i i 找一个长度为 v a l val val 的区间，满足区间内的字符可以全为第 i i i 种字符，且这 k k k 个区间互不相交。
然后就可以在
c
h
e
c
k
check
check 内用状压DP：
d
p
[
x
]
dp[x]
dp[x] 表示已经解决需求的字符种类的状态为
x
x
x 时，所选区间的最右端点的最小值。那么先花个
O
(
n
k
)
O(nk)
O(nk) 的时间预处理一下
c
l
cl
cl 数组，其中
c
l
[
i
]
[
j
]
cl[i][j]
cl[i][j] 表示位置
i
i
i 后面，能为第
j
j
j 个字符选择的最近的区间的左端点，（设字符编号从0开始）那么转移为
d
p
[
x
]
=
min
(
1
<
<
i
)
∈
x
c
l
[
d
p
[
x
−
(
1
<
<
i
)
]
+
1
]
[
i
]
+
v
a
l
−
1
dp[x]=\min_{(1<<i)\in x}cl[dp[x-(1<<i)]+1][i]+val-1
dp[x]=(1<<i)∈xmincl[dp[x−(1<<i)]+1][i]+val−1
总共转移的复杂度是
O
(
k
⋅
2
k
)
O(k\cdot 2^k)
O(k⋅2k) ，所以总复杂度为
O
(
k
log
n
⋅
(
2
k
+
n
)
)
O(k\log n\cdot(2^k+n))
O(klogn⋅(2k+n)) 。
CF上没有更好的做法，这已经是最快的做法了。值得注意的是，我竟然在CF上看到了复杂度达 O ( k log n ⋅ 2 k ⋅ k 2 ⋅ log n ) O(k\log n\cdot 2^k\cdot \frac{k}{2}\cdot\log n) O(klogn⋅2k⋅2k⋅logn) 的AC代码，可见这题的数据非常友好。
代码
171ms rank1 代码
#include<cstdio>//JZM yyds!!!
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<map>
#define ll long long
#define MAXN 200005
#define MAXM 1000005
#define uns unsigned
#define INF 1e18
#define MOD 1000000007ll
#define lowbit(x) ((x)&(-(x)))
using namespace std;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
return f?x:-x;
}
int n,k,num[20],cl[MAXN][20];
int dp[MAXN];
char s[MAXN];
inline bool check(int m){
for(int i=0;i<k;i++)num[i]=0;
int tot=0;
for(int j=0;j<k;j++)cl[n+1][j]=cl[n+2][j]=n+1;
// printf("%d:\n",m);
for(int i=n;i>0;i--){
for(int j=0;j<k;j++)cl[i][j]=cl[i+1][j];
if(s[i]!='?'){
int c=s[i]-'a';
num[c]++;
if(num[c]==1)tot++;
}
if(i+m<=n&&s[i+m]!='?'){
int c=s[i+m]-'a';
num[c]--;
if(num[c]==0)tot--;
}
// printf(" %d %d\n",i,tot);
if(i+m>n+1)continue;
if(tot==1){
for(int j=0;j<k;j++)if(num[j]>0)cl[i][j]=i;
}
else if(tot==0){
for(int j=0;j<k;j++)cl[i][j]=i;
}
}
// for(int i=1;i<=n;i++)printf(" %d %d\n",cl[i][0],cl[i][1]);
int lim=(1<<k);
for(int s=1;s<lim;s++)dp[s]=n+1;
dp[0]=0;
for(int s=1;s<lim;s++)
for(int i=0;i<k;i++)
if((s>>i)&1){
int p=s^(1<<i);
dp[s]=min(dp[s],cl[dp[p]+1][i]+m-1);
}
return dp[lim-1]<=n;
}
signed main()
{
n=read(),k=read();
scanf("%s",s+1);
int l=0,r=n/k,mid;
while(l<r){
mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}