Noi.ac #309. Mas的童年(贪心)

it2022-05-06  0

/* 用所谓的加法拆分操作得到 x + y = (x ^ y) + 2 * (x & y) 那么我们这两段异或相当于前缀和 + 2 * 分段使左右两块&最大 记当前前缀异或和为S, 那么我们要找到优秀的X最大化(S^X) & X 显然贪心可行, 插入的时候维护当前数字所有子集, 打个vis标记, 就能快速查询了 */ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<iostream> #define ll long long #define mmp make_pair #define M 3000100 using namespace std; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } bool vis[M]; int n, a[M], s[M]; void insert(int x) { if(vis[x]) return; vis[x] = true; for(int i = 20; i >= 0; i--) { if(x & (1 << i)) insert(x ^ (1 << i)); } } int query(int x) { int ans = 0; for(int i = 20; i >= 0; i--) { if(x & (1 << i)) continue; if(vis[ans | (1 << i)]) ans |= (1 << i); } return ans; } int main() { n = read(); for(int i = 1; i <= n; i++) { a[i] = read(); s[i] = s[i - 1] ^ a[i]; } for(int i = 1; i <= n; i++) { cout << s[i] + query(s[i]) * 2 << " "; insert(s[i]); } return 0; }

转载于:https://www.cnblogs.com/luoyibujue/p/10627933.html


最新回复(0)