2023年第十四届蓝桥杯大赛软件类省赛C&C++大学C 组真题（代码&完整题解）

#include<bits/stdc++.h> #include<set> #include<cmath> #include<vector> #include<numeric> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; #define ll long long #define pii pair<int,int> #define debug1(x) cout<<x<<" " #define debug2(x) cout<<x<<endl #define rep1(a,b,c) for (int a = (b) ; a < (c) ; a+=1) #define rep2(a,b,c) for (int a = (b) ; a < (c) ; a+=2) const int INF = 0x3f3f3f3f; const int maxn = 2e5+10; const int mod = 998244353; //埃氏筛法 vector<int> prime; bool is_prime[maxn]; void Eratosthenes(int n) { is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) is_prime[i] = true; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { prime.push_back(i); if ((ll)i * i > n) continue; for (int j = i * i; j <= n; j += i) is_prime[j] = false; } } } //快速求逆元 int inv(int a){ int b = mod-2, ans = 1; while(b){ if(b&1) ans = (ll) ans*a%mod; a = (ll) a*a%mod; b >>= 1; } return ans; } //回文串 void Manacher(char* str,char* new_str,int* p){ int n = strlen(str), m=0; new_str[m++]='$'; new_str[m++]='#'; for(int i=0;i<n;i++) new_str[m++]=str[i], new_str[m++]='#'; new_str[m]='\0'; int mx=0,id=1,ans = 0; for(int i=1;i<m;i++){ p[i] = id<mx ? min(p[2*id-i],mx-i) : 1; while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++; if(i+p[i]>mx) mx=i+p[i], id=i; } return ; } //快速幂 long long qpow(long long a, long long b) { long long res = 1; for (; b > 0; b >>= 1){ if ((b & 1) == 1) res = res * a % mod; a = a * a % mod; } return res; } //01字典树 存前缀异或和 int trie[4*maxn][2], m=20, cur=0; void add(int x) { int rt = 0; for (int i = m; ~i; --i) {// 二进制一位一位向下取 int b = (x >> i) & 1; if (!trie[rt][b]) trie[rt][b] = ++cur; rt = trie[rt][b]; } } //01字典树中查找与 x 异或后结果最大的数 int xor_max(int x) { int rt = 0, max = 0; for (int i = m; ~i; --i) { int b = (x >> i) & 1; if (trie[rt][b ^ 1]) { rt = trie[rt][b ^ 1]; max |= 1 << i; } else rt = trie[rt][b]; } return max; } //01字典树中查找与 x 异或后结果最小的数 int xor_min(int x) { int rt = 0, min = 0; for (int i = m; ~i; --i) { int b = (x >> i) & 1; if (trie[rt][b]) rt = trie[rt][b]; else { rt = trie[rt][b ^ 1]; min |= 1 << i; } } return min; } int n, ans, A[maxn], lmax, lmin, rmax[maxn], rmin[maxn]; void solve(){ scanf("%d",&n); rep1(i,1,n+1) scanf("%d",&A[i]); lmin = rmin[n + 1] = INF;lmax = rmax[n + 1] = 0; for (int i = n, s = 0; i > 0; --i) { add(s), s ^= A[i]; rmax[i] = max(rmax[i + 1], xor_max(s)); rmin[i] = min(rmin[i + 1], xor_min(s)); } for (; cur; --cur) trie[cur][0] = trie[cur][1] = 0; trie[0][1] = trie[0][0] = 0; for (int i = 1, s = 0; i < n; ++i) { add(s), s ^= A[i]; lmax = max(lmax, xor_max(s)); lmin = min(lmin, xor_min(s)); ans = max(ans, lmax - rmin[i + 1]); ans = max(ans, rmax[i + 1] - lmin); } printf("%d", ans); return ; } int main(){ ios::sync_with_stdio(false) ; cin.tie(0); cout.tie(0) ; // int N; scanf("%d",&N); while(N--) solve(); return 0; }