p4301 [CQOI2013]新Nim游戏
2024-09-04 14:37:06
分析
通过nim游戏我们可以知道我们现在的任务就是通过两轮之后使得剩余的几堆异或和为非0数
所以我们只需要在第一步使得剩余集合的任意非空子集的异或和非0即可
于是我们考虑线性基
我们知道线性基所选数会使总和最大且任意非空子集的异或和非0
于是跑线性基即可
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
long long a[],n,Ans,belong[];
inline bool cmp(long long x,long long y){return x>y;}
inline void work(){
long long i,j,k;
for(i=;i<=n;i++){
k=a[i];
for(j=;j>=;j--)
if((<<j)&a[i]){
if(!belong[j]){
belong[j]=a[i];
break;
}
a[i]^=belong[j];
}
if(!a[i])Ans+=k;
}
}
int main(){
long long i,j,k;
scanf("%lld",&n);
for(i=;i<=n;i++)scanf("%lld",&a[i]);
sort(a+,a+n+,cmp);
work();
printf("%lld\n",Ans);
return ;
}
最新文章
- java普通servlet三层开发模式图
- html5 list属性、autocomplete属性、pattern属性
- MatLab实现FFT与功率谱
- [原创]obj-c编程15[Cocoa实例02]:KVC和KVO的实际运用
- WimMaker 2.0 (2013.10) WIM制作工具
- LeetCode 163. Missing Ranges (缺失的区间)$
- 使用sklearn进行数据挖掘-房价预测(3)—绘制数据的分布
- 微信跳一跳Python
- Mac效率:配置Alfred web search
- 1.3、Android Studio创建一个Android Library
- c# 基于文件系统实现的队列处理类
- spark streaming中维护kafka偏移量到外部介质
- PHP 简易聊天室 利用redis的订阅发布功能
- python之类和__init__
- 阿里巴巴数据源Druid在tomcat中的配置
- Android--字符串和Drawable之间互相转化
- gcc常用编译选项
- excel导入 导出
- Centos 7 下 Corosync + Pacemaker + psc + HA-proxy 实现业务高可用
- 带你走进EJB--将EJB发布为Webservice(3)