EOJ 3495. 无聊的游戏

题目链接https://acm.ecnu.edu.cn/problem/3495/

题意:略。

思路:只有20个点可以进行状压,然后记忆化搜索所有局面是必胜点还是必败点即可,1即代表这一位上该点还未被删除,如果这个点相邻的所有点跟当前局面相与为0的话说明这个点所有相邻的点都被删除了即这个点度数为0是不能删的,否则就删除这个点然后继续往下搜索。时间复杂度O(n2^n)

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define ALL(x) (x.begin(),x.end())
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=20+5;
int n,i,j,u,v,dp[(1<<20)+5];
int e[N];
int dfs(int state){
    if (dp[state]) return dp[state];
    for (int i=0;i<n;i++){
        if ((state&(1<<i))&&(e[i]&state)){
            if (dfs(state^(1<<i))==-1) return dp[state]=1;
        }
    }
    return dp[state]=-1;
}
int main(){
    read(n);
    for (i=1;i<n;i++){
        read(u),read(v);
        u--,v--;
        e[u]|=(1<<v);
        e[v]|=(1<<u);
    }
    puts(dfs((1<<n)-1)==1?"First":"Second");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注