大家好,欢迎来到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