【博弈论&&建模】 Candy Piles


题目描述:

【博弈论&&建模】 Candy Piles


S

o

l

u

t

i

o

n

Solution

Solution

我们形象的理解一下去糖果的过程是怎么样的。

首先,我们将原本无序的糖果排序一下变成有序的序列,这样子能够较好的处理取出石子最多这一操作,如下:
//这里借用一下atcoder的官方图片,以助于理解
【博弈论&&建模】 Candy Piles

然后我们模拟一下取糖果的效果。
如果是取走石子最多的一堆,实际上相当于消除最左边的一列:
【博弈论&&建模】 Candy Piles

如果是给每堆石子都取走一个,那么就是消除最下面的一行:
【博弈论&&建模】 Candy Piles

因此,我们将这样的操作形象理解之后可以发现,这样的操作要么是消除最左边的一列要么是消除最底下的一行。

接着我们抽象的将这样的情况转化为网格图:
【博弈论&&建模】 Candy Piles

将操作转化到网格图上,不难想到,消除最右边的一列,就是往右走一格;消除最下面的一行,就是往上走一格。

什么情况结束呢?走到边界就结束了,并且谁走到边界谁就输。

OK,我们重新回到题目上,题目上求的是是否必胜与必败,这是一道博弈。
我们给每个点都附上一个身份:必胜点与必败点。表示走到当前是必胜还是必败。
显然的,网格图的边界都是必败点。而对于一个点,只要他的右边或者上面有一个点是必败点,那么当前就是必胜点。如果他的右边以及上面都是必胜点,那么当前就是必败点。
这里用○表示必败点,×表示必胜点:
【博弈论&&建模】 Candy Piles

我们是从原点

(

0

,

0

)

(0,0)

(0,0)出发,下一步是先手。所以可以理解为后手此时处在原点。那么当原点是必胜点是,后手必胜,原点是必败点时,先手必胜。

但是,对于此题的数据范围而言,我们显然不能够将整个网格图的信息都记录下来。所以我们需要在上图的基础上寻找规律:
【博弈论&&建模】 Candy Piles

我们发现,除了边界点,每一条对角线上的点都是相同类型的。
因此,我们如果想要确定原点的类型是怎么样的,只要确定其对角线上的点的类型是怎么样的即可。
原点斜向上的对角线是45度对角线,所以我们是需要找到以原点左下角的最大正方形,设右上角为

(

i

,

i

)

(i,i)

(i,i):
【博弈论&&建模】 Candy Piles

如果当前

(

i

,

i

)

(i,i)

(i,i)到边界的一端的前一个点的距离为奇数,那么当前点就是必败点,即原点是必败点;反之原点就是必胜点。
到此,这道题就结束了!
十分巧妙的建模……


Code

??那么简单还不会写??

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【博弈论&&建模】 Candy Piles

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【博弈论&&建模】 Candy Piles
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏