题目链接:uva 1378 - A Funny Stone Game
题目大意;两个人玩游戏,对于一个序列,轮流操作,每次选中序列中的i,j,k三个位置要求i<j≤k,然后arr[i]减1,相应的arr[j]和arr[k]加1,不能操作的人输,问先手是否必胜,必胜的话给出字典序最下的必胜方案,负责输出-1.
解题思路:首先预处理出各个位置上的SG值,然后对于给定序列,枚举位置转移状态后判断是否为必败态即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30;
int n, g[maxn], s[maxn];
int SG (int l) {
int vis[1000];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < l; i++) {
for (int j = 0; j < l; j++)
vis[g[i]^g[j]] = 1;
}
int ret = -1;
while (vis[++ret]);
return ret;
}
void init () {
g[0] = 0;
for (int i = 1; i < maxn; i++)
g[i] = SG(i);
}
int judge () {
int ret = 0;
for (int i = 0; i < n-1; i++) {
if (s[i]&1)
ret ^= g[n-1-i];
}
return ret;
}
void put_ans () {
for (int i = 0; i < n-1; i++) {
if (s[i] == 0)
continue;
s[i]--;
for (int j = i+1; j < n; j++) {
s[j]++;
for (int k = j; k < n; k++) {
s[k]++;
if (judge() == 0) {
printf(" %d %d %d\n", i, j, k);
return;
}
s[k]--;
}
s[j]--;
}
s[i]++;
}
}
int main () {
init();
int cas = 1;
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%d", &s[i]);
printf("Game %d:", cas++);
if (judge())
put_ans();
else
printf(" -1 -1 -1\n");
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-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了
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC