P9862 [CCC 2008 J5/S5] Nukit 题解

ivyjiao · 2023-11-17 09:51:39 · 题解

其实题面少了一句话：假设两人都足够聪明，我们给它加上。

首先，在博弈中，我们明确三个性质：

• 如果一个状态的后继有一个必败状态，则该状态为必胜状态。
• 如果一个状态的后继全都是必胜状态，则该状态为必败状态。
• 不能再取的状态为必败状态（即：不能再取的状态的后继全都是必胜状态）。

一般的博弈论题都是可以通过这两条从 (0,0) 递推出所有状态的，然而这道题每个状态不仅给了四个点，还有五种转移式，根本无法转移。但是数据范围很小，所以我们考虑爆搜加记忆化。

不知道为什么清空 dp 数组的时候不能用 memset，我在这里寄了十分钟。

根据以上性质，我们可以写出这样一份代码：

#include<bits/stdc++.h>
using namespace std;
int t,a,b,c,d,dp[31][31][31][31];
bool dfs(int a,int b,int c,int d){
    if(a<0||b<0||c<0||d<0) return 1;//不能再取的状态的后继全都是必胜状态
    if(dp[a][b][c][d]!=-1) return dp[a][b][c][d];
    if(dfs(a-2,b-1,c,d-2)&&dfs(a-1,b-1,c-1,d-1)&&dfs(a,b,c-2,d-1)&&dfs(a,b-3,c,d)&&dfs(a-1,b,c,d-1)) dp[a][b][c][d]=0;//如果一个状态的后继全都是必胜状态，则该状态为必败状态。
    else dp[a][b][c][d]=1;//如果一个状态的后继有一个必败状态，则该状态为必胜状态。
    return dp[a][b][c][d];
}
int main(){
    cin>>t;
    while(t--){
        for(int i=0;i<=30;i++) for(int j=0;j<=30;j++) for(int k=0;k<=30;k++) for(int l=0;l<=30;l++) dp[i][j][k][l]=-1;
        cin>>a>>b>>c>>d;
        if(dfs(a,b,c,d)) cout<<"Patrick"<<endl;
        else cout<<"Roland"<<endl;
    }
}