P3480 [POI2009]KAM-Pebbles 阶梯NIM
2024-09-07 04:40:47
$ \color{#0066ff}{ 题目描述 }$
有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
\(\color{#0066ff}{输入格式}\)
多组输入,第一行一个整数u代表数据组数(1<=u<=10)
接下来共2*u行,每两行代表一组数据:
第一行只有一个整数n(1<=n<=1000),表示石子堆数;
第二行有n个整数用空格隔开,第i个整数ai表示第i堆的石子个数,保证a1<=a2<=a3...<=an。
对于每组数据,保证石子总数不超过10000。
\(\color{#0066ff}{输出格式}\)
输出u行,如果第i组数据先手必胜,输出“TAK”,否则输出“NIE”。
\(\color{#0066ff}{输入样例}\)
2
2
2 2
3
1 2 4
\(\color{#0066ff}{输出样例}\)
NIE
TAK
\(\color{#0066ff}{数据范围与提示}\)
none
\(\color{#0066ff}{题解}\)
考虑每一堆石子能拿多少,就是\(a[i]-a[i-1]\),差分数组
如果在i堆拿了x个石子,那么相当于i堆可拿石子数-x,i+1堆可拿石子数+x
也就是说从i堆向i+1堆拿了x个石子,这是反着的阶梯NIM!!!
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
int a[1005050];
int main() {
for(int T = in(); T --> 0;) {
int n = in();
int ans = 0;
for(int i = 1; i <= n; i++) a[i] = in();
for(int i = n; i >= 1; i--) a[i] -= a[i - 1];
//注意要反着求
for(int i = n; i >= 1; i -= 2) ans ^= a[i];
printf(ans? "TAK\n" : "NIE\n");
}
return 0;
}
最新文章
- 解读ASP.NET 5 &; MVC6系列(10):Controller与Action
- 工厂模式 - Factory
- sql server 中不同服务器上的数据库中表怎么互导数据
- unity, Shader.Find的一个坑
- java字符串拼接与性能
- linux脚本编程(shell)浅介 (转载)
- Spring Boot构建RESTful API与单元测试
- 【转】ACE开发环境搭建
- Stage3D学习笔记(三):使用GPU绘制一个图片
- 自己写的一个banner动画
- POJ2739 Sum of Consecutive Prime Numbers(尺取法)
- ListView的小知识
- Shell 基本运算符
- eclipse 使用问题
- 简述angular自定义过滤器在页面和控制器中的使用
- Mac学习
- Mysql知识点个人整理
- netty源码解解析(4.0)-12 Channel NIO实现:channel初始化
- unity 获取网络时间
- C编程基础
热门文章
- leetcode599
- Spring Cloud Eureka 5 (服务发现与消费-简单的robbin使用)
- <;转>;Linux环境进程间通信--信号灯(四)
- Spring Data系列之Jpa(一)
- Java,猜猜输出是什么?
- js,javascript生成 UUID的四种方法
- 599. Minimum Index Sum of Two Lists两个餐厅列表的索引和最小
- Python 面向对象class(2)
- 分享一个好用的功能强大的节点树jQuery插件
- (转)通过Javascript得到URL中的参数(query string)