题解：CF69D Dot

Lijunzhuo · 2025-10-28 19:50:56 · 题解

简单搜索题。

我们可以发现，翻转操作无意义。因为如果你翻转后必输，对手会毫不犹豫的再翻转回去。否则对手会不翻转，去拼那一线生机。

然后再根据“如果操作后对方怎么选都不能胜则必胜，否则必败”搜索即可。

代码：

#include<bits/stdc++.h>
#define f(x,y) F[x+250][y+250]
#define int long long
using namespace std;
const int N=21,M=1000;
int x,y,n,d,dx[N],dy[N],F[M][M];
bool DFS(int x,int y)
{
    if(x*x+y*y>d*d) return true;
    if(f(x,y)!=-1) return f(x,y);
    f(x,y)=0;
    for(int i=1;i<=n;i++)
    {
        if(!DFS(x+dx[i],y+dy[i]))
        {
            f(x,y)=true;
            break;
        }
    }
    return f(x,y);
}
signed main()
{
    scanf("%lld%lld%lld%lld",&x,&y,&n,&d);
    memset(F,-1,sizeof(F));
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&dx[i],&dy[i]);
    printf("%s\n",DFS(x,y)?"Anton":"Dasha");
    return 0;
}

然后就过了。