BZOJ.3105.[CQOI2013]新Nim游戏(线性基 贪心 博弈论)
2024-09-20 18:05:51
如果后手想要胜利，那么在后手第一次取完石子后 可以使石子数异或和为0。那所有数异或和为0的线性基长啥样呢，不知道。。
往前想，后手可以取走某些石子使得剩下石子异或和为0，那不就是存在异或和为0的子集吗。
so先手要使得他取完后不存在异或和为0的子集。从大到小依次尝试插入线性基即可。
//820kb 0ms
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define Bit 30
const int N=105;
int n,A[N],base[36];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline int Insert(int v)
{
for(int i=Bit,x=v; ~i; --i)
if(x>>i & 1)
if(base[i]) x^=base[i];
else {base[i]=x; return 0;}
return v;
}
int main()
{
n=read();
for(int i=1; i<=n; ++i) A[i]=read();
std::sort(A+1,A+1+n);
long long ans=0;
for(int i=n; i; --i) ans+=Insert(A[i]);
printf("%lld\n",ans);
return 0;
}
最新文章
- 关于搭建webservice以及无法通过URL访问的简易解决办法
- 【浏览器渲染原理】渲染树构建之渲染树和DOM树的关系（转载 学习中。。。）
- strlen与sizeof的区别 [转]
- Yii2框架数据库增删改查小结
- FireMonkey vs. VCL （FMX的UI更灵活，图形效果更强，硬件加速，内嵌3D，使用浮点数更精确，跨平台，可使用Mida converter转换和TFireMonkeyContainer内嵌）
- SCXML和QScxml使用总结
- bean 与 map 互转.
- C 语言实现字符串替换
- 记一次Linux下给硬盘分区格式化操作
- linux上MongoDB安装部署
- PS调出唯美紫蓝色天空背景女生照片
- OpenJDK和JDK区别
- MySQL崩溃恢复与组提交
- C#多线程读写同一文件处理
- 字符串搜索 find()
- POJ 1126
- SpringDataJPA最佳实践（一）简介
- [转] 移动平台Html5的viewport使用经验
- flask模块
- 值得一做》关于并查集的进化题目 BZOJ1015（BZOJ第一页计划）（normal-）