常用网站缩略图自定义,泉州建设人才网站,做恒指网站,wordpress初始化题意#xff1a; Alice和Bob在一个有向图上玩游戏#xff0c;每个人各自操作一个棋子#xff0c;如果两个棋子走到一个点上#xff0c;判定Bob输#xff1b;如果轮到任何一方走时#xff0c;无法移动棋子#xff0c;判定该方输 现在Bob先走#xff0c;要求判断胜负 题解…题意 Alice和Bob在一个有向图上玩游戏每个人各自操作一个棋子如果两个棋子走到一个点上判定Bob输如果轮到任何一方走时无法移动棋子判定该方输 现在Bob先走要求判断胜负 题解 模型上看是SG问题但是通常的SG做法需要DP但是考虑这不是DAG模型普通的记忆化搜索写法会RE 正解的DP做法dp[i][j][k]i,j是Bob,Alice的位置k是目前轮到谁走了。 开始将所有显然的Bob输的情况加入队列中不断拓展找到所有的Bob输的情况。 转移类似SG #includebits/stdc.h#define clr(x,y) memset((x),(y),sizeof(x))using namespace std;
typedef long long LL;const int maxn100;struct Node
{int x1,x2;int turn; // 0:Bob 1:Alice
};int n,m;
int a,b;
int num[maxn5][maxn5];
int deg[maxn5];
bool mp[maxn5][maxn5];
bool dp[maxn5][maxn5][2];
queue Node Q;void solve(int iCase)
{while (!Q.empty()) Q.pop();int u,v;clr(mp,0);clr(deg,0);for (int i1;im;i){scanf(%d%d,u,v);deg[u];mp[u][v]true;}scanf(%d%d,a,b);clr(dp,-1);for (int i1;in;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 i1;in;i){if (deg[i]0){for (int j1;jn;j){if (ij) continue;dp[i][j][0]false;Q.push((Node){i,j,0});}}}clr(num,0);while (!Q.empty()){Node nowQ.front();Q.pop();int x1now.x1;int x2now.x2;int turnnow.turn;if (turn0){for (int i1;in;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 i1;in;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 exfreopen (../in.txt,r,stdin);//freopen (../out.txt,w,stdout);#endifint T;scanf(%d,T);for (int i1;iT;i){scanf(%d%d,n,m);solve(i);}
} 转载于:https://www.cnblogs.com/123-123/p/5862357.html
