首页 > 代码库 > 【HDU3949】XOR

【HDU3949】XOR

2024-08-16 03:12:19   209人阅读

【题目大意】

给定一个数组，求这些数组通过异或能得到的数中的第k小是多少。

传送门：http://vjudge.net/problem/HDU-3949

【题解】

首先高斯消元求出线性基，然后将k按照二进制拆分即可。

注意当高斯消元结束后若末尾有0则第1小是0 特判一下然后k--。

然后HDU输出long long是用%I64d 无论C++还是G++都是。（虽然我用了lld也AC了）

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<ctime> 6 #include<cmath> 7 #include<algorithm> 8 using namespace std; 9 typedef long long ll;10 #define MAXN 1001011 ll T,n,m,flag,a[MAXN];12 inline ll read()13 {14     ll x=0,f=1;  char ch=getchar();15     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}16     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}17     return x*f;18 }19 void guess()20 {21     ll temp=0;22     for(ll i=(1ll<<62),j;i;i>>=1)23     {24         for(j=temp+1;j<=n;j++)  if(a[j]&i)  break;25         if(j>n)  continue;26         swap(a[++temp],a[j]);27         for(ll j=1;j<=n;j++)  if(j!=temp&&(a[j]&i))  a[j]^=a[temp];28     }29     flag=(temp!=n);30     n=temp;31 }32 ll ask(ll x)33 {34     x-=flag;  ll ans=0;35     if(!x)  return 0;36     for(int i=n;i;i--)  {if(x&1)  ans^=a[i];  x>>=1;}37     if(x)  return -1;38     return ans;39 }40 int main()41 {42     //freopen("cin.in","r",stdin);43     //freopen("cout.out","w",stdout);44     T=read();45     for(int CASE=1;CASE<=T;CASE++)46     {47         printf("Case #%d:\n",CASE);48         n=read();49         for(int i=1;i<=n;i++)  a[i]=read();50         guess();51         m=read();52         for(int i=1;i<=m;i++)  {ll x=read();  printf("%I64d\n",ask(x));}53     }54     return 0;55 }

附上makedata程序：

 1 #include<iostream> 2 #include<cstdio> 3 #include<ctime> 4 #include<cstdlib> 5 using namespace std; 6 int main() 7 { 8     freopen("cin.in","w",stdout); 9     srand(time(NULL));10     int T=30;11     printf("%d\n",T);12     while(T--)13     {14         int n=10000;  printf("%d\n",n);15         for(int i=1;i<=n;i++)  printf("%I64d ",(long long)rand()*rand()*rand());16         int m=10000;  printf("\n%d\n",m);17         for(int i=1;i<=m;i++)  printf("%d ",rand()%n+1);18         printf("\n");19     }20     return 0;21 }

 

【HDU3949】XOR


联系
我们