1665：【例 3】移棋子遊戲
時間限制: 1000 ms 記憶體限制: 524288 KB
【題目描述】
給定一個有 N 個節點的有向無環圖，圖中某些節點上有棋子，兩名玩家交替移動棋子。
玩家每一步可将任意一顆棋子沿一條有向邊移動到另一個點，無法移動者輸掉遊戲。
對于給定的圖和棋子初始位置，雙方都會采取最優的行動，詢問先手必勝還是先手必敗。
【輸入】
第一行，三個整數 N,M,K， N 表示圖中節點總數， M 表示圖中邊的條數， K 表示棋子的個數。
接下來 M 行，每行兩個整數 X,Y 表示有一條邊從 X 出發指向 Y。
接下來一行， K 個空格間隔的整數，表示初始時，棋子所在的節點編号。
【輸出】
若先手勝，輸出 win，否則輸出 lose。
【輸入樣例】
6 8 4
2 1
2 4
1 4
1 5
4 5
1 3
3 5
3 6
1 2 4 6 【輸出樣例】
win 【提示】
資料範圍與提示：
對于全部資料，N≤2000,M≤6000,1≤K≤N。
sol：圖中已經給出了一張拓撲圖，每個點走到不能走都有若幹個不同的步數，
暴力dfs 就可以求出SG值，詢問的時候異或起來就好了
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=0;
bool f=0;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<0)
{
putchar('-'); x=-x;
}
if(x<10)
{
putchar(x+'0'); return;
}
write(x/10);
putchar((x%10)+'0');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=2005,M=6005;
int n,m,k;
int SG[N];
namespace Picture
{
int tot=0,Next[M],to[M],head[N];
inline void add(int x,int y)
{
Next[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
bool Arr[N];
inline void dfs(int x)
{
if(Arr[x]) return;
Arr[x]=1;
int i,Up=0;
bool Mark[N]={0};
for(i=head[x];i;i=Next[i])
{
dfs(to[i]);
Up=max(Up,SG[to[i]]);
Mark[SG[to[i]]]=1;
}
for(i=0;i<=Up+1;i++) if(!Mark[i])
{
SG[x]=i; break;
}
}
inline void GetSG()
{
int i;
for(i=1;i<=n;i++) if(!Arr[i]) dfs(i);
return;
}
}
#define Pc Picture
int main()
{
int i,ans=0;
R(n); R(m); R(k);
for(i=1;i<=m;i++)
{
int x=read(),y=read();
Pc::add(x,y);
}
Pc::GetSG();
for(i=1;i<=k;i++) ans^=SG[read()];
(ans)?puts("win"):puts("lose");
return 0;
}
/*
input
6 8 4
2 1
2 4
1 4
1 5
4 5
1 3
3 5
3 6
1 2 4 6
output
win
*/ View Code
轉載于:https://www.cnblogs.com/gaojunonly1/p/10554640.html