CF1234F Yet Another Substring Reverse

Description

给定一个字符串，可以任意翻转一个子串，求最终满足所有字符互不相同的子串的最大长度。

数据范围： \(n \le 10^6, \Sigma \le 20\)

Solution

由于被翻转子串的选择是任意的，我们可以将最终的子串看作两个原串的前缀的后缀的拼合。由于题目的各种性质，我们只需要考虑所有子串构成的字符集的所有可能状态，而与位置无关。

而字符集的状态依然要求不能有重复字符，因此对于每一个位置的字符，以它结尾的子串最多只有 \(\Sigma\) 个是合法的，因此我们状压并 \(O(n\Sigma)\) 扫一遍即可处理出字符集的所有状态。

原问题要求的是两个互斥的字符集 \(P,Q\) ，相当于把字符集划分为对立的两部分 \(A,B\)， 并取任意 \(P \subset A, Q \subset B\) 。我们 \(O(\Sigma 2^\Sigma)\) 预处理出子集前缀和，暴力枚举这种对立的划分，即枚举子集，即可在 \(O(2^\Sigma)\) 时间计算出答案。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 2100005;

int n,f[N],g[N];

char s[N];

int main() {

    scanf("%s",s+1);

    n=strlen(s+1);

    for(int i=1; i<=n; i++)

        s[i]-='a';

    vector <int> v,w;

    f[0]=1;

    v.push_back(0);

    for(int i=1; i<=n; i++) {

        for(int j=0; j<v.size(); j++)

            if((v[j]&(1<<s[i]))==0) {

                int p=v[j]|(1<<s[i]);

                f[p]=1;

                w.push_back(p);

            }

        swap(v,w);

        w.clear();

        v.push_back(0);

    }

    for(int i=0; i<1<<20; i++) {

        int cnt = 0;

        for(int j=0; j<20; j++)

            cnt += (i>>j)&1;

        if(f[i])

            g[i]=cnt;

        if(g[i])

            for(int j=0; j<20; j++)

                g[i|(1<<j)]=max(g[i|(1<<j)], g[i]);

    }

    int ans = 0;

    for(int i=0; i<1<<20; i++)

        ans=max(ans, g[i]+g[i^((1<<20)-1)]);

    cout<<ans<<endl;

}