BZOJ 1115: [POI2009]石子游戏Kam (阶梯nim)
2018-06-17 21:11:43来源:未知 阅读 ()
Submit: 1138 Solved: 697
[Submit][Status][Discuss]
Description
有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
Input
第一行u表示数据组数。对于每组数据,第一行N表示石子堆数,第二行N个数ai表示第i堆石子的个数(a1<=a2<=……<=an)。 1<=u<=10 1<=n<=1000 0<=ai<=10000
Output
u行,若先手必胜输出TAK,否则输出NIE。
Sample Input
2
2 2
3
1 2 4
Sample Output
TAK
HINT
感谢MT大牛翻译.
Source
又是一道很神的题
题目中给出的序列是严格上升的,所以我们可以考虑对整个序列差分一边
然后我们再考虑拿走石子对答案个贡献
拿走石子实际上是减小与前面的差值,增大与后面的差值
这实际上就是一个反方向的阶梯nim游戏!
然后倒着把奇数层异或起来就好啦
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1e6+10,INF=1e9+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();} return x*f; } int a[MAXN]; main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif int QWQ=read(); while(QWQ--) { int N=read(),ans=0; for(int i=1;i<=N;i++) a[i]=read(); for(int i=N;i>=2;i--) a[i]=a[i]-a[i-1]; for(int i=N;i>=1;i--) if( (N-i+1)&1 ) ans=ans^a[i]; puts(ans?"TAK":"NIE"); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash