CF - D1/2. Burenka and Traditions (DP，异或，思维)

https://codeforces.com/contest/1719/problem/D1

题意
给定一个长度为 n 的数列，可以经过下面若干次操作

• 选择一段区间 $[l,r](1\le l\le r\le n)$，选定一个值 $x$，将区间中的所有数 $a_i=a_i\oplus x$，花费 $\lceil \frac{r-l+1}{2}\rceil$。

问，将所有数变为 0 的最小花费？

思路
场上看到这题的时候是完全没有思路的，每次选一个区间异或一个值，花费还随着区间长度变化，觉得肯定很麻烦。。
其实不然，分析花费 $\lceil \frac{r-l+1}{2}\rceil$ 发现，当区间长度为 1 的时候花费为 1，长度为 2 花费为 1，长度为 3 花费 2，长度为 4 花费 2（长度为 2 的花费的两倍），长度为 6 花费为长度为 3 花费的两倍。那么长度较长的区间完全可以分成两段，反正花费不变，而分开操作可以能操作次数更小。
所以每次操作只作用于长度为 2 或者长度为 1 的区间，花费 1。

而每次选什么 x 呢？
每次选最前面的两个数a, b，然后异或上第一个数a，那么第一个数变为 0，第二个数变为 a^b。
同理，四个数最后的数变为 a^b^c^d。
如果这些数总的异或值为 0 的话，那么最后一个数就不用异或自己本来就是 0 了，否则还要花费 1 异或自己变为 0。
所以如果长度为 n 的数列总异或值为 0，那么就需要花费 n-1，否则花费 n。

定义 f[i] 表示，前 i 个位置变为 0 的最小花费。
最坏情况下，f[i] 都是等于 i 的，唯一减少花费的机会就是，将当前位置放到一段区间异或为 0 的区间将花费 -1。所以可以遍历前面所有位置，如果那个位置 p 到当前位置异或值为 0 了，那么就可以用前 p-1 个位置的答案 f[p-1] 加上当前区间花费 i - p + 1 - 1 来转移。
如果两个相同的值异或会变为0，所以可以维护前缀异或，如果 [1~y] 的异或值异或上 [1~x] 为0，那么 [x+1, y] 这段区间的异或值就为 0，可以 O(1) 判断一段区间异或值是否为 0。

直接枚举前面到当前位置异或和为0的位置，时间复杂度$O(n^2)$：

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], f[N];
int sum[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n;i++){
			int x; cin >> x;
			sum[i] = sum[i-1] ^ x;
		}
		
		for(int i=1;i<=n;i++)
		{
			f[i] = f[i-1] + 1;
			for(int j=1;j<=i;j++)
			{
				if((sum[i] ^ sum[j-1]) == 0)
					f[i] = min(f[i], f[j-1] + i - j);
			}
		}
		cout << f[n] << endl;
	}
	
	return 0;
}
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

用 map 存下来 sum[i] 的位置，每次用最后一个和当前 sum[i] 相等的位置来更新，因为最后一个位置可能是转移过的，省下花费更多的，所以用最后一个位置更新即可。
复杂度$O(n)$。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
map<int,int> mp;

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], f[N];
int sum[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n;i++){
			int x; cin >> x;
			sum[i] = sum[i-1] ^ x;
		}
		
		mp.clear();
		
		mp[0] = 0;
		
		for(int i=1;i<=n;i++)
		{
			f[i] = f[i-1] + 1;
			if(mp.count(sum[i]))
			{
				f[i] = min(f[i], f[mp[sum[i]]] + i - mp[sum[i]] - 1);
			}
			mp[sum[i]] = i;
		}
		cout << f[n] << endl;
	}
	
	return 0;
}
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