[codeforces1234F]Yet Another Substring Reverse

大致题意为将某个子串进行翻转后，使得不包含相同字符的字符子串长度最长。只能翻转一次或零次。

设一个子串的状态为包含字符的二进制。如子串为$abacd$，则状态为$00000000000000001111$。

根据分析可以得到，一个子串和另一个子串如果没有交集，则两个串可以经过一次翻转合并在一起。

例如：$abcdefga$，串$ab$和串$fg$，可以通过翻转$cdefg$变成$abgfedca$。

所以如果枚举一个状态，再枚举这个状态的补集的子集。就可以得到合法的状态。

但是枚举子集的复杂度太大，所以我们先处理出每种合法状态有多少个字符，然后再从小到大枚举一遍状态。这样可以得到每种状态的合法子集的最大值。

然后计算答案。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 int dp[ << ], vis[];

 string s;

 int main() {

     cin >> s;

     for (int i = ; i < s.size(); i++) {

         int mark = , cnt = ;

         memset(vis, , sizeof(vis));

         for (int j = i; j < s.size(); j++) {

             if (vis[s[j] - 'a'])

                 break;

             vis[s[j] - 'a'] = ;

             mark |= ( << (s[j] - 'a'));

             cnt++;

             dp[mark] = cnt;

         }

     }

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

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

             if (i & ( << j))

                 dp[i] = max(dp[i], dp[i ^ ( << j)]);

     int ans = ;

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

         ans = max(ans, dp[i] + dp[i ^ (( << ) - )]);

     printf("%d\n", ans);

 }

巴特西

[codeforces1234F]Yet Another Substring Reverse

最新文章

热门文章