http://acm.hdu.edu.cn/showproblem.php?pid=3949

求n个数的异或和第k小。

参考:https://blog.sengxian.com/algorithms/linear-basis

没了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int BASE=;
ll b[];
int n,cnt;
vector<ll>mp;
ll query(ll k){
if(cnt!=n)k--;
if(k>(1LL<<(int)mp.size())-)return -;
ll ans=;
for(int i=;i<(int)mp.size();i++){
if(k>>i&)ans^=mp[i];
}
return ans;
}
inline void init(){
cnt=;
memset(b,,sizeof(b));
mp.clear();
}
int main(){
int t;
scanf("%d",&t);
for(int cas=;cas<=t;cas++){
printf("Case #%d:\n",cas);
scanf("%d",&n);
init();
for(int i=;i<=n;i++){
ll a;scanf("%lld",&a);
for(int j=BASE;j>=;j--){
if(a>>j&){
if(b[j])a^=b[j];
else{
b[j]=a;cnt++;
for(int k=j-;k>=;k--)
if(b[k]&&(b[j]>>k&))b[j]^=b[k];
for(int k=j+;k<=BASE;k++)
if(b[k]>>j&)b[k]^=b[j];
break;
}
}
}
}
for(int i=;i<=BASE;i++)
if(b[i])mp.push_back(b[i]);
int q;
scanf("%d",&q);
while(q--){
ll k;
scanf("%lld",&k);
printf("%lld\n",query(k));
}
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

最新文章

  1. People Tools catalog tables.
  2. Tomcat启动时项目重复加载,导致资源初始化两次的问题
  3. C#通过安全证书生成签名和验签辅助类
  4. fast-framework – 基于 JDK 8 实现的 Java Web MVC 框架
  5. Laravel5.1控制器小结
  6. Sql CLR
  7. VS2012格式化插件配置备份
  8. JNI(2)
  9. 背包问题matlab程序
  10. Openlayers 3 图层探查功能
  11. 【模板】Tarjan求强连通分量
  12. burpsuite截断上传webshell
  13. P1577 切绳子
  14. SQLServer 2008 R2查看字段约束
  15. tensorflow-softmax
  16. Python开发【笔记】:什么是RESTful框架
  17. c++——默认参数、函数占位参数
  18. 恢复二进制文件中的block符号表
  19. Error creating bean with name &#39;adminUserController&#39;: Injection of autowired dependencies failed;
  20. easyUI datagrid 排序

热门文章

  1. gdb 分析出错
  2. PyMySQL连接MySQL数据库
  3. 阿里云ECS下CentOS7.4 yum安装Python3.6环境
  4. Swift使用AVAudioPlayer来调节游戏的背景音乐大小
  5. 用Python实现一个端口扫描,只需简单几步就好
  6. Java注解的基本原理
  7. ORACLE高级部分内容
  8. anaconda安装scrapy报错解决办法
  9. Keil sct分散加载文件
  10. POJ 2069 Super Star(计算几何の最小球包含+模拟退火)