2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111 [2021/07/15 20:49] 王智彪 |
2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111 [2021/07/16 00:47] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 101: | 行 101: | ||
| } | } | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | ===== E. [Stringforces] ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定字符串长度 $n$ 以及，字符集大小 $k$ ，其中字符集从字符 $a$ 开始到字符 $a+k-1$ 。接下来给定字符串，其中一些已经填好了，没填的用 $?$ 表示，问最少的长度，使得存在一种方案将 $?$ 全换成字符集的字符，能使得对所有字符集中的字符，都有连续的这些长度的字符串。 | ||
| + | |||
| + | 答案有单调性，显然要二分解决，下界 $0$ ，上界 $n$ 。难点是如何写 $check$ 函数。 | ||
| + | |||
| + | 我们预处理出每个位置对于每个字符而言下一个合法位置，之后用状压的思想，处理每个状态，如果有位置更优的情况则选之，最后二进制全是1的情况如果合法返回 $true$ 即可。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | int n,k,p[18][200010],flag[200010]; | ||
| + | char str[200010]; | ||
| + | bool check(int x) { | ||
| + | for(int i=0; i<k; i++)p[i][n+1]=n+1; | ||
| + | for(int i=0; i<k; i++) { | ||
| + | int lst=n+1; | ||
| + | for(int j=n; j; j--) { | ||
| + | if(str[j]!='?'&&str[j]!=i+'a')lst=j; | ||
| + | p[i][j]=p[i][j+1]; | ||
| + | if(lst-j>=x)p[i][j]=j+x-1; | ||
| + | } | ||
| + | } | ||
| + | for(int i=1; i<(1<<k); i++)flag[i]=n+1; | ||
| + | for(int i=1; i<(1<<k); i++){ | ||
| + | for(int j=0; j<k; j++){ | ||
| + | if(((1<<j)&i)&&(flag[i^(1<<j)]<=n)) flag[i]=min(flag[i],p[j][flag[i^(1<]+1]); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | |||
| + | return flag[(1<<k)-1]<=n; | ||
| + | |||
| + | } | ||
| + | int main() { | ||
| + | scanf("%d %d",&n,&k); | ||
| + | scanf("%s",str+1); | ||
| + | int l=0,r=n+1,ans=-1; | ||
| + | while(l<=r) { | ||
| + | int mid=(l+r)>>1; | ||
| + | if(check(mid)) { | ||
| + | l=mid+1; | ||
| + | ans=mid; | ||
| + | } else r=mid-1; | ||
| + | } | ||
| + | printf("%d\n",ans); | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/王智彪/contest/educational_codeforces_round_111.1626353342.txt.gz · 最后更改: 2021/07/15 20:49 由 王智彪
