题目链接:uva 11927 - Games Are Important
题目大意:给出一张无环有向图,并给出每个节点上的石子数,每次操作可以选择一个石子,向下一个节点移动。两人轮流操作,直到不能操作为失败者。
解题思路:有了图之后,用记忆化的方式处理出每个节点的SG值,取所有石子数为奇数的节点的Nim和。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int N, M, g[maxn][maxn], c[maxn], s[maxn];
inline int SG(int u) {
if (s[u] != -1)
return s[u];
int vis[maxn];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < c[u]; i++) {
int tmp = SG(g[u][i]);
vis[tmp] = 1;
}
int ret = -1;
while (vis[++ret]);
return s[u] = ret;
}
void init () {
int u, v;
memset(s, -1, sizeof(s));
memset(c, 0, sizeof(c));
for (int i = 0; i < M; i++) {
scanf("%d%d", &u, &v);
g[u][c[u]++] = v;
}
for (int i = 0; i < N; i++)
s[i] = SG(i);
}
int main () {
while (scanf("%d%d", &N, &M) == 2 && N + M) {
init();
int ans = 0, u;
for (int i = 0; i < N; i++) {
scanf("%d", &u);
if (u&1)
ans ^= s[i];
}
printf("%s\n", ans ? "First" : "Second");
}
return 0;
}
分享到:
相关推荐
CPP中的Postfix-Tree-Calculator:在C ++中实现后缀树计算器。 包括来自UVA CS部门的测试C ++文件
UVa写入 使用C ++编写UVa OJ: : 等级 基于 ★★ ★★ ★★★ ★★★★ ★★★★★ 未排名
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
programming-problems:使用C ++,Rust,C或Python解决方案来解决不同竞争编程平台的问题
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
uva532 Dungeon Master的源代码,并且AC了