題意

從前有兩個人，一個叫Utkarsh，另外一個叫Ashish。
這兩個人在一個2D的棋盤上玩移動棋子的游戲，一開始從原點出發，Ashish先手。每次可以把棋子向上或者是向右移動k個單位的距離。兩人交替移動，游戲規定棋子距離原點的距離必須要小于d。當有人移動不了棋子的時候落敗。

現在給出d和k，要求在兩人都智商爆表的情況下，誰會獲勝。

樣例

首先輸入一個整數t，表示測試數據的組數。接著輸入t行，每行代表一個樣例。每一行輸入兩個整數，

要求輸出勝者的名字。

關于第一個樣例的解釋：

我們可以發現當兩人輪流執行一個回合之后，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> #define rep(i,a,b) for (int i=a;i<b;i++) #define Rep(i,a,b) for (int i=a;i>b;i--) #define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++) #define mid ((l+r)>>1) #define lson (k<<1) #define rson (k<<1|1) #define MEM(a,x) memset(a,x,sizeof a) #define L ch[r][0] #define R ch[r][1] const int N=1000050; const long long Mod=1000000007;using namespace std;int main() {int t;scanf("%d", &t);rep(z, 0, t) {long long d, k;scanf("%lld%lld", &d, &k);int n = d / (sqrt(2) * k);long long x = (n+1) * k;long long y = n * k;// 判斷是否會出現((x+1)k, xk)可行的情況if (x * x + y * y > d * d) {puts("Utkarsh");}else {puts("Ashish");}}return 0; }

這里有一個小小的坑，就是由于d的范圍是1e5，那么當我們計算距離的時候由于用到平方會超過int的范圍，所以需要改成long long。

這道題到這里就結束了，我們也可以看得出來，題目本身是不難的，但是解法沒有那么容易想到。我個人覺得挺有意思的，希望大家也會喜歡。

總結

以上是生活随笔為你收集整理的牛客网-数据结构笔试题目（三）-博弈论圆圈游戏（Circle Game）（附源码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。