https://ac.nowcoder.com/acm/contest/11168

E - CCA的区间

 

题意：给定一个数列 a,1≤ai≤223a,1\le a_i\le 2^{23}，每个数都是 2 的幂次，最多可以翻转一个区间，要找出一个内部不含相同元素，且区间和最大的区间，问区间和。

SOSdp

可以翻转一个区间，所以问题变为求两个不含相同元素的区间，区间和最大。

由数据范围发现可以把每个区间进行状压，遍历左端点可以得到所有不含相同元素的区间状压为数。

接下来就要找到两个and等于0的数，和最大。

dp[x]dp[x] 表示 xx 的所有子集的最大值。

由 FMT 的技巧可以得到转移：

设 dp[i][x]dp[i][x] 表示与 xx 只有前 ii 位可能不同的所有数字 y,(y∈x)y,(y\in x) 的最大 dpdp 值，则

dp[i][x]= \begin{cases} dp[i-1][x], & \text {if x&$2^i$=0} \\ \max(dp[i-1][x],dp[i-1][x\oplus 2^{i}], & \text{if x&$2^i$=1} \end{cases}

把第一维压缩掉就变成 dp[x]dp[x]。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int a[N];
int vis[24], dp[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		int tmp = 0;
		for (int j = i; j <= n; j++) {
			int t = (int)log2(1.0*a[j]);
			if (vis[t])break;
			vis[t] = 1;
			tmp |= a[j];
			dp[tmp] = tmp;
		}
	}
	for (int i = 0; i < 24; i++) {
		for (int j = 1; j < (1 << 24); j++) {
			if (j >> i & 1) {
				dp[j] = max(dp[j], dp[j ^ (1 << i)]);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < (1 << 24); i++) {
		ans = max(ans, dp[i] + dp[((1 << 24) - 1) ^ i]);
	}
	printf("%d\n", ans);
	return 0;
}