【题目大意】

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

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

【题解】

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

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

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

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 10010
ll T,n,m,flag,a[MAXN];
inline ll read()
{
ll x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void guess()
{
ll temp=;
for(ll i=(1ll<<),j;i;i>>=)
{
for(j=temp+;j<=n;j++) if(a[j]&i) break;
if(j>n) continue;
swap(a[++temp],a[j]);
for(ll j=;j<=n;j++) if(j!=temp&&(a[j]&i)) a[j]^=a[temp];
}
flag=(temp!=n);
n=temp;
}
ll ask(ll x)
{
x-=flag; ll ans=;
if(!x) return ;
for(int i=n;i;i--) {if(x&) ans^=a[i]; x>>=;}
if(x) return -;
return ans;
}
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
T=read();
for(int CASE=;CASE<=T;CASE++)
{
printf("Case #%d:\n",CASE);
n=read();
for(int i=;i<=n;i++) a[i]=read();
guess();
m=read();
for(int i=;i<=m;i++) {ll x=read(); printf("%I64d\n",ask(x));}
}
return ;
}

附上makedata程序:

 #include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
int main()
{
freopen("cin.in","w",stdout);
srand(time(NULL));
int T=;
printf("%d\n",T);
while(T--)
{
int n=; printf("%d\n",n);
for(int i=;i<=n;i++) printf("%I64d ",(long long)rand()*rand()*rand());
int m=; printf("\n%d\n",m);
for(int i=;i<=m;i++) printf("%d ",rand()%n+);
printf("\n");
}
return ;
}

最新文章

  1. 浅谈如何使用python抓取网页中的动态数据
  2. jQuery.cookie.js
  3. TCP协议漏洞影响大量Linux设备
  4. asp.net全局记住值
  5. POJ1258Agri-Net
  6. ES6之Promise
  7. ES6(阮一峰)学习总结
  8. [物理学与PDEs]第2章第1节 理想流体力学方程组 1.3 理想流体力学方程组的数学结构
  9. pip改源
  10. 再次认识void
  11. Educational Codeforces Round 53 (Rated for Div. 2)
  12. Qt程序ibus输入法不跟随
  13. Qt编写软件运行时间记录(开源)
  14. tkinter拦截关闭事件
  15. Java的GUI如何能够切换界面
  16. Android 配置从GitHub上下载下来的不太规则的源代码库,并保证程序正常运行
  17. JavaScript 中 类型转换
  18. git回退之前版本
  19. delphi 安卓程序如何读取外部配置文件
  20. DapperExtensions 使用教程

热门文章

  1. Java 实现--时间片轮转 RR 进程调度算法
  2. 使用wsgiref库diy简单web架构
  3. 【抽时间 试验】hibernate集合映射inverse和cascade详解
  4. P2P技术基础: 关于TCP打洞技术
  5. 《DSP using MATLAB》示例Example7.23
  6. JavaScript 与 Java、PHP 的比较
  7. 洛谷 P1561 [USACO12JAN]爬山Mountain Climbing
  8. 解决安装Weblogic domain卡住问题(Primeton BPS)
  9. 搭建JIRA汉化后乱码问题
  10. GitFlow在客户端Sourcetree的使用