CF1234F Yet Another Substring Reverse

CF1234F Yet Another Substring Reverse

状压 dp+高维前缀和

一个很显然的发现是最长子串长度不会超过字符集。那么如果没有这个操作，是很简单的，我们看看多了这个操作意味着什么。

对于一个子串，考虑一次翻转对它的影响。在它内部的翻转肯定是没有意义的；我们一定有一个操作能将任意子串与它接到一起，可以改变答案。那么我们就可以刻画这样一个翻转操作：将两个各个字符不相同的（不相交的）子串接在一起（因为发现各个字符不相同已经保证了两个子串不相交）。

考虑状压字符集，设 \(f_{s}\) 表示包含字符集 \(s\) 的子串是否存在，转移就枚举 \(s\) 补集的子集 \(f_{t}\)，合并即可。

复杂度 \(O(3^n)\)，考虑优化。发现瓶颈在于枚举补集的子集，而我们只需要其中的最大值，所欲可以 \(O(2^nn)\) 高维前缀和预处理每个集合的所有子集的最大值。

复杂度 \(O(2^nn)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10, S = 21;
int n, ans;
int f[1 << S], g[1 << S];
char s[N];
void solve() {
	std::cin >> s + 1;

	n = strlen(s + 1);
	for(int i = 1; i <= n; i++) {
		int sta = 0;
		for(int j = 0; i + j <= n; j++) {
			int c = s[i + j] - 'a';
			if((1 << c) & sta) break;
			sta |= (1 << c);
			f[sta] = std::max(f[sta], __builtin_popcount(sta));
		}
	}
	int lim = (1 << 20);
	for(int s = 0; s < lim; s++) g[s] = f[s];
	for(int i = 0; i <= 19; i++) {
		for(int s = 0; s < lim; s++) {
			if(s & (1 << i)) g[s] = std::max(g[s], g[s & (~(1 << i))]);
		}
	}
	
	for(int s = 0; s < lim; s++) {
		int s2 = (lim - 1) ^ s;
		if((!s || f[s]) && (!s2 || g[s2])) ans = std::max(ans, f[s] + g[s2]); 
	}
	std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	solve();

	return 0;
}