HDU5795A Simple Nim SG定理
2024-10-12 21:44:04
A Simple Nim
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 980 Accepted Submission(s): 573
Problem Description
Two players take turns picking candies from n heaps,the player who picks the last one will win the game.On each turn they can pick any number of candies which come from the same heap(picking no candy is not allowed).To make the game more interesting,players can separate one heap into three smaller heaps(no empty heaps)instead of the picking operation.Please find out which player will win the game if each of them never make mistakes.
Input
Intput contains multiple test cases. The first line is an integer $1\le T\le 100$, the number of test cases. Each case begins with an integer n, indicating the number of the heaps, the next line contains N integers $s[0],s[1], ....,s[n-1]$, representing heaps with $s[0],s[1], ...,s[n-1]$ objects respectively.$(1\le n\le 10^6,1\le s[i]\le 10^9)$
Output
For each test case,output a line whick contains either"First player wins."or"Second player wins".
Sample Input
2
2
4 4
3
1 2 4
Sample Output
Second player wins.
First player wins.
题意:n堆石子,两个人轮流拿,每次可以选择任意一堆取任意个(不能不拿)或者将一个堆分成3个小堆,问先手胜还是后手胜。
题解:SG定理的应用,可以看做是Nim博弈,打表找规律,我也不会证
i=8*k+7时SG[i]=8*k+8,i=8*k+8时SG[i]=8*k+7其他情况SG[i]=i。
#include<bits/stdc++.h>
#define N 45000
#define mes(x) memset(x, 0, sizeof(x));
#define ll __int64
const long long mod = 1e9+;
const int MAX = 0x7ffffff;
using namespace std;
int dir[], SG[];
int getSG(int n){
if(n == ) return ;
if(n% == ) return n-;
if(n% == ) return n+;//注意这里是n%8==7,不是n%7==0....
return n;
}
int main()
{
int T,t, i,n, ans;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(ans=i=;i<n;i++){
scanf("%d", &t);
ans ^= getSG(t);
}
if(ans==) printf("Second player wins.\n");
else printf("First player wins.\n");
}
return ;
}
最新文章
- angularjs $broadcast $emit $on 事件触发controller间的值传递
- Lintcode 469. 等价二叉树
- H5 多个视频 循环播放效果
- mysql模糊查询 like/REGEXP
- PreparedStatement和Statement的区别
- register 不允许 block 模式,而默认的是
- WebDAV被启用(转)
- Java异常基础Exception
- linux下mysql出现Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)解决方法
- CSS文字样式
- animation渐进实现点点点等待效果实例页面
- .Net 分布式技术比较
- smarty模板基础知识
- org.springframework.core.NestedIOException: ASM ClassReader failed to parse class file - probably du
- js按位运算符及其妙用
- class-逻辑回归与最大熵模型
- canvas路径剪切和判断是否在路径内
- Java io概述
- python的序列化与反序列化
- first H5