coreBugZJ

此 blog 已棄。

POJ 1067 取石子游戲

/*
2

POJ 1067 取石子游戲
3

----問(wèn)題描述：
6

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

----輸入：
11

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

----輸出：
16

輸出對(duì)應(yīng)也有若干行，每行包含一個(gè)數(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)然就知道這是一道博弈論的問(wèn)題，最容易想的就是直接用博弈論的必?cái)　⒈貏賾B(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求解。但是樸素的動(dòng)態(tài)規(guī)劃是 O(N * M) 的，如果做一些優(yōu)化可能可以過(guò)掉 RQNOJ 的題目，但是對(duì)于 POJ 1067 來(lái)說(shuō)就完全無(wú)能為力。所以我們嘗試分析數(shù)據(jù)，看看有沒(méi)有什么規(guī)律（以下用 (a, b) 表示兩堆石子的個(gè)數(shù)，即游戲中的一個(gè)狀態(tài)）。
39

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

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

首先回顧必勝態(tài)和必?cái)B(tài)的樸素求法：
45

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

證明略去。
49

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

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

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

定理 2：若 (a, b) 是必?cái)B(tài)，則對(duì)于所有的 x <> a 和 y <> b，(x, b) 和 (a, y) 是必勝態(tài)。
57

證明：
59

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

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

定理 3: 若 (a, b) 是必?cái)B(tài)，則對(duì)于所有的 d > 0，(a + d, b + d) 是必勝態(tài)。
65

證明：
67

與定理 2 類(lèi)似。
69

定理 4：在所有的必?cái)B(tài)中，每個(gè)數(shù)字恰巧出現(xiàn)一次。
71

證明：
73

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

1 2
77

3 5
79

4 7
81

6 10
83

……
85

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

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

證明：
91

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

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

證明：
97

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

100

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

102

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

104

首先，我們考慮從第一堆中取出 p 個(gè)石子，得到狀態(tài) (a[i] - p, a[i] + delta)，由定理 5，比 a[i] 小的數(shù)都在之前出現(xiàn)過(guò)，若 a[i] - p 出現(xiàn)在某一行的第一列，由于存在必?cái)B(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)在某一行的第二列，由于第一列是單增的，因而其對(duì)應(yīng)的第一列數(shù)必小于 a[i] + delta，故而也可推出其狀態(tài)為必勝態(tài)。
105

106

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

108

于是，(a[i], a[i] + delta) 狀態(tài)的勝負(fù)性只與狀態(tài) (a[i], a[i] + d) (d < delta) 有關(guān)。不難看出，delta = i 時(shí)恰為必?cái)B(tài)，因?yàn)椴徽搹牡诙阎腥〕龆嗌賯€(gè)石子，作為另一堆的第一堆石子并沒(méi)有在之前出現(xiàn)過(guò)，所以得到的一定是一個(gè)必勝態(tài)，因而 (a[i], a[i] + delta) 為必?cái)B(tài)，由定理 2 及定理 4 可得，原命題成立。即矩陣中第 i 行第二列的數(shù)等于同行第一列的數(shù)加上 i。
109

110

111

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

113

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

115

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

117

證明：暫時(shí)略去，將來(lái)補(bǔ)充。
118

119

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

121

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

123

我們的目的是要讓 Z+ 中每個(gè)數(shù)都在這個(gè)矩陣中出現(xiàn)，于是考慮到 Betty 定理的條件，Φ 和 (Φ + 1) 應(yīng)滿(mǎn)足 1/Φ + 1/(Φ + 1) = 1。解這個(gè)方程，我們得到 Φ = (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，代碼的實(shí)現(xiàn)就十分簡(jiǎn)單了，由于是數(shù)學(xué)算法，總復(fù)雜度為 O(1)。至此，本題完美解決。
136

137

138

總結(jié)：遇到這樣困難的題目時(shí)，我們不應(yīng)該輕言放棄。而應(yīng)該仔細(xì)分析題目隱含的信息，學(xué)會(huì)分析和轉(zhuǎn)化問(wèn)題，從而找到問(wèn)題的突破口，一舉殲滅問(wè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 閱讀(5488) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè)

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營(yíng)技術(shù)類(lèi)職位在線(xiàn)測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問(wèn)題，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 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(lèi)(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語(yǔ)言

好有道理

技術(shù)

開(kāi)源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

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

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

POJ 1067 取石子游戲