题目连接:uva 1500 - Alice and Bob
题目大意:在黑板上又一个序列,每次操作可以选择一个数减1,或者是合并两个数,一个数被减至1则自动消除,不能操作者输。
解题思路:结论,对于大于1的数可以看成是一个整数s,为消除他们的总操作步数,包括减1以及合并,c为列中1的个数,如果s>2的话,c或者是s为奇数则为必胜,否则必败。若s≤2的话(s=2或者s=0)是,判断c是否为3的倍数,是的话必败,不是的话必胜。
证明:s>2时,s和c均为偶数是为必败态。
s为奇数,c为偶数:先手操作,将s减1,转移至必败态。 s为偶数,c为奇数:先手操作,将一个1减1,则c会减少1,转移至必败态。
s为奇数,c为奇数:将一个1和s中的一个数合并。转移至必败态。
s为偶数,c为偶数:s减1,则s为奇数c为偶数,必胜态;c减1,则s为偶数c为奇数,必胜态;合并1和非1数,s奇数c奇数,必胜态;
s==0或者s==2时,当c%3==0时,为必败态。
c%3==1时,将一个1减1,c%3==0,转移至必败态。
c%3==2时,对于s==0,合并两个1,则变为s+2,c-2,此时如果s==0,则变为s==2时,c%3==0的必败态;对于s==2,将s减1,则变为s变为1,于是1的个数又增加1,所以c%3==0,必败态。
c%3==0时,减掉一个1即为必胜态。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, c, s, x;
void init () {
c = s = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
if (x == 1)
c++;
else if (x > 1)
s += (x + 1);
}
if (s)
s--;
}
bool judge () {
if (s > 2)
return (c&1) || (s&1);
if (s == 0)
return c % 3;
return c % 3;
}
int main () {
int cas;
scanf("%d", &cas);
for (int k = 1; k <= cas; k++) {
init();
printf("Case #%d: %s\n", k, judge() ? "Alice" : "Bob");
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC