Yet Another Substring Reverse

Posted on | Post modified:

一道有趣的题目

题意：

现在有一个字符串 $s$（$1 \leq |s| \leq 10^6$）,现在选择一个区间$[l,r]$，反转一次或者不反转。若某区间的字母各不相同，则该区间为完美区间。你要做的就是执行完操作后使完美区间的长度最大。（整个字符串的字母种类数不超过$20$）

题解:

这个问题可以转换为寻找两个不相交的完美区间使得他们的长度和最大。

首先枚举所有的完美区间，复杂度为$O(n \cdot siz)$,$siz$为字符种类数。

对于每个完美区间，用二进制形式来表示，若第$i$个字母存在，则第$i$位为$1$，如$abcf$即可表示为：

接下来令$dp_{mask}$代表$mask$所有子集的长度的最大值。这个过程可以采用二进制枚举子集的方式进行$dp$。复杂度$O(2^{siz} \cdot {siz})$

接下来其实就是找两个不相交的状态$mask1$和$mask2$使得$dp_{mask1}+dp_{mask2}$最大化，枚举$mask1$,$mask2$其实就是$mask1$按位取反。枚举更新答案即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>

using namespace std;
int dp[1<<21];//dp[mask]表示mask所有子状态的最大值
int cal(int x){
    int ans=0;
    while(x){
        ans+=x%2;
        x/=2;
    }
    return ans;
}
int main(){
    string s;
    cin>>s;
    int l=(int)s.length();
    memset(dp,0,sizeof(dp));
    for(int i=0;i<l;i++){//枚举s[i:j]满足s[i:j]各个字母不相同
        bool vis[20];
        memset(vis,0,sizeof(vis));
        int mask=0;
        for(int j=0;i+j<l;j++){
            if(vis[s[i+j]-'a']) break;
            vis[s[i+j]-'a']=1;
            mask|=(1<<(s[i+j]-'a'));
            dp[mask]=cal(mask);
            //cout<<mask<<' '<<dp[mask]<<endl;
        }
    }
    for(int mask=0;mask<(1<<20);mask++){
        for(int j=0;j<20;j++){
            if((mask>>j)&1){
                dp[mask]=max(dp[mask],dp[mask^(1<<j)]);//枚举子集更新最大值
                //cout<<mask<<' '<<dp[mask]<<endl;
            }
        }
    }
    int ans=0;
    for(int mask=0;mask<(1<<20);mask++){
        if(dp[mask]==cal(mask)){
            int now=~mask&((1<<20)-1);
            //cout<<mask<<' '<<now<<endl;
            ans=max(ans,dp[mask]+dp[now]);
        }
    }
    cout<<ans<<endl;
    return 0;
}