codeforces 1451D,一道有趣的博弈论问题

codeforces 1451D,一道有趣的博弈论问题

首页角色扮演腾讯Code-D更新时间:2024-07-30

大家好,欢迎来到codeforces专题。

今天选择的问题是Contest 1451场的D题,这是一道有趣简单的伪博弈论问题,全场通过的人有3203人。难度不太高,依旧以思维为主,坑不多,非常友好。

题目链接:https://codeforces.com/contest/1451/problem/D

废话不多说,我们直接来看问题。

题意

从前有两个人,一个叫Utkarsh,另外一个叫Ashish。这两个名字看起来有点怪,我猜可能出题人是老毛子的原因,老毛子的问题当中这两个名字经常出现。也许类似于我们的小红、小明这样的名字吧。

这两个人在一个2D的棋盘上玩移动棋子的游戏,一开始从原点出发,Ashish先手。每次可以把棋子向上或者是向右移动k个单位的距离。两人交替移动,游戏规定棋子距离原点的距离必须要小于d。当有人移动不了棋子的时候落败。

现在给出d和k,要求在两人都智商爆表的情况下,谁会获胜。

样例

首先输入一个整数t,表示测试数据的组数。接着输入t行,每行代表一个样例。每一行输入两个整数,分别代表d(1 <= d <= 1e5)和k(1 <= k <= d)。

要求输出胜者的名字。

关于第一个样例的解释:

我们可以发现当两人轮流执行一个回合之后,Ashish一定无路可去,所以胜者是Utkarsh。

题解

一拿到手,我们会很自然地觉得这是一道博弈论的问题。

实际上看起来也非常像,两个人轮流游戏,包括游戏的一些细节,轮流移动,不能移动者落败,都很符合博弈论问题的特征。从博弈论入手的话,我们会想到必败态和必胜态之间的转化。

我们进一步分析的话,也不难想到思路。我们把这个平面想象成一个用一个扇形笼罩的区域,对于靠近扇形边境上的点,只有我们知道了坐标,就可以计算出来从原点出发到达这里需要的步数,步数知道了自然也就知道了最终是哪一个人落在了这个点。

这样我们首先确定下来边境的胜负状况之后,我们就可以逐渐往内层倒推,最终求解出原点的状态。这个推导的转移非常容易想明白,对于每个点来说它最多只有向右和向上两条路,对于该点做决策的人来说,只要这两个决策当中有一个能够到达自己的必胜态,那么该点自然也是必胜态。这其实有点动态规划的思想了,通过这种方法,我们可以求解出平面上每一个能够达到的点的状态。

看似这个问题就已经做完了,非常简单,但是我们稍微分析一下就会发现这样是不行的。道理也很简单,因为复杂度太大,会超时

极端情况下当d的量级是1e5,并且k=1的时候,我们需要考虑的点的数量应该在1e10这个量级,这显然是不能接受的。那除了这个办法之外还有其他方法可行吗?

很多时候看似问题很难解决,往往是我们走错了路。我们一直想着怎么递推,怎么获取每个点的状态,其实一开始这个思路就错了。这个时候需要我们把这些念头放一放,回归到问题本身。

我们把自己代入先手的玩家,我们会想出什么策略?你会发现好像一时半会也没什么特别好的策略?但如果我们是后手玩家呢?你会发现好的策略可能没有,但是赖皮的套路却是存在的。因为这个扇形是一个四分之一圆,它是对称的。所以我们可以利用后发的优势镜像先手的行动,先手往上我们往右,先手往右我们往上,这样我们可以保证我们的点始终落在斜对角线。这样只要先手可以前进,那么后手就一定可以移动。也就是顺着下图的路线移动。

那这样岂不是先手必输吗?其实也不是的,也有例外。就是当后手无法回到斜线的时候,也就是说((x 1)k, xk)距离原点小于d,而((x 1)k, (x 1)k)大于d的时候。

这样我们就可以很方便写出代码:

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<cmath> #include<cstdlib> #include<string> #include<map> #include<set> #include<algorithm> #include"time.h" #include<functional> #definerep(i,a,b)for(inti=a;i<b;i ) #defineRep(i,a,b)for(inti=a;i>b;i--) #defineforeach(e,x)for(__typeof(x.begin())e=x.begin();e!=x.end();e ) #definemid((l r)>>1) #definelson(k<<1) #definerson(k<<1|1) #defineMEM(a,x)memset(a,x,sizeofa) #defineLch[r][0] #defineRch[r][1] constintN=1000050; constlonglongMod=1000000007; usingnamespacestd; intmain(){ intt; scanf("%d",&t); rep(z,0,t){ longlongd,k; scanf("%lld%lld",&d,&k); intn=d/(sqrt(2)*k); longlongx=(n 1)*k; longlongy=n*k; //判断是否会出现((x 1)k,xk)可行的情况 if(x*x y*y>d*d){ puts("Utkarsh"); }else{ puts("Ashish"); } } return0; }

这里有一个小小的坑,就是由于d的范围是1e5,那么当我们计算距离的时候由于用到平方会超过int的范围,所以需要改成long long。

这道题到这里就结束了,我们也可以看得出来,题目本身是不难的,但是解法没有那么容易想到。我个人觉得挺有意思的,希望大家也会喜欢。

今天的文章就到这里,衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话,请来一个三连支持吧~(点赞、关注、转发

本文始发于公众号:TechFlow,求个关注

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved