Codeforces 1234F Yet Another Substring Reverse
题目链接
https://codeforces.com/contest/1234/problem/F
题目大意
给你一个字符串，你可以选择一个连续子串并将其反转。问反转后的字符串中不出现相同字符的连续子串的长度最大为多少。
题目分析
由于字符集仅有 20 个字符，因此可以先预处理出来所有满足要求的子串处理出来。因为每个字符只出现一次，所以可以使用二进制来表示所有的子串。
考虑定义 f[S] 为由 S 字符集构成的最大连续子串的长度，显然可以非常容易的 DP 出来。
由于还可以反转，因此需要考虑合并集合。注意到，因为都是连续不重复字符的子串，因此如果两个子串没有字符交集那么一定不会相交。因此可以直接枚举集合然后和其相反的集合，那么一定可以构造出来这两个集合的字符所构成的子串。
枚举所有的集合后取最大值就可以得到答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char str[maxn];
int f[(1 << 21)];
int n;
int main(){
int i, j;
scanf("%s", &str[1]);
str[0] = '0';
n = strlen(str) - 1;
for(i=1;i<=n;i++){
int mask = 0;
for(j=i;j>0;j--){
int x = str[j] - 'a';
if((mask >> x) & 1)break;
mask |= (1 << x);
f[mask] = i - j + 1;
}
}
for(i=0;i<(1<<20);i++){
for(j=0;j<20;j++){
if((i >> j) & 1){
f[i] = max(f[i], f[i ^ (1 << j)]);
}
}
}
int ans = 0;
for(i=0;i<(1<<20);i++){
ans = max(ans, f[i] + f[(~i) & ((1 << 20) - 1)]);
}
printf("%d\n", ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char str[maxn];
int f[(1 << 21)];
int n;
int main(){
int i, j;
scanf("%s", &str[1]);
str[0] = '0';
n = strlen(str) - 1;
for(i=1;i<=n;i++){
int mask = 0;
for(j=i;j>0;j--){
int x = str[j] - 'a';
if((mask >> x) & 1)break;
mask |= (1 << x);
f[mask] = i - j + 1;
}
}
for(i=0;i<(1<<20);i++){
for(j=0;j<20;j++){
if((i >> j) & 1){
f[i] = max(f[i], f[i ^ (1 << j)]);
}
}
}
int ans = 0;
for(i=0;i<(1<<20);i++){
ans = max(ans, f[i] + f[(~i) & ((1 << 20) - 1)]);
}
printf("%d\n", ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char str[maxn];
int f[(1 << 21)];
int n;
int main(){
int i, j;
scanf("%s", &str[1]);
str[0] = '0';
n = strlen(str) - 1;
for(i=1;i<=n;i++){
int mask = 0;
for(j=i;j>0;j--){
int x = str[j] - 'a';
if((mask >> x) & 1)break;
mask |= (1 << x);
f[mask] = i - j + 1;
}
}
for(i=0;i<(1<<20);i++){
for(j=0;j<20;j++){
if((i >> j) & 1){
f[i] = max(f[i], f[i ^ (1 << j)]);
}
}
}
int ans = 0;
for(i=0;i<(1<<20);i++){
ans = max(ans, f[i] + f[(~i) & ((1 << 20) - 1)]);
}
printf("%d\n", ans);
return 0;
}