题目传送门:Problem - 7184 (hdu.edu.cn)
题意 / Problem
给定一个数组,每次可以选择一段连续区间[l, r]并将区间内所有元素变为区间元素的异或和。问最终能够把整个数组变成的最大的数,要求所有数字都变成相同的。
思路 / Thought
线性基的板子,就是求一个数组的最大异或和。
线性基可以看这篇文章《[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记》
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9, MAXL = 55; int p[60], d[60], tot = 0, N, M; void ins(int x) { for(int i = MAXL;i >= 0; -- i) { if(!x)return; if(!(x >> i & 1))continue; if(p[i])x ^= p[i]; else return p[i] = x, void(); } } void rebuild() { tot = 0; for(int i = 0;i <= MAXL; ++ i) { for(int j = 0;j < i; ++ j)if(p[i] >> j & 1)p[i] ^= p[j]; if(p[i])d[tot ++] = p[i]; } } int que_max() { int res = 0; for(int i = 0;i < tot; ++ i)res ^= d[i]; return res; } void solve() { cin >> N; memset(p, 0, sizeof p); for(int i = 1;i <= N; ++ i) { int x;cin >> x; ins(x); } rebuild(); cout << que_max() << '\n'; } signed main() { ios::sync_with_stdio(false); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING