[POJ 1704] Georgia and Bob (尼姆博弈变形)

2014-11-24 02:56:58 · 作者: · 浏览: 1

POJ 1704 Georgia and Bob (尼姆博弈变形)

题目链接: http://poj.org/problem id=1704

题目大意:

Georgia和Bob两个人玩游戏,他们设计了如下的的棋盘,有N块格子,从1开始标号。棋盘上不同的格子上有一些棋子,其中每个格子只能有一个棋子。然后他们开始轮流移动棋子,每次选择其中的一个向左移动,每次最少移动一格,最多只能移到前一个的右边。(第一个只能移到1上)。当谁先不能移动棋子便算输。Gerogia先移动。

输入为T组样例,每个样例有n个棋子,位置分别为p1,p2,……pn

\\\

思路:

这道题困扰了我很久,我都知道他是尼姆博弈了,还是wa成了狗。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgIM7SysfV4sO0z+u1xKOssNHP4MHawb220cqvzbfWrrzktcS+4MDrtbHX9srH0ru20cqvzbejrMO/tM7Sxravyq/Nt6Osz+C1sdPatNPW0Mihs/bKr9fToaM8L3A+CjxwPiAgICC1q8rHo6y688C0t6LP1tXiw7TP67HYyLvKx7TttcShozwvcD4KPHA+ICAgIL7NyOfJz828y/nKvqOssNHU2jO1xMbl19PSxrW9wcsyoaPEx8O0z+C1sdPayKHX38HLo6gxLDOjqdauvOS1xMqv19OjrLWrysejqDMsNqOp1q685LXEyq/X08r9u+Gx5LbgoaO63M/UyLujrMrHuPa07c7ztcS82cnooaM8L3A+CjxwPjwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICC688C0u7nKx8nPzfi/tMHLsfDIy7XEy7zCt6OsssW3os/W1eK1wMzitcTEo9DNvajBosrHxMfDtMfJw+6hozwvcD4KPHA+ICAgILTz1sLKx9Xi0fm1xKO6PC9wPgo8cD6009PSzfnX86Oswb3BvbfWzqrSu9fpo6zI57n7xuXX08r9zqrG5sr9o6zU8rDRtdrSu7j2us3HvbfWzqrSu9fpoaPIu7rzsNHBvbbR1q685LXEv9UmIzI2Njg0O8r9tbHX9srH0ru20cqvzbeho6OoutzJ8cbmo6y3tNX9ztLKx8S+09DP67W9oaOho6OpPC9wPgo8cD7Iu7rz1qTD99Xi0fm9qMGixKPQzbXE1f3It9DUoaM8L3A+CjxwPqOoMaOpytfPyL/J0tSxo9ako6zDv7TO0sa2r9K7uPbG5dfTo6yx2Mi7ysfSxravxLPSu9fpo6jBvcG9t9bX6aOptcTX87Hfu/LV39PSsd+1xMbl19OhozwvcD4KPHA+xuS0zsrH0qrIz8q2tb2jrLbU09omIzIzNjEyO8S3sqnexKOsxuTKtcO/tM7SxravtrzKx9Tasru2z7Hku7vS7Lvyus2jrLy0tNMwtb23xzDU2bW9MLXEseS7r7n9s8yho6Ooz+rPuL3iys2147v3tMu0pqOpPC9wPgo8cD6jqDKjqdK71+mjqG6jrG2jqcjnufvSxrav1/Ox37XExuXX0yB4ILK9o6zSu7aov8nS1NLGtq+21NOmtcTT0rHfxuXX0yB4ILK9o6yx5M6qo6huIC0geKOsIG0gLSB4o6mho9XixuTKtb7Nyse00yAwILW9ILfHMCDU2bW9IDAgtcS5/bPMoaM8L3A+CjxwPqOoM6OpttTT2qOobqOsbaOpyOe5+9LGtq/T0rHftcTG5dfTIHggsr2jrLK7xNy5u7Gj1qTG5LbU06a1xNfzsd+1xMqv19PSssTcubvSxravIHggsr2jrMv50tTO3reossnTw6OoMqOptcS3vcq9oaO1q8rHztLDx9aqtcCjrNLGtq/By9PSsd+1xMqvzbejrM/gtbHT2rTT0ru20cqvzbe1sdbQyKHX39K70KmjrMTHw7S4+b7dJiMyMzYxMjvEt7Kp3sS1xNLsu/LUrdTyo6zSu7aov8nS1NTawe3Su7bRtbHW0Mih198geSC49sqvzbejrMq5tcPS7Lvy1q6689PWseTOqjCho7y00sa2r8Ht0rvX6dPSsd+1xMqvzbe8tL/JoaM8L3A+CjxwPjxicj4KPC9wPgo8cD7P1Mi7o6zJz8r2tcTEo9DNuty6w7XEveK+9sHL1eK49s7KzOKho7Wryseyu9aqtcDT0MO709DIy8u8v7y5/c6qyrLDtNK7tqjKx7TT09LN+dfzwb249rfWttHE2KOsyOe5+7TT1/PN+dPSt9bE2KOs1eLR+dfT0NCyu9DQo788L3A+CjxwPs7SuPbIy7OiytTBy9K7z8KjrNbBydnO0r2owaK1xMSj0M3Kx8O709C63LrDtcS94r721eK49s7KzOKho8jnufvLtcbl19PK/crHxbzK/bj2o6zKx9K70fm1xKGj1vfSqsrHyq/X08r9zqrG5sr9uPbKsaOs1+6688LktaW1xMbl19PU9cO0sOyho87StcS3vbeoyse82c/rs/a12iBuICYjNDM7IDEguPbG5dfTwLSjrM671sPV/brDysdwWyBuIF0gJiM0MzsgMaGj1eLR+aOsz+C1sdPasrnBy9K7ttHKr9fTyv3OqiAwILXEyq/X0734yKWho8i7uvPU2dPDyc/K9rXEIDMguPayvdbowLSy2df3o6y40L71yc+6w8/xysfSu8Sj0rvR+aOstavKx3dhwcs8L3A+CjxwPs7Sw8fAtLfWzvbSu8/Co6y80734yKW1xMqv19Oxvsntvs3Kx9DpxOKz9sC0tcSjrMv50tTI57n70sa2r7XaIG4gv8XG5dfTo6i21NOmzqrX87HftcSjqaOsvs2yu8Tc0sa2r8bk09Kx37XExuXX06Gjy+TIu87Sw8e82cnos/bBy7XaIG4gJiM0MzsgMSC20cqv19OjrLWr1eKxz765ysfO0sPHvNnJ6LXEoaPI57n71rTD1LK7zvK1xM/r0qrSxravuMO20cqv19OjrM/gtbHT2sO709Cy2df3oaM8L3A+CjxwPjxicj4KPC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">/* 尼姆博弈变形,巧妙的建模思想 */ #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int p[maxn + 10]; int main () { int t, n, sum; scanf("%d", &t); while(t--) { scanf("%d", &n); sum = 0; for (int i = 0; i < n; i++) scanf("%d", p + i); if (n % 2) p[n++] = 0; //把石子从右向左两两一组,如果为奇数,把位置为0的也当做一枚棋子,但不能移动了 sort(p, p + n); for (int i = 1; i < n; i += 2) sum ^= (p[i] - p[i - 1] - 1); //每一组左右的间隔就是石子数 if (!sum) puts("Bob will win"); else puts("Georgia will win"); } return 0; }