欧美一区二区三区视频免费播放,免费观看成人,老司机午夜免费精品视频

POJ 1067 取石子游戲

/*
2

POJ 1067 取石子游戲
3

----問題描述：
6

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

----輸入：
11

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

----輸出：
16

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

----樣例輸入：
21

2 1
23

8 4
24

4 7
25

----樣例輸出：
28

0
30

1
31

0
32

----分析：
35

（轉(zhuǎn)自網(wǎng)上，略有修正）
37

大致看完題目，想當(dāng)然就知道這是一道博弈論的問題，最容易想的就是直接用博弈論的必敗、必勝態(tài)進行動態(tài)規(guī)劃求解。但是樸素的動態(tài)規(guī)劃是 O(N * M) 的，如果做一些優(yōu)化可能可以過掉 RQNOJ 的題目，但是對于 POJ 1067 來說就完全無能為力。所以我們嘗試分析數(shù)據(jù)，看看有沒有什么規(guī)律（以下用 (a, b) 表示兩堆石子的個數(shù)，即游戲中的一個狀態(tài)）。
39

列舉了幾個狀態(tài)之后容易發(fā)現(xiàn)，必勝態(tài)的數(shù)目比必敗態(tài)要多很多，所以我們先手工求出前幾個必敗態(tài)：
41

(1, 2)、(2, 1)、(3, 5)、(5, 3)、(4, 7)、(7, 4)、（6, 10）、（10, 6）……
43

首先回顧必勝態(tài)和必敗態(tài)的樸素求法：
45

定理 0：一個狀態(tài)是必敗態(tài)，當(dāng)且僅當(dāng)它的所有后繼狀態(tài)都是必勝態(tài)；而一個狀態(tài)是必勝態(tài)，只要它的后繼狀態(tài)有一個以上的必敗態(tài)即可。
47

證明略去。
49

容易發(fā)現(xiàn)下面的定理：
51

定理 1：(a，b) 和 (b, a) 的勝負性是相同的（a <> b）。
53

證明：如果 (a, b) 是必勝態(tài)，那么將必勝策略中所有的操作，對第一堆的變?yōu)榈诙眩瑢Φ诙训淖優(yōu)榈谝欢眩蜆?gòu)成 (b, a) 的必勝策略
55

定理 2：若 (a, b) 是必敗態(tài)，則對于所有的 x <> a 和 y <> b，(x, b) 和 (a, y) 是必勝態(tài)。
57

證明：
59

對于 x > a 和 y > b，不管是哪一種情況，總可以從 x 堆或 y 堆中取出一定量的石子使當(dāng)前狀態(tài)變?yōu)楸財B(tài) (a, b)，由定理 1，(x, b) 和 (a, y) 為必勝態(tài)。
61

對于 x < a 和 y < b，不管是哪一種情況，如果 (x, b) 或 (a, y) 是必敗態(tài)的話，由上述可得 (a, b) 是必勝態(tài)，矛盾。故 (x, b) 和 (a, y) 均為為必勝態(tài)。
63

定理 3: 若 (a, b) 是必敗態(tài)，則對于所有的 d > 0，(a + d, b + d) 是必勝態(tài)。
65

證明：
67

與定理 2 類似。
69

定理 4：在所有的必敗態(tài)中，每個數(shù)字恰巧出現(xiàn)一次。
71

證明：
73

有了定理 1，對于對稱的狀態(tài)我們只需要處理其中一個，而兩個數(shù)不會相同（相同的狀態(tài)必然是必勝態(tài)），于是我們把每個狀態(tài)中較小的數(shù)字放在前面，每行寫一個狀態(tài)，去掉括號并按照升序排列每行的第一個數(shù)，就構(gòu)成了如下的矩陣：
75

1 2
77

3 5
79

4 7
81

6 10
83

……
85

觀察這個矩陣，我們又可以得到新的定理：
87

定理 5：矩陣中每行第一個數(shù)恰巧是前面每一行中沒有出現(xiàn)過的最小正整數(shù)。
89

證明：
91

由定理 4，矩陣中每個數(shù)字恰巧出現(xiàn)一次，而按照這個矩陣的定義，第二列的數(shù)總比同行第一列大，第一列又按照升序排列，所以每一行的第一個數(shù)正好為前面每一行中沒有出現(xiàn)過的最小正整數(shù)。
93

定理 6：矩陣第 i 行的第二個數(shù)正好為第一個數(shù)加上 i
95

證明：
97

用數(shù)學(xué)歸納法。
99

100

1) 對于第一行顯然成立
101

102

2) 若對于前 i - 1 行均成立，則所有的 (a[p], a[p] + p) (a[p] 為第 p 行第一個數(shù)，p < i) 均為必敗態(tài)，那么考察第 i 行的狀態(tài) (a[i], a[i] + delta)。容易看出 delta >= i，因為如果 delta < i，一定可以通過一次操作變?yōu)榍懊娉霈F(xiàn)過的必敗態(tài)，那么這個狀態(tài)就是必勝態(tài)。下面由 delta >= i，我們來說明 delta = i。
103

104

首先，我們考慮從第一堆中取出 p 個石子，得到狀態(tài) (a[i] - p, a[i] + delta)，由定理 5，比 a[i] 小的數(shù)都在之前出現(xiàn)過，若 a[i] - p 出現(xiàn)在某一行的第一列，由于存在必敗態(tài) (a[i] - p, a[i] - p + d) (d < delta)，故 (a[i] - p, a[i] + delta) 一定為必勝態(tài)（定理 2）；若 a[i] - p 出現(xiàn)在某一行的第二列，由于第一列是單增的，因而其對應(yīng)的第一列數(shù)必小于 a[i] + delta，故而也可推出其狀態(tài)為必勝態(tài)。
105

106

對于從兩堆石子中取出相同數(shù)目的情況與之類似，容易看出一定為必勝態(tài)。
107

108

于是，(a[i], a[i] + delta) 狀態(tài)的勝負性只與狀態(tài) (a[i], a[i] + d) (d < delta) 有關(guān)。不難看出，delta = i 時恰為必敗態(tài)，因為不論從第二堆中取出多少個石子，作為另一堆的第一堆石子并沒有在之前出現(xiàn)過，所以得到的一定是一個必勝態(tài)，因而 (a[i], a[i] + delta) 為必敗態(tài)，由定理 2 及定理 4 可得，原命題成立。即矩陣中第 i 行第二列的數(shù)等于同行第一列的數(shù)加上 i。
109

110

111

這時，我們所有的問題都轉(zhuǎn)化到了矩陣上，只要能通過合適的方法表示出這個矩陣，我們就可以很好地解決原問題。
112

113

下面的過程可能需要比較高的數(shù)學(xué)技巧，首先給出我們需要的一個重要定理（[x] 表示 x 的整數(shù)部分，{x} 表示 x 的小數(shù)部分，即 {x} = x - [x]）：
114

115

定理 7（Betty 定理）：如果存在正無理數(shù) A, B 滿足 1/A + 1/B = 1，那么集合 P = { [At], t ∈ Z+}、Q = { [Bt], t ∈ Z+} 恰為集合 Z+ 的一個劃分，即：P ∪ Q = Z+，P ∩ Q = ø。
116

117

證明：暫時略去，將來補充。
118

119

考慮到 Betty 定理中“恰為 Z+ 的劃分”這一說，這意味著，Z+ 中的每個數(shù)都恰好出現(xiàn)一次，這與上述矩陣的性質(zhì)十分吻合。于是我們猜想每一行第一列的數(shù)滿足 [Φi] 的形式。
120

121

于是我們得到每一行第二列的數(shù)為 [Φi] + i = [Φi + i] = [(Φ + 1)i]
122

123

我們的目的是要讓 Z+ 中每個數(shù)都在這個矩陣中出現(xiàn)，于是考慮到 Betty 定理的條件，Φ 和 (Φ + 1) 應(yīng)滿足 1/Φ + 1/(Φ + 1) = 1。解這個方程，我們得到 Φ = (sqrt(5) + 1) / 2，于是 Φ + 1 = (sqrt(5) + 3) / 2。
124

125

Φ 恰為黃金分割比，這是多么令人驚奇的結(jié)論！
126

127

于是應(yīng)用 Betty 定理，我們得到最終我們需要的定理：
128

129

定理 8：上述矩陣中每一行第一列的數(shù)為 [Φi]，第二列的數(shù)為 [(Φ + 1)i]，其中 Φ = (sqrt(5) + 1) / 2 為黃金分割比。
130

131

證明：由 Betty 定理顯然得證。
132

133

134

135

有了定理 8，代碼的實現(xiàn)就十分簡單了，由于是數(shù)學(xué)算法，總復(fù)雜度為 O(1)。至此，本題完美解決。
136

137

138

總結(jié)：遇到這樣困難的題目時，我們不應(yīng)該輕言放棄。而應(yīng)該仔細分析題目隱含的信息，學(xué)會分析和轉(zhuǎn)化問題，從而找到問題的突破口，一舉殲滅問題。
139

140

141

*/
142

143

144

#include <iostream>
145

#include <cstdio>
146

#include <cmath>
147

148

using namespace std;
149

150

int main() {
151

int a, b, d, t;
152

while ( 2 == scanf( "%d%d", &a, &b ) ) {
153

if ( a > b ) {
154

t = a;
155

a = b;
156

b = t;
157

}
158

d = b - a;
159

t = floor( d * ( sqrt(5.0) + 1 ) / 2 );
160

puts( (t == a) ? "0" : "1" );
161

}
162

return 0;
163

}
164

posted on 2012-06-04 16:05 coreBugZJ 閱讀(5470) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè)

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 微軟2014實習(xí)生及秋令營技術(shù)類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1067 取石子游戲