2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111 [2021/07/15 20:47] 王智彪 |
2020-2021:teams:legal_string:王智彪:contest:educational_codeforces_round_111 [2021/07/16 00:47] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 再规定完美的数组为好数组且 $l≤a_{i}≤r$ 且它的 $F$ 函数值为所有好数组中最大的那个，给定 $n,l,r$ ，求完美数组的个数对 $10^{9}+7$ 取模。 $t$ 组数据， $1≤t≤1000,2≤n≤2·10^{5},-10^{9}≤l≤1,n≤r≤10^{9}$ | 再规定完美的数组为好数组且 $l≤a_{i}≤r$ 且它的 $F$ 函数值为所有好数组中最大的那个，给定 $n,l,r$ ，求完美数组的个数对 $10^{9}+7$ 取模。 $t$ 组数据， $1≤t≤1000,2≤n≤2·10^{5},-10^{9}≤l≤1,n≤r≤10^{9}$ | ||
| - | 不难发现对于给定的 $n$ ，最大的 $F$ 值应为 ${\frac n^{2} 4}$ 。 | + | 不难发现对于给定的 $n$ ，最大的 $F$ 值应为 ${\frac {n^2} 4}$ 。 |
| - | 首先证明其为上界，因为 $a_{i} != i$ ，所以对于任意一个数，要么它变大了要么它变小了，假设有 $x$ 个变大的，则有 $n-x$ 个变小的，就算所有的大+小都正好和原来的下标和一样，也只有 $x×(n-x)$ 对，可以证明无论 $n$ 是奇数还是偶数，这个值都等于 ${\frac n^2 4}$ ，故为上界。 | + | 首先证明其为上界，因为 $a_{i} != i$ ，所以对于任意一个数，要么它变大了要么它变小了，假设有 $x$ 个变大的，则有 $n-x$ 个变小的，就算所有的大+小都正好和原来的下标和一样，也只有 $x×(n-x)$ 对，可以证明无论 $n$ 是奇数还是偶数，这个值都等于 ${\frac {n^2} 4}$ ，故为上界。 |
| 而构造是显而易见的，将这个数组分成两组（如果是奇数就分成差为1的两组），一组同时加 $1$ ，另一组同时减 $1$ 即可，注意 $n$ 要分在减的那组， $1$ 要分在加的那组，这样一定保证所有的数变化后依然在 $[1,n]$ 范围内，又由题目的 $l,r$ 的范围知这样一定满足题意。 | 而构造是显而易见的，将这个数组分成两组（如果是奇数就分成差为1的两组），一组同时加 $1$ ，另一组同时减 $1$ 即可，注意 $n$ 要分在减的那组， $1$ 要分在加的那组，这样一定保证所有的数变化后依然在 $[1,n]$ 范围内，又由题目的 $l,r$ 的范围知这样一定满足题意。 | ||
| 行 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.1626353264.txt.gz · 最后更改: 2021/07/15 20:47 由 王智彪
