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

题链

题目解析

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

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

考虑该数组的第 $i$ 个数字，如果我能知道前 $i-1$ 个数字组成的上升子序列能异或出哪些值，并且能知道异或出这些值所需要的上升子序列的最后一个值的最小值就好了，比如说序列 [2,4,6,5]，下标分别为 [1,2,3,4]，当 $i=4$ 时，前 $3$ 个数字能组成的子序列可得到 [0,2,4,6] 这些值，并且得到 0 的子序列的末尾最小值是 0，得到 2 的子序列的末尾最小值是 2，得到 4 的子序列的末尾最小值是 4，得到 6 的子序列的末尾最小值是 4 (由子序列[2,4]的到)；

于是我记录前 $i$ 个数字能否得到 $w$，对应 $vis[w] = 1$，以及记录得到 $w$ 的子序列末尾最小值是 $x$，对应 $val[w] = x$；

那么对于第 $i$ 个数字，只需要遍历前 $i-1$ 个数组成的子序列可能异或出来的值 $w$，并判断 $vis[w]$ 是否存在，以及能组成 $w$ 的子序列的末尾最小值 $val[w]$ 是否小于第 $i$ 个数字，然后更新 $vis[]$ 和 $val[]$；

代码实现

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
	#define gg(x) cout << #x << ": " << x << "\n";
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<int ,int >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define fi first
	#define se second
	#define ll long long

const int mod = 998244353;
const int MAXN = 2e9;
const int MS = 100009;

int n,m,k;
int a[MS];
int b[MS];
int vis[MS];
int val[MS];

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=0;i<512;i++) val[i] = 520;
	vis[0] = 1;
	val[0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<512;j++){
			if(vis[j] && val[j] < a[i]){
				vis[j^a[i]] = 1;
				val[j^a[i]] = min(val[j^a[i]], a[i]);
			}
		}
	}
	
	int cnt = 0;
	for(int i=0;i<512;i++){
		cnt += vis[i];
	}
	cout << cnt << "\n";
	for(int i=0;i<512;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:50:00 # ACM
Next