Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6706 Accepted Submission(s): 3646

Problem Description
有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。

Input
輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000。

Output
輸出對應(yīng)也有若干行，每行包含一個數(shù)字1或0，如果最后你是勝者，則為1，反之，則為0。

Sample Input
2 1
8 4
4 7

Sample Output
0
1
0

【題目鏈接】:http://acm.hdu.edu.cn/showproblem.php?pid=1527

【題解】

/*假設(shè)剩余的石子為(i,j);(不妨設(shè)i<=j)有這樣的必敗點(diǎn)(0,0) (1,2) (3,5) (4,7) (6,10)...設(shè)為(n,m)為第x對必敗點(diǎn);(從0開始);這里的n是前面的x-1對必敗點(diǎn)中沒有出現(xiàn)的最小整數(shù);m則等于n+x這里的n有通項(xiàng)公式n=[x*(1+√5)/2][x]為不超過x的最大整數(shù);①證所有的自然數(shù)都有出現(xiàn)在必敗點(diǎn)中;n[x]是之前沒有出現(xiàn)過的自然數(shù);所以n[x]>n[x-1];又m[x]=n[x]+x>n[x-1]+x-1=m[x-1]>n[x-1]所以m[x]比之前出現(xiàn)過的所有數(shù)字都大;即也沒有出現(xiàn)過;又n[x]是之前沒有出現(xiàn)過的數(shù)中最小的那個;則可知所有的自然數(shù)都出現(xiàn)在了必敗點(diǎn)中;(可能在i也可能在j);②證所有的必敗點(diǎn)都能在規(guī)則允許的操作內(nèi)推出必勝點(diǎn);(i,j)->(i+t,j)||(i,j+t)||(i+t,j+t);顯然都是合法的操作;t取任意實(shí)數(shù)都能推出一個必勝點(diǎn);(且因?yàn)樗鼈儍蓚€的差是固定的k,則不可能是下一個必敗點(diǎn));③證所有的不是上述必敗點(diǎn)的都是必勝點(diǎn)(能轉(zhuǎn)移到必敗點(diǎn));設(shè)非必敗點(diǎn)為(i,j)這里i<=j因?yàn)樗械淖匀粩?shù)都在必敗點(diǎn)當(dāng)中(是必敗點(diǎn)對中的一個)則一.若i=n[x],1' j>m[x]則可以讓j減少j-m[x]就變成必敗點(diǎn)了;2' j<m[x]則可以讓(n[x],j)->(n[j-n[x]],n[j-n[x]]+j-n[x])即i和j同時減少n[x]-n[j-n[x]]這里因?yàn)閖>=i,所以j>=n[x];而變化后的點(diǎn)是一個合法的必敗點(diǎn);二.若j=m[x]1' i>n[x]則讓i減少i-n[x],這樣(i,j)就變成必敗點(diǎn)了;2' i<n[x]這里還有分類i肯定是某個必敗點(diǎn)的元素;(自然數(shù)都是必敗點(diǎn)的元素);①如果i=n[x0](x0<x)則j=m[x]>m[x0];則讓j減去j-m[x0]就又得到一個必敗點(diǎn)了;->(n[x0],m[x0])②如果i=m[x0](x0<x)j=m[x]>m[x0]>n[x0];則讓j減去j-n[x0];這樣i會變成大于j的了->(m[x0],n[x0]);但是沒關(guān)系再倒回了就好;總之又得到了必敗點(diǎn)綜上不是必敗點(diǎn)就一定是必勝點(diǎn)(所以證明②有什么用?:))則對于輸入,先保證a<b然后x=b-a看看x*(1+√5)/2是不是等于a;如果是,則為必敗點(diǎn);否則為必勝點(diǎn); */

【完整代碼】

#include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se second #define rei(x) scanf("%d",&x) #define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii; typedef pair<LL,LL> pll;//const int MAXN = x; const int dx[9] = {0,1,-1,0,0,-1,-1,1,1}; const int dy[9] = {0,0,0,-1,1,-1,1,-1,1}; const double pi = acos(-1.0);int a,b;int main() {//freopen("F:\\rush.txt","r",stdin);while (~scanf("%d%d",&a,&b)){if (a>b)swap(a,b);int x = b-a;int temp = floor(x*(1.0+sqrt(5))/2.0);if (temp==a)puts("0");elseputs("1");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AWCXV/p/7626728.html

總結(jié)

以上是生活随笔為你收集整理的【hdu 1527】取石子游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。