【思维】Codeforces Round 750 (Div. 2) F2. Korney Korneevich and XOR (hard version)
2021-10-25 19:54:00 # ACM

题链

题目解析

这是 F1 的数据加强版；

定义一个严格上升子序列的 $f$ 值为该子序列的所有元素异或和，给定一个数组，求它的所有严格上升子序列能出现的 $f$ 值；

一个严格上升的子序列有这样的性质，第 $i+1$ 个数要比第 $i$ 个数大，且位置要更靠后；

始终维护两个数组：
  $vis[i]$ 表示 $i$ 这个值能否是某个子序列异或和；
  $pos[i]$ 表示异或出 $i$ 这个值的某个子序列末尾的最小位置；

于是用 $vector[a_i]$ 记录给定数组 $a_i$ 的所有位置，在 $vector[a_i]$ 中是按照位置递增排序的；

遍历每一个 $vector[i]$，考虑 $vis[[0,8192)]$ 是否存在，如果存在某个 $vis[j]$，$pos[j]$ 就是异或出 $j$ 这个值的某个子序列末尾的最小位置，二分查找 $vector[i]$ 中第一个大于 $pos[j]$ 的位置 $t$，如果存在的话那么 $vis[i \oplus j] = 1$ 并且更新 $pos[i \oplus j] = min(pos[i \oplus j], t)$；

最后所有 $vis[i] = 1$ 的值都是能得到的；

代码实现

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
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	
const int MS = 5001;
const int MAXN = 8192;

int n,m,k;
vector<int > vc[MS];
int pos[MAXN];
int vis[MAXN];

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		int x; cin >> x;
		vc[x].push_back(i);
	}
	for(int i=0;i<MAXN;i++) pos[i] = n+1, vis[i] = 0;
	vis[0] = 1, pos[0] = 0;
	for(int i=0;i<MS;i++){
		for(int j=0;j<MAXN;j++){
			if(vis[j]){
				int t = lower_bound(vc[i].begin(), vc[i].end(), pos[j]) - vc[i].begin();
				if(t < vc[i].size()){
					vis[i^j] = 1;
					pos[i^j] = min(pos[i^j], vc[i][t]);
				} 
			}
		}
	}
	int cnt = 0;
	for(int i=0;i<MAXN;i++) if(vis[i]) cnt++;
	cout << cnt << "\n";
	for(int i=0;i<MAXN;i++) if(vis[i]) cout << i << " ";
	cout << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) solve();
	
	return 0;
}
Prev
2021-10-25 19:54:00 # ACM
Next