題意：兩個人在有向上進行博弈，先手先下，后手在睡覺，所以后手由先手代下，每個人每次要沿著邊移動，不能移動的人輸，問最后先手是贏還是輸還是平局，贏的話輸出路徑

題解：兩個人進行博弈，先手幫后手下，所以先手的優勢更大，只要從開始點經過環，那么先手不可能輸

現在先考慮先手贏，從開始點直接搜就可以了，有環會進入死循環，所以一個點標記開始點到這個點步數的奇偶，如果走到這個點為奇數，而奇數被標記，那么就可以不繼續搜這個點了

先手平局的情況是先手不能贏，而且能從開始點走到環

剩下的情況就是輸了

#include <bits/stdc++.h> #define maxn 100010 #define INF 0x3f3f3f3f using namespace std; vector<int >G[maxn], ans; int dp[maxn][2], pre[maxn][2], out[maxn], n, m, t, a, flag = 0; bool vis[maxn]; void dfs(int x, int l) {vis[x] = true;for(int to : G[x]){if(pre[to][l^1]==0) {pre[to][l^1] = x;dfs(to, l^1);}if(vis[to]) flag = 1;}vis[x] = false; } int main(){scanf("%d%d", &n, &m);for(int i=1;i<=n;i++){scanf("%d", &t);while(t--){scanf("%d", &a);G[i].push_back(a);out[i]++;}}scanf("%d", &t);pre[t][0] = -1;dfs(t, 0);for(int i=1;i<=n;i++){if(out[i] == 0&&pre[i][1]){printf("Win\n");t = 1;while(i!=-1){ans.push_back(i);i = pre[i][t];t ^= 1;}for(int i=ans.size()-1;i>=0;i--)printf("%d ", ans[i]);return 0;}}if(flag) printf("Draw\n");else printf("Lose\n");return 0; }

?

轉載于:https://www.cnblogs.com/Noevon/p/8596540.html

總結

以上是生活随笔為你收集整理的Codeforces937D Sleepy Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。