NC50616. 移棋子游戏
描述
输入描述
第一行，三个整数N,M,K，N表示图中节点总数，M表示图中边的条数，K表示棋子的个数。
接下来M行，每行两个整数X,Y表示有一条边从X出发指向Y。
接下来一行，K个空格间隔的整数，表示初始时，棋子所在的节点编号。
输出描述
若先手胜，输出win，否则输出lose。
示例1
输入:
6 8 4 2 1 2 4 1 4 1 5 4 5 1 3 3 5 3 6 1 2 4 6
输出:
win
C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 1032K, 提交时间: 2023-02-19 10:29:39
#include<bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
vector<int> node[N];
set<int> se[N];
int sg[N];
int main(){
int n,m,k;
cin >> n >> m >> k;
vector<int> cnt(n+1);
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
node[b].push_back(a);
cnt[a] ++;
}
queue<int> qe;
for(int i=1;i<=n;i++)
if(cnt[i] == 0)
qe.push(i);
while(qe.size()){
int var = qe.front();
qe.pop();
while(se[var].count(sg[var]))sg[var]++;
for(int x:node[var]){
cnt[x]--;
se[x].insert(sg[var]);
if(cnt[x] == 0){
qe.push(x);
}
}
}
int ans = 0;
for(int i=1;i<=k;i++){
int x;cin >>x ;
ans ^= sg[x];
}
cout << (ans ? "win":"lose") <<"\n";
}
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 752K, 提交时间: 2020-02-16 17:13:16
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 7e3;
vector<int> G[MAXN];
int sg[MAXN];
int N, M, K;
void dfs(int s) {
if (sg[s] != -1) return;
set<int> S;
for (auto t: G[s]) {
dfs(t);
S.insert(sg[t]);
}
sg[s] = 0;
while (S.count(sg[s])) sg[s]++;
}
int main() {
cin >> N >> M >> K;
while (M--) {
int u, v; cin >> u >> v;
G[u].push_back(v);
}
memset(sg, -1, sizeof(sg));
for (int i = 1; i <= N; i++) dfs(i);
int ans = 0;
while (K--) {
int t; cin >> t;
ans ^= sg[t];
}
if (ans) cout << "win" << endl;
else cout << "lose" << endl;
}
Python3 解法, 执行用时: 507ms, 内存消耗: 36888K, 提交时间: 2021-12-13 13:20:39
f = [-1] * 2010
g = [[None] * 2010 for _ in range(2010)]
def sg(x, n):
if f[x] != -1:
return f[x]
s = set()
for i in range(1, n + 1):
if g[x][i]:
s.add(sg(i, n))
for i in range(0, 2011):
if i not in s:
f[x] = i
return f[x]
n, m, k = map(int, input().split())
for i in range(1, m + 1):
a, b = map(int, input().split())
g[a][b] = 1
res = 0
x = map(int, input().split())
for i in x:
res = res ^ sg(i, n)
if res:
print('win')
else:
print('lose')
C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 744K, 提交时间: 2020-06-02 20:42:44
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7e3;
vector<int> G[MAXN];
int sg[MAXN];
int N,M,K;
void dfs(int s)
{
if(sg[s]!=-1)
return;
set<int> S;
for(auto t:G[s])
{
dfs(t);
S.insert(sg[t]);
}
sg[s]=0;
while(S.count(sg[s]))
sg[s]++;
}
int main()
{
cin>>N>>M>>K;
while(M--)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
}
memset(sg,-1,sizeof(sg));
for(int i=1;i<=N;i++)
dfs(i);
int ans=0;
while(K--)
{
int t;
cin>>t;
ans^=sg[t];
}
if(ans)
cout<<"win"<<endl;
else
cout<<"lose"<<endl;
}