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