LOJ#114. k 大异或和(贪心)

xiaoxiao2021-02-28  91

传送门

题解: 建出线性基后按位贪心即可。 注意不能选空集。

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++; } inline LL rd() { char ch=nc(); LL i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } inline void W(LL x) { static int buf[50]; if(!x) {putchar('0'); return;} if(x<0) {putchar('-'); x=-x;} while(x) {buf[++buf[0]]=x%10; x/=10;} while(buf[0]) {putchar(buf[buf[0]--]+'0');} } const int LIM=50, N=1e5+50; int n, cnt, lim=LIM; LL ans, a[N], bin[LIM+5], pre[LIM+5], base[LIM+5]; inline void inc(LL v) { for(int i=LIM;~i && v;i--) { if(v&bin[i]) { if(!base[i]) { base[i]=v; ++cnt; break; } else v^=base[i]; } } } inline void solve(int p,LL kth) { if(!~p) return; if(!base[p]) {solve(p-1,kth); return;} if(!(ans&bin[p])) { if(bin[pre[p]]>=kth) solve(p-1,kth); else ans^=base[p], solve(p-1,kth-bin[pre[p]]); } else { if(bin[pre[p]]>=kth) ans^=base[p],solve(p-1,kth); else solve(p-1,kth-bin[pre[p]]); } } int main() { n=rd(); for(int i=0;i<=LIM;i++) bin[i]=1ll<<i; for(int i=1;i<=n;i++) inc(rd()); while(!base[lim]) --lim; for(int i=1;i<=lim;i++) pre[i]=pre[i-1]+(base[i-1] ? 1 : 0); for(int i=rd();i;i--) { LL k=rd()+(n==cnt); if(bin[cnt]<k) W(-1); else ans=0,W((solve(lim,k),ans)); putchar('\n'); } }
转载请注明原文地址: https://www.6miu.com/read-2614632.html

最新回复(0)