当前位置 : 主页 > 网页制作 > css >

Codeforces Round #590 (Div. 3) F

来源:互联网 收集:自由互联 发布时间:2021-06-13
传送门 题意: 给出一个只含前 \(20\) 个字符的字符串,现在可以选择一段区间进行翻转,问区间中字符各不相同时,最长长度为多少。 思路: 首先,容易将题意转换为选择两个字符各

传送门

题意:
给出一个只含前\(20\)个字符的字符串,现在可以选择一段区间进行翻转,问区间中字符各不相同时,最长长度为多少。

思路:

  • 首先,容易将题意转换为选择两个字符各不相同的区间,然后长度相加取最大;
  • 注意到字符串中满足条件的区间长度不超过\(20*n\),那么处理出所有区间,现在任务即为找到两个区间,其字符各不想同,且长度和最大;
  • 因为最多\(20\)个字符,将满足条件的区间转换为二进制数,任务转换为找到两个数\(a_i,a_j\)满足\(a_i\&a_j=0\)且二进制为\(1\)的个数和最大;
  • 构造\(b\)数组,且\(b_i\)\(a_i\)按位取反后的值,之后问题转换为子集问题,对于每一个\(state\),我们找到子集中\(a_i\)二进制\(1\)个数的最大值,之后用\(a_i,b_i\)更新答案即可。
  • 直接枚举子集复杂度为\(3^n\),可能会\(T\),那么\(dp\)优化一下就行(即高维前缀和,似乎也叫\(sos(sum\ of\ subset)\ dp\)

其实只要发现满足条件的区间不超过\(20*n\)个,之后的思路就比较自然了,最后的\(dp\)优化也要有知识储备才出得来。
挺不错的一个题。
代码如下:

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1666666;
 
char s[N];
int n;
int a[N], b[N];
 
void run() {
    memset(b, -1, sizeof(b));
    cin >> s + 1;
    n = strlen(s + 1);
    int lim = (1 << 20) - 1;
    for(int i = 1; i <= n; i++) {
        int x = 0, c = 0;
        for(int j = i; j <= n; j++) {
            int bit = s[j] - 'a';
            if(x >> bit & 1) break;
            x |= (1 << bit); ++c;
            a[x] = c; b[lim ^ x] = c;
        }
    }
    for(int j = 0; j < 20; j++) {
        for(int i = 0; i < lim; i++) {
            if(i >> j & 1) a[i] = max(a[i ^ (1 << j)], a[i]);
        }
    }
    int ans = 0;
    for(int i = 0; i < lim; i++) {
        if(b[i] >= 0) {
            ans = max(ans, a[i] + b[i]);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    run();
    return 0;
}
网友评论