信息學集訓隊作業(yè)

1、IOI2004 中國國家集訓隊第一輪訓練泛做表格SGU湖南沙郡中學107987654321 problem問 n 位數(shù)中有多少個 x，使 x2 的最后 9 個數(shù)字為 987654321對于一個數(shù) a，如果 a2 的最后 9 個數(shù)字為 987654321，則必有(a mod 109)*(a mod 109)的最后 9 位數(shù)字為 987654321，因此，只要用搜索搜出最后的 9 位數(shù)字可能有多少種，將這個數(shù)目乘以前面的可以填的數(shù)字的方案數(shù)就可以了。最后的如下：編號題目名稱題目和簡要算法描述時空性能程度題目評價106The equation求直線 ax + by + c = 0 在矩形(x1,y1

2、)-(x2,y2)內(nèi)經(jīng)過的整點個數(shù)。數(shù)學方法。先解方程，求出一個可行解，然后可以算出有多少個解。但要注意 a,b 中有 0 的情況。O(log2(a+b)很經(jīng)典的題目114ecasting SionX 軸上有 n 個點，每個點都有一個坐標和正整數(shù)的權(quán)值 Vi，要求在 X 軸上找出一點 P，使大的 Self-number直接枚舉判斷。不過在用 x 計算d(x)時要用一點點小優(yōu)化。時，才后悔莫及。109ofDavid Copperfield II有一個 n*n 的格子，第 i 行第 j 列的格子標號為(i-1)*n+j，開始手指指向第一個格子，手指每移動一格只能移到上下左右相鄰的格子內(nèi)，每次可以發(fā)

3、布指令確定手指能移動的步數(shù)，手指移完后將一些格子移走，手指將不能再次移進已移走的格子內(nèi)，但每次可以讓手指移的步數(shù)不能相同且不超過 300，也不允許移走手指所在的格。問怎樣使最后只剩下一個格子且手指在這個格子中。構(gòu)造。首先報數(shù) n，可以把右下角的部分的格子刪掉，然后每次都報一個奇數(shù)，把剩下的格子中靠右下的一條線刪掉，直到最后只剩下(1,1)。O(n2)此題還是比較容易構(gòu)造出來的， 如果可以動的次數(shù)再少一點。出)，然后把不在鏈中的點添到鏈中，設(shè)原鏈為 a1,a2al,在添加 P的過程中，必能找到一個 i，使 ai-1 與 al 有邊，ai 與 P 有邊，這樣只要把 ai 至 al 一段全部倒置就可

4、以了。125Shtirlits有一個 N*N(N3)的矩陣，每個元素的取值范圍是 1 到 9?，F(xiàn)在已知每個元素上、下、左、右比它大的元素個數(shù)，求一個可行的矩陣。搜索，先搜(1,2),(2,1),(2,3),(3,2)，然后再搜四角，最后確定中間O(105*24)由于數(shù)據(jù)范圍比較小，所以怎么搜似乎都能搜出來，但如果把數(shù)據(jù)范圍改大的話。就是 省選拔賽的題目了。126Boxes有兩堆球，第一堆有 A 個，第二堆有 B 個，每次可以從其中一堆移動一些球到另一堆，使另一堆的數(shù)目增倍。問最近能否使其中一堆的數(shù)目變?yōu)?0，如果能，求出要移多少步。模擬。第一次 A,B 必定都是 20 的倍數(shù)，第二次必定都是

5、21 的倍數(shù)，第 k 次必定都是 2k-1 的倍數(shù)，否則無解。這樣模擬起來很快就能得到結(jié)果。O(log2(a+b)一道不錯了模擬題，關(guān)鍵是要想到所模擬的次數(shù)只有 log 級。130Circle圓周上有 2k 個點，要求連 k 條線段，把圓分開，問最少能分成多少份，分成最少份的分法有多少種。組合數(shù)學?？梢苑殖?k+1 份，有(2k)!/(k!*(k+1)!)(Cantlan 數(shù))種分法O(k)比較簡單132Another Chocolate Maniac有一個 M*N 的蛋糕，有些地方不能放巧克力，其他地方都能放。有很多 1*2 和 2*1 的巧克力?，F(xiàn)在要問，最少要放多少巧克力才能使蛋糕上再也

6、放不下巧克力了。動態(tài)規(guī)劃。用 FI,J表示到第 I 行為止，最后一行放的巧克力的狀態(tài)為 J，最少要有多少塊巧克力。其中 J 的表示可以用長為 N 的二進制，每 k 位的數(shù)字 0,1,2,3 分別表示第 I 行第 k 列是不放、放一個橫的巧克力(只會占據(jù)第 I 行的格子)、放一個豎的巧克力且占據(jù)第 I-1行和第 I 行和放一個豎的巧克力且占據(jù)第 I 行和第 I+1 行。這樣每行有 4N 個狀態(tài)，轉(zhuǎn)移也是 4N 的，總的復(fù)雜度可達 M*24N。但有很多狀態(tài)都是沒用的，比如，狀態(tài)數(shù)實際不到 2000 個，可以把有哪些狀態(tài)預(yù)先存下來，然后處理。O(M*24N)想到動態(tài)規(guī)劃并不難，但狀態(tài)有多種表示方法狀

7、態(tài)數(shù)會少一些，但編程復(fù)雜度會高，而有的卻多一些，而編程復(fù)雜度會低一點134Centroid對于一棵二叉樹，它的質(zhì)心指一個結(jié)點 P，以 P 為根，所有子樹結(jié)點個數(shù)中最大的不大于以其他點為根的所有結(jié)點個數(shù)O(m)這一類型的題目好像都是這么出的，然后都是這中最大的。把整棵樹深度優(yōu)先遍歷一遍就可以了。么做的137Funny Strings對于給定的 n,k(n,k 互質(zhì)) ， 求出一列數(shù) s1,s2sn ，使 s1+s2+sn=k，且將 s1 加 1，sn 減 1 后能通過旋轉(zhuǎn)得到原來的數(shù)列。本題可采用枚舉構(gòu)造的方法。對于題中告訴 對于任意的 n,k 互質(zhì)都能構(gòu)造出來，所以，如果 kn，可以將它轉(zhuǎn)化為

8、 n,k mod n 構(gòu)造出一個 s，然后在 s的每一個數(shù)上加 k div n 得出 s，s 必是滿足條件的。這樣， 人為的制造了一個條件 kn。當 kn 時怎么構(gòu)造 s呢？下面給出一個用 0,1 構(gòu)造 s 的方法：由于整列數(shù)是 0,1，將 s1+1,sn-1 后仍是 0 或 1 所以 s1=0，sn=1。設(shè) q1=s1+1=1，qn=sn-1=0，qi=si(1iP。給出 Ni,Pi,Qi,Wi，求一個安排，使得能參加下一次比賽的選手權(quán)值和最大。貪心，每次盡量使權(quán)值大的選手，如果第 i 個選手要進入，這把他安排在滿足 PiQi 條件且 Pi 最大的一個沒有安排別人的地方。否則將它放在一個 P

9、i 最大的地方。O(n*k)一道不錯的貪心題173Coins有一排硬幣，有的 朝上，有的正面朝上，分別為 0 和 1 表示。給出一列數(shù) A1.Ak-1，一個操作對 Si、Di，是指將從第 Si 開始的 k 個硬幣進行 Di 次變換。對于 k 個硬幣的一次變換是指：首先把這 k 個硬幣循環(huán) 一位， 然后對于第 p 個硬幣 (1pk-1)，如果它正面朝上且對應(yīng)的 Ap 是 1，則把第 k 個硬幣翻轉(zhuǎn)?，F(xiàn)在不知道最初始的序列，也不知道 A，只知道 l 組(每組都是 k 個)硬幣經(jīng)過一次變換后分別的結(jié)果、操作的順序和最后的硬幣狀態(tài)。問初始的狀態(tài)是怎樣的。首先列方 A，然后從后向前推。中間的過程可以用矩

10、陣的乘法實現(xiàn)，可以用二分降低復(fù)雜度。O(lk2+mk3log2 maxD)出題人好“要不得”，把一個矩陣搞得亂七八糟的，看題好痛苦。然后還要先把解方程做題程序的預(yù)處理。174Walls給出 n 條線段，除端點外，它們無交點。問取前多少條線段可以圍成一個圈。采用并查集。連一條線段相當于將兩個點所在的集合合并，如果兩個點已在一個集合中，則產(chǎn)生的圈。由于要判斷哪些點是同一個點，因此要對所有的點排序。O(mlog2m+m)似乎算法比較容易想到，可選擇對邊并查集還是對點并查集就得考慮一下176Flow Construction給出一個網(wǎng)絡(luò)，要求對網(wǎng)絡(luò)求一個最小的流，使某些規(guī)定的路一個容量有上下界的網(wǎng)徑上

11、必須流滿。容量有上下界的網(wǎng)絡(luò)流。絡(luò)最小流的特例。177Square有一個 n*n 的白 域，每次給一個四邊平行于區(qū)域邊界且四頂點都是整點心的矩形染色，每次只能染成白色或黑色。問最后白色的區(qū)域有多大。用四叉線段樹。O(n2log2n)好強的題目，可以用四叉樹也可以用二維線段樹。178Golden Chain有一條長度為 n 個項鏈，要求從中斷出最少個數(shù)的 1，使得 1至 n 中的所有數(shù)都能用整條整條的項鏈表示出來。數(shù)學方法?？梢郧蟪鰯?i 次最多可以處理的 n 最大為 2i+1*(i+1)，然后枚舉 i 即可求出要多少個。O(log2n)此題很容易想到要用到二進制，很難想到枚舉答案然后看 是否滿

12、足條件的方法179Brackets light給出一個只含(,)的正確表達式，設(shè)字符(字符)，求出與它等長的字典序正好在它后面的表達式。構(gòu)造。找出一個最大的 i，使輸入表達式的第 i 個字符為(，且第 i個字符及后面的字符中(的個數(shù) t0 小于)的個數(shù) t1，第 i 位前面的串原樣輸出，緊接著輸出 t0 個(和 t1 個)即可。O(Len)一道不錯的題目182Open the brackets給出一個可帶括號的表達式，求出一個與它等價的不帶括號的表達式。把所有可能為真的狀態(tài)都記下來，然后對于每一種狀態(tài)都用&把每個變量和它應(yīng)該對應(yīng)的值連起來，最后很有狀態(tài)間用|連接即可?？瓷先ズ苡袑嶋H意義的題目，

13、居然算法是這樣的。183Paing the balls有一排球，給每個球涂色都需要不同的顏料數(shù)，現(xiàn)在要用最少的顏料給一些球涂色，要求任意相鄰的 M 個球都至少有兩個被涂色。動態(tài)規(guī)劃。用 Fi,j表示最后一個球放在 i 位置，倒數(shù)第二球放在 i-j位置且從第 1 至第 i 個位置都已滿足任意相鄰的 M 個球都至少有兩個被涂色最少需要多少顏料。則 Fi,j=minFi-j,k+ci(0km-j)，其中 ci表示涂第 i 個球所需的顏料數(shù)。復(fù)雜度為 O(n*m2)。從方程可以看出，如果用 Di,j表示最后一個球放在 i 位置，倒數(shù)第二球放在 i-j 位置至 i-1 位置之中的一個位置且從第 1 至第

14、 i 個位置都已滿足任意相鄰的 M 個球都至少有兩個被涂色最少需要多少顏料。則 Di,j=Di-j,m-j+ci，復(fù)雜度降為 O(m*n)。O(n*m)怎樣想到用動態(tài)規(guī)劃、怎樣表述狀態(tài)、怎樣能優(yōu)化都是本題的難點187Twist and whirl有 n 個數(shù)排成一列依次為 1,2,n，每次給出一對 Pi,Qi，將數(shù)列的第 Pi 項到第 Qi 項倒過來，m 次后，要求輸出這列數(shù)。首先把這 n 個數(shù)分成185Two shortest給出一個無向圖，找出兩給出的兩個結(jié)點之間的兩條最短最徑。要求它們之間沒有任何邊相同（可以有頂點相同）。Dijkstra+搜索。先求一條最短路，然后用廣搜再找一條，這中間

15、可能要類似網(wǎng)絡(luò)流的處理“后向弧”。O(m)一條最短路太簡單的，兩條最短路卻不簡單205zation Problem給出一列數(shù) Si 和一個 m*s 的矩陣 A(ms 且 m,s 都是 2 的整數(shù)次方)。求一列數(shù) Ki，使 K0=0，且Hanoi Revisited動態(tài)規(guī)劃。用 Fi,j表示把標號連續(xù)的 i 個盤子用 j 個根柱子從一根柱子上完全轉(zhuǎn)移到另一根柱子上最少要移動的步數(shù)。則 Fi, j=minFi-k,j-1+Fk,j*2(1ki-1)。把路徑 下來，可以根據(jù)路徑構(gòu)造出怎么移動的。劃就不難了203Hyperhuffman給出一每段代碼的出現(xiàn)頻率，問用它們的 Huffman 樹的權(quán)值是多

16、少。模擬。直接模擬 Huffman 的建樹方法，使用兩個線性表，一個輸入序列，一個中間產(chǎn)生的序列(每次產(chǎn)生的權(quán)值都必定比以前產(chǎn)生的要大)就可以了。O(n)204Little Jumper如圖，在一塊地上有兩堵墻距離為 l 的墻，每個墻上都有一個洞，左邊墻上洞的上口和下口分別距地高 t1 和 b1，另一個洞的上口和下口分別距地高 t2 和 b2，現(xiàn)在要從左墻左邊距離為 Ds 的地方跳到右墻右邊距離為 Df 的地方，中間經(jīng)過兩墻的中間位置一次，問求兩次跳躍的速度的最大值最小是多少。三分中間的落腳位置。由于中間位置從左到右變換時，第一次跳躍所需的最小速度和第二次跳躍所需的最小速度都是單峰的凹函數(shù)，它

17、們?nèi)∽畲笾等匀皇菃畏宓陌己瘮?shù)，這樣求最小值很容易了。精度處理好痛若動態(tài)規(guī)劃。用 Fa,b表示 Ka 取 b 時有位都是 0，每次加上一個 2 的整數(shù)次冪，要求對這些加法進行進位處理，使任一次的進位次數(shù)不超過 4 次。構(gòu)造?？梢允沟萌我鈨蓚€ 2 之間都至少有一個 0，這個是可以構(gòu)造出來的。如果當前位置 P 上已經(jīng)是 2，則變換 P+1 和 P 位置上的數(shù)，把 X2變?yōu)?X+1)1。如果當前位置 P 上是 0，則把 0 變?yōu)?1，再把前面最近的一個 X2 變?yōu)?X+1)0。如果當前位置 P 上是 1，要分兩種情況：若 P+1 位是 2，則把 P+2,P+1和 P 位上的數(shù)由 X21 變?yōu)?X+1)

18、02。否 P+1 位不是 2，則把 X1 變?yōu)?(X+1)0，再把 P+2 以前最近的一個 X2 變?yōu)?X+1)0。至少有一個 0”的時候才然大悟哦，原來我也可以做出來212Daransmis有一個分層圖，求一個流，從起點到終點的流，它不存在有錢相弧 的增廣軌。構(gòu)造。每一次讓盡量多的流流向下一層，直道流到終點為止。中間過程中沒有流完的流可以沿原路返回。直到有一個分叉，可以往下一層流時，再往 。這個算法的關(guān)鍵就是要減少流的次數(shù)，如果一次流可以使得某一條邊飽和，那么流是很劃算的，就流，如果不飽和，這樣可能增加流的次數(shù)，就暫時不流而把它堆積在這個節(jié)點上。無話可說。213Strong Defence給

19、出一個圖，對于圖中的兩個頂點 S 和 T。問最多能從這些邊中找出多少子集，使任意兩個子集不相交，且去掉任意子集中的所有邊 S 和 T 都不連通。廣搜。能找到的子集數(shù)為 S 到 T 的最短路徑長度 L。以 S 為根結(jié)點，建立一根樹，每個結(jié)點的深度都是它到 S 的最短距離的長度+1。然后，第 1 至第 L 層每層的邊分為一個子集，其他的邊可以不必考慮。O(m)似乎比較容易214Weird Dissimilarity設(shè)字母表中兩個字母之間都有一個“距離”，、 的距離為 V,，距離由輸入輸入給出。給出兩個串 S1,S2，要求通過對每個串添加或不加一些字符使兩個串的長度相等，且對應(yīng)位置上的字母的距離之和最小。動態(tài)規(guī)劃。用 Fi,j表