【刷题】BZOJ 1413 [ZJOI2009]取石子游戏_weixin_30435261的博客-程序员宅基地

技术标签: ui  

Description

在研究过Nim游戏及各种变种之后,Orez又发现了一种全新的取石子游戏,这个游戏是这样的: 有n堆石子,将这n堆石子摆成一排。游戏由两个人进行,两人轮流操作,每次操作者都可以从最左或最右的一堆中取出若干颗石子,可以将那一堆全部取掉,但不能不取,不能操作的人就输了。 Orez问:对于任意给出一个初始一个局面,是否存在先手必胜策略。

Input

文件的第一行为一个整数T,表示有 T组测试数据。对于每组测试数据,第一行为一个整数n,表示有n堆石子;第二行为n个整数ai,依次表示每堆石子的数目。

Output

对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略,0表示没有。

Sample Input

1  
4  
3 1 9 4  

Sample Output

0  

数据范围

对于30%的数据 n≤5 ai≤105

对于100%的数据 T≤10 n≤1000 每堆的石子数目≤109

Solution

重要性质:

  • 对于一段区间 \([L,R]\) ,若 \(L+1\)\(R\) 的石子固定,那么让当前先手在这段区间上必败的 \(a_L\) 有且只有一个。 \pause

证明唯一:如果有两个必败态,那么由于其中一个必败态可以转移到另一个必败态,与定义矛盾,所以只会有一个必败态

证明存在:如果左边没有必败态,那么左边所有的必胜态都由右边的必败态转移过来。由于左边的石子可以有任意多个,但右边的石子是固定的,所以会有石子对应多个必败态,这与唯一性矛盾

根据这两条性质,得出一个做法

\(L[i][j]\) 代表区间 \([i,j]\) 左边加上一堆数量为 \(L[i][j]\) 的石子后先手必败;\(R[i][j]\) 定义相似,代表右边

最后只要判断 \(L[2][n]\) 是否等于 \(a[1]\) 就知道先手是否有必胜策略

考虑计算这两个数组:发现 \(L[i][j]\) 只与 \(L[i][j-1],R[i][j-1]\)\(a[j]\) 有关

\(l=L[i][j-1],r=R[i][j-1],x=a[j]\)

分情况讨论

  • 边界条件,\(L[i][i]=R[i][i]=a[i]\)

  • \(r=x\) ,已经确定先手必败,\(L[i][j]=0\)

  • \(x \le l\)\(x \le r\)\(L[i][j]=x\) 。后手要做的就是在另一边取与先手一样数量的石子,这样先手一定先取完一堆。假设先手取完的是右边一堆,那么根据我们的 \(l=L[i][j-1]\) ,含义是区间 \([i,j-1]\) 左边加上数量为 \(l\) 的石子先手必败,可以把当前局面等价于先手已经把数量为 \(l\) 的这堆石子取了一些了,所以先手必败

  • \(r \le x \leq l\)\(L[i][j]=x-1\) 。假设先手拿的左边一堆,拿到 \(y\) 个。若 \(y \le r\) ,那么后手在右边一堆也拿到 \(y\) 个,变成上面一种情况;若 \(y > r\) ,那么后手拿到 \(y+1\) ,变成当前情况递归。假设先手拿右边一堆,拿到 \(y\) 个。若 $ y \le r$ 那么后手在左边一堆也拿到 \(y\) 个,变成上面一种情况;若 \(y=r\) ,后手直接取完左边一堆,由于 \(R[i][j-1]=r\) ,所以先手必败;若 \(y > r\) ,那么后手将左边一堆取到 \(y-1\) ,变成这种情况递归。无论何种走向,最后只能是先手必败

  • \(l \le x \leq r\)\(L[i][j]=x+1\) 。类似于上面一种情况

  • \(x > l\)\(x > r\)\(L[i][j]=x\) 。假设先手取其中一堆到 \(y\) 个。若 \(y > l,r\) ,那么变成这种情况递归;若 \(y \le l,r\) ,那么变成第二种情况;剩下的情况后手相应取到 \(y+1\)\(y-1\) ,变成上面两种情况中的一种就好了

\(L[i][j]\) 的所有情况都讨论完了,\(R[i][j]\) 的求法类似。

复杂度 \(O(Tn^2)\)

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define ft first
#define sd second
#define pb(a) push_back(a)
#define PII std::pair<int,int>
#define PLL std::pair<ll,ll>
#define mp(a,b) std::make_pair(a,b)
#define ITR(a,b) for(auto a:b)
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=1000+10;
int n,a[MAXN],L[MAXN][MAXN],R[MAXN][MAXN];
template<typename T> inline void read(T &x)
{
    T data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')putchar(ch);
}
template<typename T> inline bool chkmin(T &x,T y){return y<x?(x=y,true):false;}
template<typename T> inline bool chkmax(T &x,T y){return y>x?(x=y,true):false;}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
int main()
{
    int T;read(T);
    while(T--)
    {
        int n;read(n);
        REP(i,1,n)read(a[i]),L[i][i]=R[i][i]=a[i];
        REP(len,2,n)REP(i,1,n-len+1)
        {
            int j=i+len-1,l,r,x;
            l=L[i][j-1],r=R[i][j-1],x=a[j];
            if(r==x)L[i][j]=0;
            else if(r<x&&x<=l)L[i][j]=x-1;
            else if(l<x&&x<=r)L[i][j]=x+1;
            else L[i][j]=x;
            l=L[i+1][j],r=R[i+1][j],x=a[i];
            if(l==x)R[i][j]=0;
            else if(l<x&&x<=r)R[i][j]=x-1;
            else if(r<x&&x<=l)R[i][j]=x+1;
            else R[i][j]=x;
        }
        puts(L[2][n]==a[1]?"0":"1");
    }
    return 0;
}

转载于:https://www.cnblogs.com/hongyj/p/10542695.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30435261/article/details/97299521

智能推荐

计算机网络的物理层特性,计算机网络物理层的特性 -华强电子网_回忆的眼泪的博客-程序员宅基地

物理层接口有四个技术特性:1.机械特性:规定了物理连接时接口所需连接插件的形状、规格尺寸、引脚数量、排列情况以及固定和锁定装置等。2.电气特性:规定了DTE和DCE间导线的电气连接及有关电路方面的特性。DTE和DCE之间各根导线的电气连接方式有:非平衡方式、采用差动接收器的非平衡方式、平衡方式。3.功能特性:定义了DTE和DCE间各信号线的功能,即某条信号线上出现的某一电平的电压表示何种确切含义。...

Linux日程管理课程设计,Linux课程设计shell编程.doc_小舜利的博客-程序员宅基地

参考文献课 程 设 计 报 告课程名称 Linux操作系统课程设计指导教师 张玲起止日期 2014-03-01实验项目 实验三 Shell编程学 院 信息与通信工程学院专 业 电子信息工程学生姓名班级/学号成 绩指导老师签字课程设计概述理解Shell程序的执行环境和执行过程,掌握Shell语言的一般语法规则,能用...

分组查询和条件查询【having和where】_萌新小灯笼(英文IDfengmo)的博客-程序员宅基地

一.语法【分组查询】select 分组列名,聚合函数from 表名group by 分组列名 ;二.范例三.语法【条件查询having】1.语法select 分组列名,聚合函数from 表名group by 分组列名 having 条件查询条件2.注意事项所有条件查询不能使用列的别名。四.范例五.语法【条件查询where】1.语法select 分组列名,聚...

计算机网络专业现状,计算机网络的发展现状及网络体系结构涵义分析论文_袁浩瀚的博客-程序员宅基地

计算机网络的发展现状及网络体系结构涵义分析论文现阶段,计算机网络技术发生了飞速发展,计算机网络是计算机技术与通信技术结合的新科技,它能够远距离通信,还能够处理通信内容并实现资源共享等优点。计算机网络技术起源于20世纪60年代,迄今为止已经有大半个世纪的演变过程,在近年来发展尤其迅猛,其应用领域已经涉及到政治、经济、科技、军事、文化及日常生活中。一、计算机网络的发展现状计算机网络发展速度是飞速的,从...

storm-kafka示例详解_jinhong_lu的博客-程序员宅基地

(一)简介1、本项目完整代码请见https://github.com/jinhong-lu/stormkafkademo/tree/master/src/main/java/org/jinhong/demo/storm_kafka/trident。2、本项目主要完成以下功能:(1)从kafka中读取一个topic的消息,然后根据空格拆分单词,最后统计数据后写入一个HazelCastSt

linux上清空一个文件,技术|Linux 下清空或删除大文件内容的 5 种方法_冯妥坨的博客-程序员宅基地

在 Linux 终端下处理文件时,有时我们想直接清空文件的内容但又不必使用任何 Linux 命令行编辑器 去打开这些文件。那怎样才能达到这个目的呢?在这篇文章中,我们将介绍几种借助一些实用的命令来清空文件内容的方法。注意:在我们进一步深入了解这些方法之前,请记住: 由于在 Linux 中一切皆文件,你需要时刻注意,确保你将要清空的文件不是重要的用户文件或者系统文件。清空重要的系统文件或者配置文件可...

随便推点

input 中 checkbox与 radio的样式表 自定义样式_邪小新的博客-程序员宅基地

对于表单,input[type="radio"的样式总是不那么友好,在不同的浏览器中表现不一。思路:可以为元素添加生成性内容(伪元素),并基于单选按钮的状态来为其设置样式;然后把真正的单选按钮隐藏起来;最后把生成内容美化一下。 &lt;!DOCTYPE html&gt;&lt;html lang="en"&gt;&lt;head&gt; &lt;met...

637_AUTOSAR_AUTOSAR_TR_Glossary_文档阅读7_小灰笔记-程序员宅基地

全部学习汇总: https://github.com/GreyZhang/hack_autosar 继续看《AUTOSAR_AUTOSAR_TR_Glossary》,进入到下半场了。一件事情,只要是过了一半总会让我感到心情的轻松感。接下来,应该会顺利,继续! 又是FlexRay的信息,看起来,这个协议涉及到的概念很多啊。兴许,会是一个比CAN还让人头疼的通信。这里的这个概念,应该是一个数据包的ID。 SDU一般都是用于服务的,但是这里竟然没有服务的概念。 与CAN矩阵可能还不是同一个概念,这个看...

PostgreSQL字段类型说明_cyuyan的专栏-程序员宅基地_postgresql字段类型

PostgreSQL字段类型说明已有 817 次阅读  2009-02-25 22:49   标签:  PostgreSQL  字段  类型  BIGSERIALSERIAL8 存储自动递增的惟一整数,最多 8 字节。BIT 固定长度的位串。BIT VARYING(n)VARBI

6、通道(Channels)_昉钰的博客-程序员宅基地

本节介绍通道----Channels(官方文档)Deferred values提供了一种在协程之间传递单个值的简便方式,通道(channels)则提供了在协程间传递流的方法。1、Channel basics熟悉Java的读者应该都知道阻塞队列BlockingQueue,而这里说的通道在概念上则与BlockingQueue非常相似,一个重要的区别是通道使用的是suspend的send方法存储数据而BlockingQueue使用的是阻塞的put方法,同时在取数据的时候通道使用的是suspend的re

制作一个钟表html,用html5实现一个简单的钟表外观_知乎生活的博客-程序员宅基地

html5已经出来好长时间了,但仍然有不多小伙伴们不太懂,下面小编就来用html5实现一个简单的钟表外观 #myCanvas{border:3px solid blue;} window.onload = function() { var mycanvas = document.getElementById("myCanvas"); var context = mycan...

推荐文章

热门文章

相关标签