A. Berzerk（cf786A) （水）

标签：pre now int dfs 必胜 Berzerk cf786A dp

A. Berzerk（cf786A)

tag：记忆化搜索 博弈

题目链接

题意：

有n个星球，编号从0到n-1围成一个圈，某颗星球上有只怪兽
Rick和Morty轮流操作，他们各有一个集合，每轮可以从自己的集合中选一个数x，使得怪物顺时针走x步,若使怪物走到了编号为0的星球就胜利
现在你需要判断所有情况下（枚举谁先手，怪物原本在哪个星球)的胜负情况，或判断是否谁也赢不了

做法：

首先我们知道必胜态一定能转移到一个必败态，而必败态无论怎么转都只能到必胜态
也就是说 必败态的上一个状态一定是必胜态，我们倒着随便转移即可，而如何确定当前是一个必败态我们需要确认每种转移后是否都是必胜态
我们设 dp[2][N]，表示谁先手，怪兽当前在哪个位置，胜负情况。

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const int mod=998244353;
int dp[2][N],win[2][N];
vector<int> a[2];
int n;

void dfs(int u,int now) {
	
	int v=u^1; 
    if(dp[u][now]==0){
        for(auto i: a[v]){
            int pre = (now-i+n)%n;
            if(dp[v][pre]!=-1) continue;
            dp[v][pre]=1;
            dfs(v,pre);
        }
    }
    else{
        for(auto i: a[v]){
            int pre = (now-i+n)%n;
            if(dp[v][pre]!=-1) continue;
            win[v][pre]++; //统计转移后必胜态的个数
            if(win[v][pre]==a[v].size()){
                dp[v][pre] = 0;
                dfs(v,pre);
            }
        }
    }
}


int main() {
    cin>>n;
    int x,k;
    cin>>k; 
    for(int i=1;i<=k;i++) cin>>x,a[0].push_back(x);
    cin>>k;
    for(int i=1;i<=k;i++) cin>>x,a[1].push_back(x);

    memset(dp,-1,sizeof(dp));
    dp[0][0] = dp[1][0] = 0;
    dfs(0,0),dfs(1,0);

    for(int i=0;i<2;i++){
        for(int j=1;j<n;j++){
            if(dp[i][j]==-1) cout<<"Loop"<<" ";
            if(dp[i][j]==0) cout<<"Lose"<<" ";
            if(dp[i][j]==1) cout<<"Win"<<" ";
        }
        cout<<le;
    }

    return 0;
}

标签：pre,now,int,dfs,必胜,Berzerk,cf786A,dp
From： https://www.cnblogs.com/touchfishman/p/17071498.html