首页 > 代码库 > BZOJ3105: [cqoi2013]新Nim游戏
BZOJ3105: [cqoi2013]新Nim游戏
题解:
线性基?类似于向量上的基底。
此题题解戳这里:http://blog.csdn.net/wyfcyx_forever/article/details/39477673
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100+514 #define maxm 100000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)23 #define mod 100000000724 using namespace std;25 inline int read()26 {27 int x=0,f=1;char ch=getchar();28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30 return x*f;31 }32 int n,a[maxn],b[maxn];33 ll sum,ans;34 int main()35 {36 freopen("input.txt","r",stdin);37 freopen("output.txt","w",stdout);38 n=read();39 for1(i,n)a[i]=read(),sum+=(ll)a[i];40 sort(a+1,a+n+1);41 for3(i,n,1)42 {43 int t=a[i];44 for3(j,30,0)45 if(a[i]>>j&1)46 {47 if(b[j])a[i]^=b[j];48 else {b[j]=a[i];break;}49 }50 if(a[i])ans+=(ll)t;51 }52 cout<<sum-ans<<endl;53 return 0;54 }
动态维护线性基的方法真是orz了。
3105: [cqoi2013]新Nim游戏
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 396 Solved: 239
[Submit][Status]
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
BZOJ3105: [cqoi2013]新Nim游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。