pascal算法講義第九講

1、第九講 分治算法一、分治思想分治思想融入于常見算法的各個(gè)角落,簡(jiǎn)單點(diǎn)說,所謂的分治 , 實(shí)際上是將一個(gè)問題拆成若干個(gè)小問題 , 將它們分別解決后 , 就等價(jià)于 解決了整個(gè)問題。二、快速冪算法與分治思想(底下部分的 表示乘方 求 2233(mod 1,000,000,007這個(gè)問題我們可以這么考慮2233 = 2116 * 2116 * 2那么原來問題就轉(zhuǎn)化為求 2116(mod 1,000,000,007就這樣下去 , 我們只要求得 252即可 , 也就是說 226即可換句話說 , 我們求得 213即可 , 也就是說 26 * 26 * 226 = 23 * 2323 = 21 * 21 *

2、2 = 8所以 26 = 8*8=64213 = 26 * 26 * 2 = 64 * 64 * 2 = 8192就這樣我們逐步回推 , 可以得到 2233當(dāng)然注意要取模*你可以說這個(gè)算法是遞歸 , 但是這個(gè)也可以說是”拆成若干個(gè)小問題” *三、一道 NOIP2007的例題本題摘自 NOIP 2007 普及組 初賽 (完善程序第二題 大家可以暫時(shí)思考一下 本題中 , 我們只要求構(gòu)造一種方案所以 , 這個(gè)題我們可以采取分治的策略來解決首先 , 我們思考一下 , 這一題的特殊條件1, 我們用的是 2的 k 次方 *2的 k 次方的格子2, 這一題中 , 有一個(gè)” -1”的存在那么 , 我們就可以用

3、一種特殊的策略首先 , 如果 k=0,那么就不 用構(gòu)造了 , 皆大歡喜所以 , 我們想辦法將 2k改為2(k-1即可我們可以將原來的正方形切成四個(gè) , 如右圖所以 , 這時(shí)候 , 我們可以將三個(gè)” 1”當(dāng)作 -1, 帶入到右上 , 右下 , 左下 處理 , 將” -1”依舊留在左上角這樣 , 問題就轉(zhuǎn)化成了一個(gè) 2(k-1規(guī)模的然后 .(本圖中為了較為清晰的顯示 , 將 1316與 1821略去了 所以 , 這樣就將原來問題分治出來了那么 , 這一個(gè)問題就得到了解決四、一道來自 codeforces 的例題這一題摘自 Codeforces 321C題面 :英文版 :C. Ciel the Co

4、mmandertime limit per test1 second memory limit per test256 megabytesinputstandard inputoutputstandard outputNow Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has n cities connected byn -1 undirected roads, and for any two cities there always exists a path between them.Fo

5、x Ciel needs to assign an officer to each city. Each officer has a rank a letter from 'A' to 'Z'. So there will be 26 different ranks, and 'A' is the topmost, so 'Z' is the bottommost.There are enough officers of each rank. But there is a special rule must obey: if x

6、and y are two distinct cities and their officers have the same rank, then on the simple path between x and y there must be a city z that has an officer with higher rank. The rule guarantee that a communications between same rank officers will be monitored by higher rank officer.Help Ciel to make a v

7、alid plan, and if it's impossible, output "Impossible!".InputThe first line contains an integer n (2 n 105 the number of cities in Tree Land.Each of the following n -1 lines contains twointegers a and b (1 a,b n,a b they mean that there will be an undirected road between a and b. Consi

8、der all the cities are numbered from 1 to n. It guaranteed that the given graph will be a tree.OutputIf there is a valid plane, output n space-separated characters in a line i-th character is the rank of officer in the city with number i. Otherwise output "Impossible!".Examplesinput41 21 3

9、1 4outputA B B Binput101 22 33 44 5百度 Pascal 吧公開培訓(xùn)教材-Pascal 培訓(xùn)課程算法講義-第九講 56 67 78 89 9 10 output DCBADCBDCD Note In the first example, for any two officers of rank 'B', an officer with rank 'A' will be on the path between them. So it is a valid solution. 中文題意: 給你 n 個(gè)點(diǎn),求構(gòu)造一個(gè)方案,使得每個(gè)點(diǎn)存在一個(gè)A到Z 的權(quán)值 任意兩個(gè)權(quán)值為 x(x 從A到Z的點(diǎn)之間,一定存在至少一 個(gè)權(quán)值比 x 大的點(diǎn) 如果無解,輸出”Impossible!” 注意:A比BZ大,B比CZ大Y比 Z大 如果不懂,可以觀察樣例 所以,這道題我們?cè)撛趺醋瞿? 我們仔細(xì)觀察 A是最大的,也就是說,最多只有一個(gè)A 第 6 頁，共 7 頁 百度 Pascal 吧公開培訓(xùn)教材-Pascal 培訓(xùn)課程算法講義-第九講 那么我們每次選一個(gè)點(diǎn) , 將它當(dāng)作最大的