• <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>
            

    
            

            




            







												


        


            


            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)?、必勝態(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 閱讀(5447) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



97久久超碰成人精品网站|
中文精品久久久久国产网址|
www亚洲欲色成人久久精品|
久久精品国产色蜜蜜麻豆|
久久精品无码一区二区三区免费
|
久久伊人精品青青草原高清|
热久久视久久精品18|
国产午夜精品理论片久久|
国产99久久精品一区二区|
久久久av波多野一区二区|
99精品国产综合久久久久五月天|
亚洲国产婷婷香蕉久久久久久
|
91精品国产高清久久久久久国产嫩草
|
欧美日韩精品久久久免费观看|
久久99精品久久久久久齐齐|
国内精品久久久久久久coent
|
久久se精品一区二区影院|
色综合色天天久久婷婷基地|
久久亚洲欧美日本精品|
99久久精品国产综合一区|
色综合合久久天天综合绕视看
|
亚洲国产精品人久久|
久久91精品国产91久久麻豆|
91久久成人免费|
久久精品人妻一区二区三区|
香蕉久久AⅤ一区二区三区|
婷婷国产天堂久久综合五月|
亚洲综合熟女久久久30p|
久久精品国产亚洲av高清漫画|
国内精品久久人妻互换|
色综合久久最新中文字幕|
久久久久国产日韩精品网站|
综合久久久久久中文字幕亚洲国产国产综合一区首|
久久久久国产精品麻豆AR影院|
伊人情人综合成人久久网小说|
中文字幕日本人妻久久久免费|
国产精品美女久久久久久2018|
久久精品无码一区二区三区免费
|
一本色道久久88综合日韩精品|
人妻丰满AV无码久久不卡
|
精品久久久久久久久久久久久久久|