https://codeforces.com/contest/1234/problem/F
https://codeforces.com/blog/entry/70233
https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/11620068.html
先考虑它的一个子问题：给定一个字符串，求它的所有连续不相同子串。
之前做过求最大子序列和，思想上差不多，一个指针记录起点，另一个指针不断右移直到碰到出现过的字符，把起点的指针跳到第一次出现该字符的位置，直到起点指针跑遍字符串为止。时间复杂度：（因为终点指针最多跳动20次就要更改起点指针了）。
对于原问题，因为对于两个不相邻的子串，总可以翻转第一个子串的末尾到第二个子串的末尾，使得第二个子串能连在第一个子串后面，故翻转后的连续不相同子串长度的最大值为翻转前两个不相交连续不相同子串长之和的最大值。
记，
为所有连续不相同子串构成的集合。枚举
的所有子集
，若存在一个连续不相同子串，它的所有字母和
中的字母相同，则枚举
关于
的补集的所有子集；如果存在一个子集
，它和另一个连续不相同子串的所有字母相同，说明
可能为答案。枚举所有的
和
并求答案的最大值即可，这样做枚举了两次子集，时间复杂度为
，而
，会超时，必须想办法把一个
去掉。
答案说：对于确定的，如果能找到
的最大值
，则直接把
作为可能的答案就行了，不用枚举
。如果某个集合
就是由一个连续不相同子串构成的，那么
，否则问题转化为求所有
的
的最大值，这就变成了dp问题。由于状态暴多而且是2的多少次方，可以用二进制位来保存状态。
正常的位运算实现：
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
cin>>s;
vector<int> dp(1<<20); //1<<20太大，普通的数组会爆掉
int len=s.size();
for(int i=0;i<len;i++){
bool used[20]={0}; //这样做没问题，循环一次新建一个数组
int mask=0;
for(int j=0;i+j<len;j++){
if(used[s[i+j]-'a']) break;
used[s[i+j]-'a']=true;
mask|=1<<(s[i+j]-'a'); //把mask中代表s[i+j]的二进制位设成1
dp[mask]=__builtin_popcount(mask); //求mask中1的个数，即字母数
}
}
for(int mask=0;mask<(1<<20);mask++){
for(int pos=0;pos<20;pos++){
if((mask>>pos)&1) //如果mask的第pos位是1
dp[mask]=max(dp[mask],dp[mask^(1<<pos)]); //就把这一位去掉再求最大值
}
}
int ans=0;
for(int mask=0;mask<(1<<20);mask++){
if(dp[mask]==__builtin_popcount(mask)){ //如果mask是连续不相同子串
int comp=~mask&((1<<20)-1); //求mask的补集，要注意把前面的1去掉
ans=max(ans,dp[mask]+dp[comp]); //计算答案
}
}
cout<<ans<<endl;
return 0;
}
答案用了一个神奇的函数：
__builtin_popcount(n)：返回n的二进制位中的1的个数，可以用于枚举，也可以用来判断一个数是不是2的幂，此函数在状压dp中特别有用。
还有这些：
__builtin_parity(n)：判断n二进制位中1的个数是否为奇数，奇数返回1，偶数返回0。
__builtin_ffs(n)：返回n的二进制位中从后往前数第一个1的位置（从1开始计数），同时也是从后往前数0的个数加1。
__builtin_clz(n)：返回n从最高位开始连续0的个数。
__builtin_ctz(n)：返回n从最低位开始连续0的个数，可以用来算lowbit。
位运算的几个操作：
n|=(1<<x) 把n的第x位设成1。
n&=(0<<x) 把n的第x为设成0。
(n>>x)&1 判断n的第x位是否为1。
~n&((1<<x)-1) 将n的低x位取反，其余位不变。
