【bzoj3105】【cqoi2013】【新Nim游戏】【线性基+贪心】
2024-08-31 08:46:20
Description
传统的Nim游戏是这种:有一些火柴堆,每堆都有若干根火柴(不同堆的火柴数量能够不同)。两个游戏者轮流操作,每次能够选一个火柴堆拿走若干根火柴。能够仅仅拿一根,也能够拿走整堆火柴。但不能同一时候从超过一堆火柴中拿。
拿走最后一根火柴的游戏者胜利。
本题的游戏略微有些不同:在第一个回合中,第一个游戏者能够直接拿走若干个整堆的火柴。
能够一堆都不拿,但不能够所有拿走。第二回合也一样,第二个游戏者也有这样一次机会。
从第三个回合(又轮到第一个游戏者)開始,规则和Nim游戏一样。
假设你先拿,如何才干保证获胜?假设能够获胜的话,还要让第一回合拿的火柴总数尽量小。
Input
第一行为整数k。即火柴堆数。
第二行包括k个不超过109的正整数,即各堆的火柴个数。
Output
输出第一回合拿的火柴数目的最小值。假设不能保证取胜,输出-1。
Sample Input
6
5 5 6 6 5 5
5 5 6 6 5 5
Sample Output
21
HINT
k<=100
题解:先手必胜的条件为剩下的火柴中不存在异或和为0的子集。
因此我们须要寻求极大的线性无关组。答案即为总和减去极大线性无关组的权值和。
能够证明这是一个拟阵,然后贪心就好了。贪心过程中维护线性基。
。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int ins[50],k,a[1001],c[1001];
long long ans,sum;
int main()
{
scanf("%d",&k);
for (int i=1;i<=k;i++) scanf("%d",&a[i]);
sort(a+1,a+k+1);
for (int i=1;i<=k;i++) sum+=(long long)(c[i]=a[i]);
for (int i=k;i>=1;i--)
{
for (int j=30;~j;j--)
if (a[i]&(1<<j))
{
if (!ins[j])
{
ins[j]=i;break;
}
else a[i]^=a[ins[j]];
}
if (a[i]) ans+=(long long )c[i];
}
printf("%lld",sum-ans);
}
最新文章
- Oracle同义词
- IIS服务器和xampp中的appche服务器端口冲突解决办法
- (转载)SQL— CONCAT(字符串连接函数)
- python __name__
- hibernate中 inverse的用法(转载)
- 安装Ubuntu14.04版本的操作系统
- R2D2 and Droid Army(多棵线段树)
- Python深入02 上下文管理器
- HTTP首部及各状态码
- javascript笔记之正则表达式
- 23个.NET开源项目
- 【COGS1049】天空中的繁星
- 1009 Enigma
- 转载文章:Windows Azure 七月份更新:SQL 数据库、流量管理器、自动伸缩、虚拟机
- Java用ZIP格式压缩和解压缩文件
- 练习使用markdown
- RHEL7 配置网络yum源
- ";车羊门问题";作业
- Spring Boot 之httpClient使用
- JDK1.7 的 HashMap
热门文章
- java项目怎么打jar包(项目中包含第三方jar包)
- 1102 A-B数对
- SugarCRM安装过程——PHP文件上传限制问题
- 【PostgreSQL-9.6.3】LOG: unrecognized configuration parameter ";dynamic_shared_memory_type";
- 【转载】 python sort、sorted高级排序技巧
- 梦想CAD控件图层COM接口知识点
- Introduction of Version Control/Git, SVN
- Java变量及数据类型
- JAVA基础——集合Iterator迭代器的实现
- 字符串--P1308 统计单词数