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

coreBugZJ

此 blog 已棄。

POJ 1067 取石子游戲

  1/*
  2POJ 1067 取石子游戲
  3
  4
  5----問題描述:
  6
  7有兩堆石子,數量任意,可以不同。游戲開始由兩個人輪流取石子。游戲規定,每次有兩種不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者。現在給出初始的兩堆石子的數目,如果輪到你先取,假設雙方都采取最好的策略,問最后你是勝者還是敗者。
  8
  9
 10----輸入:
 11
 12輸入包含若干行,表示若干種石子的初始情況,其中每一行包含兩個非負整數a和b,表示兩堆石子的數目,a和b都不大于1,000,000,000。
 13
 14
 15----輸出:
 16
 17輸出對應也有若干行,每行包含一個數字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(轉自網上,略有修正)
 37
 38大致看完題目,想當然就知道這是一道博弈論的問題,最容易想的就是直接用博弈論的必敗、必勝態進行動態規劃求解。但是樸素的動態規劃是 O(N * M) 的,如果做一些優化可能可以過掉 RQNOJ 的題目,但是對于 POJ 1067 來說就完全無能為力。所以我們嘗試分析數據,看看有沒有什么規律(以下用 (a, b) 表示兩堆石子的個數,即游戲中的一個狀態)。
 39
 40列舉了幾個狀態之后容易發現,必勝態的數目比必敗態要多很多,所以我們先手工求出前幾個必敗態:
 41
 42(1, 2)、(2, 1)、(3, 5)、(5, 3)、(4, 7)、(7, 4)、(6, 10)、(10, 6)……
 43
 44首先回顧必勝態和必敗態的樸素求法:
 45
 46定理 0:一個狀態是必敗態,當且僅當它的所有后繼狀態都是必勝態;而一個狀態是必勝態,只要它的后繼狀態有一個以上的必敗態即可。
 47
 48證明略去。
 49
 50容易發現下面的定理:
 51
 52定理 1:(a,b) 和 (b, a) 的勝負性是相同的(a <> b)。
 53
 54證明:如果 (a, b) 是必勝態,那么將必勝策略中所有的操作,對第一堆的變為第二堆,對第二堆的變為第一堆,就構成 (b, a) 的必勝策略
 55
 56定理 2:若 (a, b) 是必敗態,則對于所有的 x <> a 和 y <> b,(x, b) 和 (a, y) 是必勝態。
 57
 58證明:
 59
 60對于 x > a 和 y > b,不管是哪一種情況,總可以從 x 堆或 y 堆中取出一定量的石子使當前狀態變為必敗態 (a, b),由定理 1,(x, b) 和 (a, y) 為必勝態。
 61
 62對于 x < a 和 y < b,不管是哪一種情況,如果 (x, b) 或 (a, y) 是必敗態的話,由上述可得 (a, b) 是必勝態,矛盾。故 (x, b) 和 (a, y) 均為為必勝態。
 63
 64定理 3: 若 (a, b) 是必敗態,則對于所有的 d > 0,(a + d, b + d) 是必勝態。
 65
 66證明:
 67
 68與定理 2 類似。
 69
 70定理 4:在所有的必敗態中,每個數字恰巧出現一次。
 71
 72證明:
 73
 74有了定理 1,對于對稱的狀態我們只需要處理其中一個,而兩個數不會相同(相同的狀態必然是必勝態),于是我們把每個狀態中較小的數字放在前面,每行寫一個狀態,去掉括號并按照升序排列每行的第一個數,就構成了如下的矩陣:
 75
 761  2
 77
 783  5
 79
 804  7
 81
 826  10
 83
 84……
 85
 86觀察這個矩陣,我們又可以得到新的定理:
 87
 88定理 5:矩陣中每行第一個數恰巧是前面每一行中沒有出現過的最小正整數。
 89
 90證明:
 91
 92由定理 4,矩陣中每個數字恰巧出現一次,而按照這個矩陣的定義,第二列的數總比同行第一列大,第一列又按照升序排列,所以每一行的第一個數正好為前面每一行中沒有出現過的最小正整數。
 93
 94定理 6:矩陣第 i 行的第二個數正好為第一個數加上 i
 95
 96證明:
 97
 98用數學歸納法。
 99
1001) 對于第一行顯然成立
101
1022) 若對于前 i - 1 行均成立,則所有的 (a[p], a[p] + p) (a[p] 為第 p 行第一個數,p < i) 均為必敗態,那么考察第 i 行的狀態 (a[i], a[i] + delta)。容易看出 delta >= i,因為如果 delta < i,一定可以通過一次操作變為前面出現過的必敗態,那么這個狀態就是必勝態。下面由 delta >= i,我們來說明 delta = i。
103
104首先,我們考慮從第一堆中取出 p 個石子,得到狀態 (a[i] - p, a[i] + delta),由定理 5,比 a[i] 小的數都在之前出現過,若 a[i] - p 出現在某一行的第一列,由于存在必敗態 (a[i] - p, a[i] - p + d) (d < delta),故 (a[i] - p, a[i] + delta) 一定為必勝態(定理 2);若 a[i] - p 出現在某一行的第二列,由于第一列是單增的,因而其對應的第一列數必小于 a[i] + delta,故而也可推出其狀態為必勝態。
105
106對于從兩堆石子中取出相同數目的情況與之類似,容易看出一定為必勝態。
107
108于是,(a[i], a[i] + delta) 狀態的勝負性只與狀態 (a[i], a[i] + d) (d < delta) 有關。不難看出,delta = i 時恰為必敗態,因為不論從第二堆中取出多少個石子,作為另一堆的第一堆石子并沒有在之前出現過,所以得到的一定是一個必勝態,因而 (a[i], a[i] + delta) 為必敗態,由定理 2 及定理 4 可得,原命題成立。即矩陣中第 i 行第二列的數等于同行第一列的數加上 i。
109
110
111這時,我們所有的問題都轉化到了矩陣上,只要能通過合適的方法表示出這個矩陣,我們就可以很好地解決原問題。
112
113下面的過程可能需要比較高的數學技巧,首先給出我們需要的一個重要定理([x] 表示 x 的整數部分,{x} 表示 x 的小數部分,即 {x} = x - [x]):
114
115定理 7(Betty 定理):如果存在正無理數 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+ 中的每個數都恰好出現一次,這與上述矩陣的性質十分吻合。于是我們猜想每一行第一列的數滿足 [Φi] 的形式。
120
121于是我們得到每一行第二列的數為 [Φi] + i = [Φi + i] = [(Φ + 1)i]
122
123我們的目的是要讓 Z+ 中每個數都在這個矩陣中出現,于是考慮到 Betty 定理的條件,Φ 和 (Φ + 1) 應滿足 1/Φ + 1/(Φ + 1) = 1。解這個方程,我們得到 Φ = (sqrt(5) + 1) / 2,于是 Φ + 1 = (sqrt(5) + 3) / 2。
124
125Φ 恰為黃金分割比,這是多么令人驚奇的結論!
126
127于是應用 Betty 定理,我們得到最終我們需要的定理:
128
129定理 8:上述矩陣中每一行第一列的數為 [Φi],第二列的數為 [(Φ + 1)i],其中 Φ = (sqrt(5) + 1) / 2 為黃金分割比。
130
131證明:由 Betty 定理顯然得證。
132
133 
134
135有了定理 8,代碼的實現就十分簡單了,由于是數學算法,總復雜度為 O(1)。至此,本題完美解決。
136
137
138總結:遇到這樣困難的題目時,我們不應該輕言放棄。而應該仔細分析題目隱含的信息,學會分析和轉化問題,從而找到問題的突破口,一舉殲滅問題。
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 閱讀(5481) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲美女福利视频网站| 欧美日韩国产黄| 欧美成人免费全部观看天天性色| 亚洲国产美女| 欧美激情一区二区三级高清视频| 欧美巨乳在线观看| 亚洲视频999| 亚洲毛片一区| 夜色激情一区二区| 中文精品一区二区三区| 亚洲一二三区在线| 欧美一级午夜免费电影| 亚洲福利视频在线| 欧美第一黄网免费网站| 欧美成人中文字幕在线| 亚洲国产成人久久综合| 亚洲激情视频在线| 亚洲视频二区| 久久精品成人| 欧美r片在线| 欧美体内she精视频| 国产精品爽黄69| 狠狠色丁香久久综合频道| 很黄很黄激情成人| 亚洲黄色三级| 亚洲免费在线观看视频| 在线亚洲精品福利网址导航| 在线亚洲精品| 欧美亚洲免费| 免费成人激情视频| 亚洲靠逼com| 亚洲综合国产激情另类一区| 欧美一区二区三区视频在线观看| 久久九九国产精品| 欧美日韩国产欧| 国产欧美精品日韩精品| 永久免费毛片在线播放不卡| 99天天综合性| 久久综合色播五月| 亚洲精品中文字幕有码专区| 香港成人在线视频| 欧美久久一区| 经典三级久久| 一区二区三区高清不卡| 欧美亚洲免费| 最新成人av在线| 欧美xart系列高清| 亚洲一二三区精品| 免费黄网站欧美| 国产欧美日韩专区发布| 99热免费精品| 欧美成人首页| 欧美一区二区| 欧美性开放视频| 亚洲乱码国产乱码精品精天堂| 亚洲日本va在线观看| 香蕉久久一区二区不卡无毒影院| 亚洲第一区在线| 久久久久国产成人精品亚洲午夜| 国产精品乱子乱xxxx| 老司机免费视频一区二区三区| 亚洲欧洲精品一区二区| 亚洲国产视频直播| 久久国产一区二区三区| 欧美性色综合| 91久久黄色| 久久久99国产精品免费| 一本大道久久a久久综合婷婷| 久久免费国产精品1| 国产一区二区三区视频在线观看| 亚洲精品社区| 亚洲国产精品一区二区久| 久久蜜桃精品| 在线观看欧美日本| 亚洲国产美女精品久久久久∴| 欧美在线你懂的| 国产精品成人免费| 久久不射电影网| 久久久国产精品亚洲一区 | 国产农村妇女精品一二区| 性娇小13――14欧美| 亚洲欧美自拍偷拍| 悠悠资源网久久精品| 亚洲激情第一区| 欧美性理论片在线观看片免费| 亚洲免费一在线| 久久精品女人| 日韩亚洲欧美中文三级| 亚洲天堂成人| 亚洲第一天堂av| 99国产麻豆精品| 国内不卡一区二区三区| 亚洲国产成人一区| 国产精品三上| 亚洲福利视频网| 国产精品入口麻豆原神| 欧美激情女人20p| 国产精品入口日韩视频大尺度| 久久这里有精品视频| 欧美日韩国产首页| 久久亚洲图片| 欧美视频在线观看一区| 久久综合中文| 国产精品白丝黑袜喷水久久久| 久久免费视频一区| 欧美午夜精品久久久久久超碰| 久久综合综合久久综合| 国产精品蜜臀在线观看| 欧美激情视频在线免费观看 欧美视频免费一| 欧美区一区二区三区| 六月婷婷一区| 国产午夜精品全部视频播放| 亚洲六月丁香色婷婷综合久久| 国语自产在线不卡| 亚洲午夜精品视频| 99精品视频一区| 久久免费视频观看| 久久久久久一区二区| 欧美三级网址| 亚洲福利专区| 蜜臀av国产精品久久久久| 国产精品白丝黑袜喷水久久久| 麻豆精品在线视频| 国产一区二区三区电影在线观看| 日韩网站在线| 亚洲人体一区| 久久综合九色综合欧美就去吻| 久久精品国产精品亚洲综合| 国产精品国产a级| 一本色道久久综合亚洲精品婷婷| 日韩写真视频在线观看| 男男成人高潮片免费网站| 免费成人高清视频| 亚洲高清在线视频| 久久婷婷国产综合国色天香| 久久久蜜桃精品| 国产日韩在线看| 欧美一区二区三区四区在线观看地址 | 免费看黄裸体一级大秀欧美| 国产一区二区三区直播精品电影| 亚洲免费一区二区| 久久国内精品自在自线400部| 国产精品资源在线观看| 午夜视黄欧洲亚洲| 久久天堂国产精品| 亚洲国产天堂久久综合网| 欧美国产大片| 一区二区三区产品免费精品久久75 | 亚洲视频网站在线观看| 亚洲视频综合在线| 国产精品久久久久久久久久久久久| 在线午夜精品| 久久精品夜色噜噜亚洲aⅴ| 国产亚洲欧洲一区高清在线观看| 欧美一区二区三区视频免费| 久久久久久欧美| 亚洲三级电影在线观看| 欧美日韩三级在线| 午夜一级在线看亚洲| 久久综合影音| 99精品免费视频| 国产精品一区二区黑丝| 久久久91精品国产一区二区三区 | 男人天堂欧美日韩| 亚洲日韩视频| 欧美日韩在线高清| 欧美一级大片在线观看| 欧美成人午夜影院| 亚洲欧美日本在线| 欧美午夜免费电影| 校园春色综合网| 欧美大片免费观看| 亚洲欧美文学| 亚洲国内在线| 国产精品自在欧美一区| 免费91麻豆精品国产自产在线观看| 99re这里只有精品6| 久久深夜福利免费观看| 亚洲一区二区综合| 亚洲激情偷拍| 国产综合网站| 国产欧美 在线欧美| 欧美久久99| 久久久久欧美| 欧美日本在线播放| 亚洲欧美日韩国产综合在线| 欧美成人精品在线播放| 亚洲综合精品| 亚洲国产精品综合| 国产日产亚洲精品系列| 欧美理论电影网| 久久综合色88| 久久9热精品视频| 一区二区精品国产| 亚洲韩日在线| 欧美黄色片免费观看| 久久久久久成人| 午夜精品久久久久99热蜜桃导演| 亚洲精品日韩欧美| 亚洲人成人一区二区三区|