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

coreBugZJ

此 blog 已棄。

POJ 1067 取石子游戲

  1/*
  2POJ 1067 取石子游戲
  3
  4
  5----問題描述:
  6
  7有兩堆石子,數(shù)量任意,可以不同。游戲開始由兩個(gè)人輪流取石子。游戲規(guī)定,每次有兩種不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目,如果輪到你先取,假設(shè)雙方都采取最好的策略,問最后你是勝者還是敗者。
  8
  9
 10----輸入:
 11
 12輸入包含若干行,表示若干種石子的初始情況,其中每一行包含兩個(gè)非負(fù)整數(shù)a和b,表示兩堆石子的數(shù)目,a和b都不大于1,000,000,000。
 13
 14
 15----輸出:
 16
 17輸出對(duì)應(yīng)也有若干行,每行包含一個(gè)數(shù)字1或0,如果最后你是勝者,則為1,反之,則為0。
 18
 19
 20----樣例輸入:
 21
 222 1
 238 4
 244 7
 25
 26
 27----樣例輸出:
 28
 290
 301
 310
 32
 33
 34----分析:
 35
 36(轉(zhuǎn)自網(wǎng)上,略有修正)
 37
 38大致看完題目,想當(dāng)然就知道這是一道博弈論的問題,最容易想的就是直接用博弈論的必?cái) ⒈貏賾B(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求解。但是樸素的動(dòng)態(tài)規(guī)劃是 O(N * M) 的,如果做一些優(yōu)化可能可以過掉 RQNOJ 的題目,但是對(duì)于 POJ 1067 來說就完全無能為力。所以我們嘗試分析數(shù)據(jù),看看有沒有什么規(guī)律(以下用 (a, b) 表示兩堆石子的個(gè)數(shù),即游戲中的一個(gè)狀態(tài))。
 39
 40列舉了幾個(gè)狀態(tài)之后容易發(fā)現(xiàn),必勝態(tài)的數(shù)目比必?cái)B(tài)要多很多,所以我們先手工求出前幾個(gè)必?cái)B(tài):
 41
 42(1, 2)、(2, 1)、(3, 5)、(5, 3)、(4, 7)、(7, 4)、(6, 10)、(10, 6)……
 43
 44首先回顧必勝態(tài)和必?cái)B(tài)的樸素求法:
 45
 46定理 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
 48證明略去。
 49
 50容易發(fā)現(xiàn)下面的定理:
 51
 52定理 1:(a,b) 和 (b, a) 的勝負(fù)性是相同的(a <> b)。
 53
 54證明:如果 (a, b) 是必勝態(tài),那么將必勝策略中所有的操作,對(duì)第一堆的變?yōu)榈诙眩瑢?duì)第二堆的變?yōu)榈谝欢眩蜆?gòu)成 (b, a) 的必勝策略
 55
 56定理 2:若 (a, b) 是必?cái)B(tài),則對(duì)于所有的 x <> a 和 y <> b,(x, b) 和 (a, y) 是必勝態(tài)。
 57
 58證明:
 59
 60對(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
 62對(duì)于 x < a 和 y < b,不管是哪一種情況,如果 (x, b) 或 (a, y) 是必?cái)B(tài)的話,由上述可得 (a, b) 是必勝態(tài),矛盾。故 (x, b) 和 (a, y) 均為為必勝態(tài)。
 63
 64定理 3: 若 (a, b) 是必?cái)B(tài),則對(duì)于所有的 d > 0,(a + d, b + d) 是必勝態(tài)。
 65
 66證明:
 67
 68與定理 2 類似。
 69
 70定理 4:在所有的必?cái)B(tài)中,每個(gè)數(shù)字恰巧出現(xiàn)一次。
 71
 72證明:
 73
 74有了定理 1,對(duì)于對(duì)稱的狀態(tài)我們只需要處理其中一個(gè),而兩個(gè)數(shù)不會(huì)相同(相同的狀態(tài)必然是必勝態(tài)),于是我們把每個(gè)狀態(tài)中較小的數(shù)字放在前面,每行寫一個(gè)狀態(tài),去掉括號(hào)并按照升序排列每行的第一個(gè)數(shù),就構(gòu)成了如下的矩陣:
 75
 761  2
 77
 783  5
 79
 804  7
 81
 826  10
 83
 84……
 85
 86觀察這個(gè)矩陣,我們又可以得到新的定理:
 87
 88定理 5:矩陣中每行第一個(gè)數(shù)恰巧是前面每一行中沒有出現(xiàn)過的最小正整數(shù)。
 89
 90證明:
 91
 92由定理 4,矩陣中每個(gè)數(shù)字恰巧出現(xiàn)一次,而按照這個(gè)矩陣的定義,第二列的數(shù)總比同行第一列大,第一列又按照升序排列,所以每一行的第一個(gè)數(shù)正好為前面每一行中沒有出現(xiàn)過的最小正整數(shù)。
 93
 94定理 6:矩陣第 i 行的第二個(gè)數(shù)正好為第一個(gè)數(shù)加上 i
 95
 96證明:
 97
 98用數(shù)學(xué)歸納法。
 99
1001) 對(duì)于第一行顯然成立
101
1022) 若對(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,一定可以通過一次操作變?yōu)榍懊娉霈F(xiàn)過的必?cái)B(tài),那么這個(gè)狀態(tài)就是必勝態(tài)。下面由 delta >= i,我們來說明 delta = i。
103
104首先,我們考慮從第一堆中取出 p 個(gè)石子,得到狀態(tài) (a[i] - p, a[i] + delta),由定理 5,比 a[i] 小的數(shù)都在之前出現(xiàn)過,若 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ù)目的情況與之類似,容易看出一定為必勝態(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è)石子,作為另一堆的第一堆石子并沒有在之前出現(xiàn)過,所以得到的一定是一個(gè)必勝態(tài),因而 (a[i], a[i] + delta) 為必?cái)B(tài),由定理 2 及定理 4 可得,原命題成立。即矩陣中第 i 行第二列的數(shù)等于同行第一列的數(shù)加上 i。
109
110
111這時(shí),我們所有的問題都轉(zhuǎn)化到了矩陣上,只要能通過合適的方法表示出這個(gè)矩陣,我們就可以很好地解決原問題。
112
113下面的過程可能需要比較高的數(shù)學(xué)技巧,首先給出我們需要的一個(gè)重要定理([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+ 的一個(gè)劃分,即:P ∪ Q = Z+,P ∩ Q = ø。
116
117證明:暫時(shí)略去,將來補(bǔ)充。
118
119考慮到 Betty 定理中“恰為 Z+ 的劃分”這一說,這意味著,Z+ 中的每個(gè)數(shù)都恰好出現(xiàn)一次,這與上述矩陣的性質(zhì)十分吻合。于是我們猜想每一行第一列的數(shù)滿足 [Φi] 的形式。
120
121于是我們得到每一行第二列的數(shù)為 [Φi] + i = [Φi + i] = [(Φ + 1)i]
122
123我們的目的是要讓 Z+ 中每個(gè)數(shù)都在這個(gè)矩陣中出現(xiàn),于是考慮到 Betty 定理的條件,Φ 和 (Φ + 1) 應(yīng)滿足 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)化問題,從而找到問題的突破口,一舉殲滅問題。
139
140
141*/

142
143
144#include <iostream>
145#include <cstdio>
146#include <cmath>
147
148using namespace std;
149
150int 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 閱讀(5491) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲精品美女在线观看| 亚洲精品美女在线| 久久国产精品一区二区| 国产精品女同互慰在线看| 亚洲欧美日韩一区在线观看| 亚洲一区二区三区在线观看视频| 国产精品亚发布| 久久亚洲精品伦理| 欧美gay视频激情| 久久久久综合网| 亚洲高清视频一区| 西西人体一区二区| 久久av一区二区三区漫画| 亚洲国产一区二区三区a毛片| 日韩午夜电影av| 国产伦一区二区三区色一情| 老司机精品导航| 欧美日本不卡| 亚洲精品免费在线| 中国成人黄色视屏| 影音先锋久久精品| 日韩午夜中文字幕| 国产亚洲一级| 一本大道久久a久久精品综合| 国产亚洲精品aa| 亚洲精品一二区| 激情小说另类小说亚洲欧美| 亚洲精品一区在线观看| 国产一区二区三区电影在线观看| 亚洲春色另类小说| 久久天天躁狠狠躁夜夜av| 中文欧美日韩| 99精品国产99久久久久久福利| 国产在线精品成人一区二区三区| 亚洲第一视频| 伊人狠狠色丁香综合尤物| 99精品视频免费观看视频| 亚洲国产毛片完整版| 亚洲欧美视频在线| 制服丝袜亚洲播放| 免费亚洲视频| 美女啪啪无遮挡免费久久网站| 国产精品国产三级国产aⅴ9色| 亚洲国产1区| 在线播放亚洲| 欧美专区在线观看| 亚洲欧美日本日韩| 欧美日韩在线第一页| 91久久精品日日躁夜夜躁国产| 国产麻豆视频精品| 亚洲综合久久久久| 亚洲欧美国产毛片在线| 欧美人在线观看| 亚洲国产一区二区a毛片| 亚洲第一天堂av| 久久久久久91香蕉国产| 久久九九热re6这里有精品| 国产嫩草一区二区三区在线观看| 日韩午夜免费| 亚洲影音一区| 国产精品啊啊啊| 一区二区三区四区在线| 亚洲影视中文字幕| 国产精品yjizz| 亚洲在线视频| 欧美一区二区三区四区在线观看| 国产精品久久久久国产精品日日| 一区二区三区精品视频| 亚洲专区在线视频| 国产精品三级久久久久久电影| 亚洲一二三区精品| 久久成人18免费网站| 国产视频精品免费播放| 欧美一级在线视频| 久热综合在线亚洲精品| 亚洲第一成人在线| 欧美顶级少妇做爰| 久久九九全国免费精品观看| 国产一级揄自揄精品视频| 欧美中文字幕在线观看| 欧美大片免费观看在线观看网站推荐| 亚洲福利视频一区二区| 欧美美女bb生活片| 中文欧美字幕免费| 久久久精品2019中文字幕神马| 在线播放不卡| 欧美日韩精品久久久| 午夜精品剧场| 欧美成人精品h版在线观看| 99视频国产精品免费观看| 欧美色中文字幕| 午夜精品久久久久久久99热浪潮| 久久婷婷国产综合精品青草| 99热在这里有精品免费| 国产日韩精品一区二区| 欧美99久久| 亚洲女同精品视频| 欧美激情在线免费观看| 亚洲欧美卡通另类91av| 在线观看日韩欧美| 欧美午夜精品久久久久久浪潮| 欧美一级片在线播放| 亚洲国产婷婷| 久久天天躁狠狠躁夜夜爽蜜月| 99pao成人国产永久免费视频| 国产毛片精品国产一区二区三区| 美女黄网久久| 欧美一级夜夜爽| 一区二区av在线| 欧美成人亚洲成人日韩成人| 亚洲欧美视频在线| 亚洲精品乱码| 在线精品国精品国产尤物884a| 欧美日韩一区精品| 欧美成人嫩草网站| 久久精品国产一区二区三区免费看| 亚洲狼人精品一区二区三区| 免播放器亚洲一区| 欧美在线看片| 亚洲免费在线精品一区| 日韩视频第一页| 永久域名在线精品| 国产亚洲福利社区一区| 国产精品美女久久福利网站| 欧美激情中文不卡| 免费在线观看成人av| 久久久91精品国产一区二区三区 | 99re视频这里只有精品| 久久一区激情| 久久精品夜色噜噜亚洲a∨| 亚洲一区二区三区精品视频| 亚洲人成在线免费观看| 亚洲国产天堂久久国产91| 国产一区二区三区黄| 国产精品最新自拍| 国产精品一区一区三区| 国产精品黄视频| 国产精品久久久久久久久久ktv| 欧美日韩精品免费| 欧美日韩国产在线观看| 欧美人牲a欧美精品| 欧美精品在线视频| 欧美精品一区三区| 欧美区高清在线| 欧美日韩在线播放三区四区| 欧美日韩一级片在线观看| 欧美视频在线观看免费| 国产精品久久国产愉拍| 国产精品视频网站| 国产亚洲精品aa| 一区二区亚洲精品国产| 亚洲国产成人久久综合一区| 亚洲精品国产精品国产自| 日韩视频免费| 宅男在线国产精品| 欧美亚洲视频一区二区| 久久久夜色精品亚洲| 免费不卡在线视频| 亚洲国产精品国自产拍av秋霞| 日韩视频在线免费| 亚洲视频一二三| 久久精品99国产精品| 免费中文日韩| 欧美日韩精品是欧美日韩精品| 国产精品美女久久久久aⅴ国产馆| 国产亚洲永久域名| 亚洲欧洲精品一区二区| 亚洲欧美bt| 久久久天天操| 亚洲黄色视屏| 午夜日韩福利| 欧美激情第1页| 国产欧美日本在线| 亚洲国产精品小视频| 亚洲免费视频一区二区| 久久视频在线免费观看| 亚洲欧洲日本一区二区三区| 中文在线一区| 美女成人午夜| 国产欧美日韩麻豆91| 日韩视频免费大全中文字幕| 欧美一区二区| 亚洲激情网站免费观看| 欧美一区二区三区免费视| 欧美精品久久一区二区| 激情校园亚洲| 亚洲欧洲av一区二区| 亚洲国产三级| 久久久久综合网| 国产欧美日韩中文字幕在线| 夜夜狂射影院欧美极品| 久久综合伊人| 亚洲欧美成人综合| 欧美日韩亚洲视频一区| 国内精品久久久久影院优| 亚洲欧美一区二区三区久久| 亚洲国产婷婷香蕉久久久久久99 | 欧美成人中文字幕在线| 亚洲一区二区免费在线| 欧美日韩亚洲天堂|