D. Circle Game 题解(对称博弈)

题目链接

题目大意

t组数据(t<=100)

给你一个半径d和步数k,你最开始在原点(0,0)每次可以让x坐标增加k，或者y坐标增加k

两人轮流走，求谁最后不能走了，谁就输了，都是最优博弈

输的条件为下次走的坐标(x,y)都满足\(x^2+y^2>d^2\)

题目思路

就是一个对称博弈

求最远的到达的(kz,kz)使得\((kz)^2+(kz)^2<=d^2\)

如果\((kz)^2+(kz+k)^2<=d^2\) 则先手胜，否则后手胜

因为后手一定有办法使得坐标变为(kz,kz)，而这个点若不能走，则后手胜

若这个点能走，则先手一定可以到底(kz,kz+k)则这个点可以走的点为(kz+k,kz+k)和(kz,kz+2k)

显然都已经出界，则先手胜

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=400+5,inf=0x3f3f3f3f,mod=1e9+7;

const double eps=1e-5;

ll d,k;

int main(){

    int _; scanf("%d",&_);

    while(_--){

        cin>>d>>k;

        ll x=0;

        while((x+k)*(x+k)+(x+k)*(x+k)<=d*d){

            x+=k;

        }

        if((x+k)*(x+k)+x*x<=d*d){

            printf("Ashish\n");

        }else{

            printf("Utkarsh\n");

        }

    }

    return 0;

}

巴特西

D. Circle Game 题解(对称博弈)

题目链接

题目大意

题目思路

代码

最新文章

热门文章