P3480-[POI2009]KAM-Pebbles【阶梯博弈】
2024-08-31 06:41:44
正题
题目链接:https://www.luogu.com.cn/problem/P3480
题目大意
\(n\)个石头堆上进行\(\text{Nim}\)游戏,不过需要满足每次操作前后都有\(a_i\leq a_{i+1}(\ i\in[1,n)\ )\)
解题思路
让每一个\(b_i=a_i-a_{i-1}\)就是一个阶梯博弈问题了。
阶梯博弈问题:\(n\)堆石头,第\(i\)堆石头有\(a_i\)个,每次一个玩家可以取走若干个第一堆的石头,或者将第\(i\)堆的任意个石头丢到第\(i-1\)堆里面。
这个问题的\(sg\)函数就是编号为奇数的石头数量的异或和,具体证明的话就是如果只看奇数堆石头,那么转移奇数的堆里的石头就相当与去掉一些石头。所以如果奇数堆必胜的玩家一定会转移奇数堆的,因为如果后手转移偶数堆里的那么先手再把新的转走状态就不会改变。
所以直接做就好了,时间复杂度\(O(Tn)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1100;
int T,n,a[N];
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
a[i]=a[i]-a[i-1];
int ans=0;
for(int i=n;i>=1;i-=2)
ans^=a[i];
puts(ans?"TAK":"NIE");
}
return 0;
}
最新文章
- $_session (应用)
- 友盟推送 .NET (C#) 服务端 SDK rest api 调用库
- vs运行时候冒了这个错:无法启动IIS Express Web 服务器~Win10
- 从零自学Hadoop(01):认识Hadoop
- Intellj IDEA Java随笔
- OC编程的一些UI细节
- Java虚拟机7:内存分配原则
- 使用maven镜像
- Netbeans 中的编译器相关配置
- Codeforces Round #335 (Div. 1)--C. Freelancer&#39;s Dreams 线性规划对偶问题+三分
- 【转载】python:特殊函数使用方式
- YUI Array 之some(检测|any)
- selenium 学习笔记 ---新手学习记录(6) 问题总结(java)
- ASP.NET Zero--13.一个例子(6)商品分类管理-删除分类
- bzoj:1723: [Usaco2009 Feb]The Leprechaun 寻宝
- Maven的pom.xml文件结构之基本配置packaging和多模块聚合结构(微服务)
- tomcat 编码给为utf-8
- python web架构初步认识
- 【RFT】【环境配置】Mac
- Mybatis 系列10-结合源码解析mybatis 的执行流程