首页 > 代码库 > codeforce gym 100548H The Problem to Make You Happy
codeforce gym 100548H The Problem to Make You Happy
题意：
Alice和Bob在一个有向图上玩游戏，每个人各自操作一个棋子，如果两个棋子走到一个点上，判定Bob输；如果轮到任何一方走时，无法移动棋子，判定该方输
现在Bob先走，要求判断胜负
题解
模型上看是SG问题，但是通常的SG做法需要DP，但是考虑这不是DAG模型，普通的记忆化搜索写法会RE
正解的DP做法：dp[i][j][k]：i,j是Bob,Alice的位置，k是目前轮到谁走了。
开始将所有显然的Bob输的情况加入队列中，不断拓展，找到所有的Bob输的情况。
转移类似SG
#include<bits/stdc++.h>#define clr(x,y) memset((x),(y),sizeof(x))using namespace std;typedef long long LL;const int maxn=100;struct Node{ int x1,x2; int turn; // 0:Bob 1:Alice};int n,m;int a,b;int num[maxn+5][maxn+5];int deg[maxn+5];bool mp[maxn+5][maxn+5];bool dp[maxn+5][maxn+5][2];queue <Node> Q;void solve(int iCase){ while (!Q.empty()) Q.pop(); int u,v; clr(mp,0); clr(deg,0); for (int i=1;i<=m;++i) { scanf("%d%d",&u,&v); ++deg[u]; mp[u][v]=true; } scanf("%d%d",&a,&b); clr(dp,-1); for (int i=1;i<=n;++i) { dp[i][i][0]=false; dp[i][i][1]=false; Q.push((Node){i,i,0}); Q.push((Node){i,i,1}); } for (int i=1;i<=n;++i) { if (deg[i]==0) { for (int j=1;j<=n;++j) { if (i==j) continue; dp[i][j][0]=false; Q.push((Node){i,j,0}); } } } clr(num,0); while (!Q.empty()) { Node now=Q.front(); Q.pop(); int x1=now.x1; int x2=now.x2; int turn=now.turn; if (turn==0) { for (int i=1;i<=n;++i) { if (mp[i][x2]) { if (!dp[x1][i][1]) continue; dp[x1][i][1]=false; Q.push((Node){x1,i,1}); } } } else { for (int i=1;i<=n;++i) { if (mp[i][x1]) { ++num[i][x2]; if (num[i][x2]==deg[i]) //如果从i出发的所有的状态都是必败态，那么dp[i][x2][0]本身也是必败态 { if (!dp[i][x2][0]) continue; dp[i][x2][0]=false; Q.push((Node){i,x2,0}); } } } } } if (dp[a][b][0]) printf("Case #%d: Yes\n",iCase); else printf("Case #%d: No\n",iCase);}int main(void){ #ifdef ex freopen ("../in.txt","r",stdin); //freopen ("../out.txt","w",stdout); #endif int T; scanf("%d",&T); for (int i=1;i<=T;++i) { scanf("%d%d",&n,&m); solve(i); }}
codeforce gym 100548H The Problem to Make You Happy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。