bzoj 4269 再见Xor

bzoj 4269 再见Xor

​​ Description 给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。 Input 第一行一个正整数N。 接下来一行N个非负整数。 Output 一行，包含两个数，最大值和次大值。 Sample Input 3 3 5 6 Sample Output 6 5 HINT 100% ： N <= 100000, 保证N个数不全是0，而且在int范围内

Source 简单题wa一发..

线性基 消出与位无关的 第一问贪心 第二问去掉线性基中最小的一位然后再次贪心

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}int s[33],n;inline void insert1(int x){ for (int i=30;~i;--i){ if (!(x&(1<>j&1)) s[i]^=s[j]; for (int j=i+1;j<=30;++j) if (s[j]>>i&1) s[j]^=s[i];break; }else x^=s[i]; }}int main(){ freopen("bzoj4269.in","r",stdin); n=read();int ans1=0,ans2=0; for (int i=1;i<=n;++i) insert1(read()); for (int i=30;~i;--i) if ((ans1^s[i])>ans1) ans1^=s[i]; int to; //for (int i=0;i<=5;++i) printf("%d ",s[i]);puts(""); for (to=0;to<=30;++to) if(s[to]) break;++to; for (int i=30;i>=to;--i){ if ((ans2^s[i])>ans2) ans2^=s[i]; }printf("%d %d\n",ans1,ans2); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。