【BZOJ】【1115】【POI2009】石子游戏KAM
2024-08-24 06:02:51
博弈论
这个题……一看就觉得很捉急啊= =肿么办?
灵光一现:差分一下~
那么我们看一下差分以后,从第 i 堆中拿走 k 个石子变成了:a[i]-=k; a[i+1]+=k;
嗯这就转化成了阶梯博弈!
只不过是倒着的阶梯……从n到0……(sigh之前是从1到n,WA掉了……SB了一下)
/**************************************************************
Problem: 1115
User: Tunix
Language: C++
Result: Accepted
Time:24 ms
Memory:812 kb
****************************************************************/ #include<cstdio> int a[],b[];
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=;i<=n;++i){ scanf("%d",&a[i]); b[i]=a[i]-a[i-];}
int ans=;
for(int i=n;i>;i-=) ans^=b[i];
puts(ans ? "TAK" : "NIE");
}
return ;
}
1115: [POI2009]石子游戏Kam
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 627 Solved: 385
[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 2
3
1 2 4
2
2 2
3
1 2 4
Sample Output
NIE
TAK
TAK
HINT
感谢MT大牛翻译.
Source
最新文章
- 11个很棒的 jQuery 图表库
- [Linux] zip 与 unzip 命令
- C++ note
- jQuery 常见操作实现方式
- win8找到程序员计算器
- Conversion to Dalvik format failed: Unable to execute dex: null
- JS时间戳
- boost::asio译文
- poj 3959 Alignment of Code <;vector>;“字符串”
- NFC-P2P MODE
- [ios2]使用NSOperationQueue简化多线程开发和队列的优先级 【转】
- 【Luogu2458】保安站岗(动态规划)
- ansible 变量详解
- git 不能创建分支
- vs get set快捷键
- (广度搜索)A - Prime Path(11.1.1)
- Shader基础(固定管线着色器)
- HBase启动报错:ERROR: org.apache.hadoop.hbase.ipc.ServerNotRunningYetException: Server is not running yet
- POJ-1179 Polygon (动态规划)
- Python引用复制,参数传递,弱引用与垃圾回收