CF1234F题解

· · 题解

趁它还是紫题,赶紧来写一发。

题目大意

给你一个字符串 s ，你可以对于 s 的一个子串进行翻转，问你翻转后 s 的子串中满足各个字符都不相同的最长子串的长度。

思路

首先，我们观察可以发现，对于翻转后合法的一个子串，其翻转前是两个子串，而且他们的字符互不相同，我们是不关心他们的前后顺序的。

因此，题意转化为求字符串 s 的两个字符没有交集子串拼接起来的最大长度是多少。

其次，我们观察到只有前 20 个字符，因此我们可以状压表示字符的出现，一个子串的状态的第 i 位为 1 表示这一个字符在这个子串中出现了。

于是，思路就有了，我们可以将 s 的每一个没有重复字符的子串的状态处理出来（我们将其中一个子串设为 s1 ），然后再找另一个子串（设为 s2 ），满足在 s1 和 s2 中出现的字符没有交集，求最大长度。

那么我们就可以运用高维前缀和解决。

但是，除了高维前缀和，我们还可以有另一种解释。在对 s1 的状态取反后，我们获得的另一个状态中表示的字符不一定都出现了，可能出现了它的一个子集，那也是符合题意的，于是我们可以枚举状态 i 的子集，找其中贡献最大的，但也不用全都枚举，因为会造成重复枚举，只需要枚举出现的字符的数量比 i 少 1 的状态 x 即可（因为 i 的其他子集 x 已经枚举过了）。

时间复杂度显然是可以接受的。

于是我们就做完了。

Code

//区间翻转后,子串的字符集不会发生改变,其实就是求两个子串拼一起的最大价值 
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
string s;
int len[1<<20]; 
int sum[1<<20]; //高维前缀和 
int ans;
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        int da=0;
        for(int j=i;j<s.size();j++)
        {
            if(da&(1<<(s[j]-'a')))  // 看似两层循环,实际上最多20 
            {
                break;
            }
            da|=(1ll<<(s[j]-'a'));
            len[da]=j-i+1;
        }
    }
    for(int i=0;i<(1ll<<20);i++)
    {
        sum[i]=len[i];
    }
    for(int i=0;i<(1ll<<20);i++)
    //高位前缀和,但还可以换个思路,实际上在统计答案时
    //我当前状态的取反后的状态不一定是满的,此时它的子集也是符合要求的,也要统计,可以结合下面的代码 
    {
        for(int j=0;j<20;j++)
        {
            if(i&(1ll<<j)) sum[i]=max(sum[i],sum[i^(1ll<<j)]);
        }
    }
    for(int i=0;i<(1<<20);i++)
    {
        ans=max(ans,sum[((1<<20)-1)^i]+sum[i]);
    }
    cout<<ans; 
    return 0;
}