BZOJ.1115.[POI2009]石子游戏Kam(阶梯博弈)

时间:2022-11-12 14:44:18

BZOJ

洛谷


\(Description\)

有\(n\)堆石子。除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作,每次可以从一堆石子中拿掉任意多的石子,但要保证操作后仍然满足初始时的条件。谁没有石子可拿时输。求先手是否必胜。

\(Solution\)

限制条件就是相邻两个数的差非负。那么记查分数组\(d_i=a_i-a_{i-1}\)。假设拿走第\(i\)堆的\(x\)个石子,影响是\(d_i\)-=\(x\),\(d_{i+1}\)+=\(x\),就相当于从\(d_i\)中拿\(x\)个给\(d_{i+1}\)。

显然原题意和对差分数组做反向的阶梯\(Nim\)是等价的,然后就做完啦。


//1120kb	4ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1005; int A[N];
char IN[MAXIN],*SS=IN,*TT=IN; inline int read()
{
int now=0; register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
} int main()
{
for(int T=read(); T--;)
{
const int n=read();
for(int i=1; i<=n; ++i) A[i]=read();
int s=0;
for(int i=n; i>=1; i-=2) s^=(A[i]-A[i-1]);
puts(s?"TAK":"NIE");
} return 0;
}

BZOJ.1115.[POI2009]石子游戏Kam(阶梯博弈)的更多相关文章

  1. BZOJ 1115&colon; &lbrack;POI2009&rsqb;石子游戏Kam &lbrack;阶梯NIM&rsqb;

    传送门 有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数.两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏.问先手是否必胜 ...

  2. bzoj 1115&colon; &lbrack;POI2009&rsqb;石子游戏Kam -- 博弈论

    1115: [POI2009]石子游戏Kam Time Limit: 10 Sec  Memory Limit: 162 MB Description 有N堆石子,除了第一堆外,每堆石子个数都不少于前 ...

  3. BZOJ 1115&colon; &lbrack;POI2009&rsqb;石子游戏Kam

    1115: [POI2009]石子游戏Kam Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 883  Solved: 545[Submit][Stat ...

  4. 【BZOJ1115】&lbrack;POI2009&rsqb;石子游戏Kam 阶梯博弈

    [BZOJ1115][POI2009]石子游戏Kam Description 有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数.两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要 ...

  5. &lbrack;BZOJ 1115&rsqb; &lbrack;POI2009&rsqb; 石子游戏Kam 【阶梯博弈】

    题目链接:BZOJ - 1115 题目分析 首先看一下阶梯博弈: 阶梯博弈是指:初始有 n 堆石子,每次可以从任意的第 i 堆拿若干石子放到第 i - 1 堆.最终不能操作的人失败. 解法:将奇数位的 ...

  6. BZOJ 1115 &lbrack;POI2009&rsqb;石子游戏Kam(阶梯博弈)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1115 [题目大意] 有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数. ...

  7. 【BZOJ】1115&colon; &lbrack;POI2009&rsqb;石子游戏Kam

    http://www.lydsy.com/JudgeOnline/problem.php?id=1115 题意:n堆石子,个数是从左到右单增.每一次可以从任意堆取出任意石子,但要保持单增这个性质.问先 ...

  8. &lbrack;BZOJ1115&rsqb;&lbrack;POI2009&rsqb;石子游戏Kam解题报告&vert;阶梯博弈

    有N堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数.两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏.问先手是否必胜. 首先 ...

  9. 【bzoj1115】&lbrack;POI2009&rsqb;石子游戏Kam(博弈论)

    题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=1115 观察问题,我们能发现前后相邻两堆石子的数量差一定非负,而我们在第i堆石子中移走k ...

随机推荐

  1. WPF -Enum的三种绑定方法

    一.使用ObjectDataProvider <Window xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentat ...

  2. 关于phpcms v9投票模块选项排序listorder设定问题

    关于phpcms v9投票模块选项排序listorder设定问题修改,主要修改了三个文件三处地方. 主要修改三个文件: .phpcms\modules\vote\templates\vote_edit ...

  3. java&period;lang&period;OutOfMemoryError&colon; PermGen space

    Exception in thread ""http-bio-8080"-exec-1" java.lang.OutOfMemoryError: PermGen ...

  4. SQLite函数详解之二

    sqlite3支持的数据类型: NULL.INTEGER.REAL.TEXT.BLOB 但是,sqlite3也支持如下的数据类型 smallint           16位整数 integer    ...

  5. js模仿jquery里的几个方法next&comma; pre&comma; nextAll&comma; preAll

    /*siblings函数, 选取node的所有兄弟节点*/ function siblings(node){ if(node.nodeType === 1){ node.flag = true; // ...

  6. Webfrom基础知识

    MyBeNASP.NET内置对象 (1)简述ASP.NET内置对象. 答:ASP.NET提供了内置对象有Page.Request.Response.Application.Session.Server ...

  7. 【原创】Easyui tree filter 过滤本地数据无效的原因

    Easyui tree filter 过滤本地数据无效的解决方式    正确使用方式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ...

  8. Springboot系列文章

    一.springboot简介1.前世今生 在boot没有出现之前,基于spring的开发,常常需要配置大量的xml文件.工程狮们苦不堪言,渐渐厌倦了配置文件的复制黏贴.spring家族因为这件事,也经 ...

  9. 慢查询日志工具mysqlsla的使用

    安装mysqlsla源码路径:https://github.com/daniel-nichter/hackmysql.com源码存放路径:/usr/local/src1.获取源码如果没有git命令,请 ...

  10. Maven &period;m2&bsol;repository&bsol;jdk&bsol;tools&bsol;1&period;7 missing

    在pom.xml文件中加入: <dependency> <groupId>jdk.tools</groupId> <artifactId>jdk.too ...