國家集訓(xùn)隊2005論文集 朱晨光

《國家集訓(xùn)隊2005論文集 朱晨光》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光引言它的本質(zhì)思想是每次根據(jù)已經(jīng)得到的信息，將考慮的范圍擴大一倍，從而加速操作。倍增思想是一種十分巧妙的思想，在當(dāng)今的信息學(xué)競賽中應(yīng)用得十分廣泛。引言在解決信息學(xué)問題方面，倍增思想主要有這兩個方面的應(yīng)用——一、在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移二、加速區(qū)間操作倍增思想應(yīng)用之一在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移首先，讓我們來看一個簡單的例子——已知實數(shù)a，計算an。很顯然，一種最簡單的方法就是令b=a，然后重復(fù)(n-1)次進行操作b=b*a.這樣，為了得到an，共進行了(n-1)次乘法?，F(xiàn)在考慮另外一種方法

2、例一將n表示成為二進制形式并提取出其中的非零位，即n=2b1+2b2+……+2bw，不妨設(shè)b1

3、轉(zhuǎn)移等）。但是只要符合以下兩個條件，就可以應(yīng)用倍增思想并采用類似于上面的方法加速計算：小結(jié)一一、每次的變化規(guī)則必須相同二、變化規(guī)則必須滿足結(jié)合律具體到上面的例子，每次的變化規(guī)則都是乘法，而乘法是滿足結(jié)合律的。下面將通過例二更加深入地探討倍增思想在加速狀態(tài)轉(zhuǎn)移方面的應(yīng)用，同時得到更精確的定義。例二骰子的運動給定一個六個面的骰子，每個面上都有一定的權(quán)值（1到50之間的整數(shù)）。骰子運動的范圍是一個寬度為4，向左右無限延伸的帶子。帶子從左到右的橫坐標值為……，-3，-2，-1，0，1，2，3，……，從前到后的縱坐標值依次為1，2，3，4。這樣，帶子被分成了無限多個格子。每

4、個格子恰好能與骰子的一個面完全重合。骰子每次可以向前后左右中的一個方向滾動一格，但不能移出帶子，花費是滾動后朝上的面所附帶的權(quán)值。例二骰子的運動給定當(dāng)前骰子位置的坐標與各個面的朝向，求將這個骰子移動到某個新位置所需的最小花費。（所給橫坐標的絕對值小于等于109）。分析如果不考慮橫坐標巨大的差值，本題完全可以用動態(tài)規(guī)劃求解。方法是將每一格按照骰子的朝向拆分成24種狀態(tài)，然后按列進行動態(tài)規(guī)劃得到最小花費。具體方法是從起點所在列的24*4=96個狀態(tài)推到第二列96個狀態(tài)，再推到第三列，第四列……，一直推到終點所在的列。每次都用Dijkstra算法算出從一列中某個狀態(tài)轉(zhuǎn)移

5、到相鄰的一列中某個狀態(tài)的最小花費。時間復(fù)雜度是與橫坐標差值n是同階的。分析但是，由于n最大可達109，所以這個算法無論從時間還是空間上都難以滿足要求。那么，是否可以采用倍增思想呢？答案是肯定的！下面，我們來驗證這里是否存在一種變化規(guī)則符合運用倍增思想的要求——相同并符合結(jié)合律。分析設(shè)骰子從第1列某個狀態(tài)A運動到第2列某個狀態(tài)B最少需要花費代價c,則骰子從第2列的狀態(tài)A運動到第3列的狀態(tài)B同樣最少需要花費代價c！這就是一種“相同的變化規(guī)則”！更一般地，如果骰子從第i列某個狀態(tài)A運動到第(i+k)列某個狀態(tài)B最少需要花費代價c，則骰子從第j列的狀態(tài)A運動到第(j+k)

6、列的狀態(tài)B也最少需要花費代價c.分析又由于前面所給出的算法是動態(tài)規(guī)劃，而動態(tài)規(guī)劃一個很重要的特點是具有最優(yōu)子策略。階段ⅠA段B段C段階段Ⅱ階段Ⅲ階段Ⅳ階段Ⅴ分析至此，我們證明了變化規(guī)則既滿足相同性又滿足結(jié)合律，可以運用倍增思想解決：……A……B……a1分析……a1……a2……a4…………分析*………………**…………初始狀態(tài)……目標狀態(tài)*……*分析本題中，Dijkstra算法所耗費的時間可以看成是常數(shù)（根據(jù)題目中骰子各面權(quán)值的取值范圍可以算出必須考慮的點數(shù)為常數(shù)），每次倍增的時間為963，而倍增的次數(shù)為log2n，所以上述算法的時間復(fù)雜度為O(963log2N)。

7、小結(jié)二從上題中，我們進一步加深了對倍增思想的理解，并且糾正了一個以前錯誤的認識：倍增思想所作用的對象實際上是變化規(guī)則，而并非具體的狀態(tài)！倍增思想的作用是算出一個狀態(tài)到另一個狀態(tài)的變化量。也就是說，倍增思想計算出的量與具體的狀態(tài)是無關(guān)的，而僅與狀態(tài)之間的關(guān)系有關(guān)。小結(jié)二將這個過程寫成偽代碼就是：DoublingAlgorithm(A,n){//a,b,c均為變化規(guī)則，a的初值由其他算法得到。如例2中a由Dijkstra算法得到c=b=a;while(n){if(n%2)c=c?b;b=b?b;n/=2;}B=A*c;returnB;}（A為原狀態(tài)，B為末狀態(tài)?！盃顟B(tài)

8、*變化規(guī)則