题解：CF1451D Circle Game

ssy666666 · 2026-07-21 14:37:20 · 题解

正确解法

这种博弈论的题有一个共同的经典套路：看看哪些点是必败点，哪些是必胜点。

以这个半径为 3 的圆为例，如果一个点无法移动，则它显然是必败点；如果一个点能够到达必败点，即可以让他的对手必败，则这个点是必胜点；如果一个点到达的点都是必胜点，那么这个点必然是必败点。

由此，我们可以画一下。下图中，圆代表必败点，方框表示必胜点。

看起来，圆点总是四十五度斜着排列，事实上，这是正确的。我们来证明一下。

我们先只看最外圈一层点，首先，显然不可能有两个相邻的点都是圆点，不然肯定有一个圆点可以到达另一个圆点，和我们之前的分析相反。

因此，排除了其他圆点影响，这个点的下方和左方肯定是方点。因此，这个圆点左下的点肯定是圆点。

好的，接下来，我们再次看到最外层。可以发现，如果一个点右方和上方没有点，那么这个点肯定是圆点。反之，如果他的右方/上方有偶数个点，他一定是圆点，看图结合刚才的证明很容易得到这个结论。

但是我们只用关注斜向上 45 度的最外层的点。由圆的对称性可知，我们随便选一边看一下即可。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;

void solve() {
    int d , k ;
    cin >> d >> k ;

    int x = 0 , y = 0 ;
    while (1) {
        x += k ;
        y += k ;

        if (x * x + y * y > d * d) {
            x -= k ;
            y -= k ;
            break ;
        }
    }

    int cnt = 0 ;

    int dx = x , dy = y ;
    while (1) {
        dx += k ;
        cnt ++ ;

        if (dx * dx + dy * dy > d * d) {
            dx -= k ;
            cnt -- ;
            break ;
        }
    }

    if (cnt % 2 == 0) {
        cout << "Utkarsh\n" ;
    }
    else {
        cout << "Ashish\n" ;
    }
    return ;
}

signed main() {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int t ;
    cin >> t ;
    while (t--) {
        solve() ;
    }

    return 0 ;
}