[學(xué)習(xí)]算法分析與設(shè)計(jì)課件：習(xí)題選講1bywxyz

1、算法分析習(xí)題選講,,2012-9-20,2,,Sicily 地址: http://soj.me,2012-9-20,3,題目,1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Biker's Trip Odomete1198 Substring1176 Two Ends1433 O

2、ptimal Parking1325 Digit Generator,2012-9-20,4,1020 Big Integer,題目大意：給出n個(gè)整數(shù)b1,b2,...,bn，和一個(gè)大整數(shù)x，求x對(duì)每個(gè)數(shù)bi取模的結(jié)果。n<=100, 1<bi<=1000, x的長(zhǎng)度不超過(guò)400。,2012-9-20,5,1020 Big Integer,解題思路：對(duì)bi逐個(gè)計(jì)算；高精度，模擬豎式計(jì)算。int div(ch

3、ar x[], int b) {int a=0;for (int i=0;x[i]!='\0';i++) {a=(a*10+x[i]-'0')%b;return a;},2012-9-20,6,1021 Couple,題目大意：N對(duì)夫婦站成一圈如果某對(duì)夫婦站在相鄰位置，則從圈中移走重復(fù)以上操作問(wèn)最后會(huì)不會(huì)沒(méi)人如1 3是一對(duì)，2 4是一對(duì)，則No如1 4是一對(duì)，2 3是一對(duì)，

4、則Yes1<=N<=100,000,2012-9-20,7,1021 Couple,解題思路：類(lèi)似于括號(hào)匹配，可將n對(duì)夫婦看成n種括號(hào)用一個(gè)棧來(lái)模擬，將括號(hào)逐個(gè)push到棧里當(dāng)棧頂存在匹配對(duì)時(shí)進(jìn)行pop操作看最后棧是否為空,2012-9-20,8,1021 Couple,如1 3是一對(duì)，2 4是一對(duì),最后棧不為空，輸出No,2012-9-20,9,1021 Couple,如1 4是一對(duì)，2 3是一對(duì),1,1,2,1

5、,2,3,1,1,4,最后棧為空，輸出Yes,2012-9-20,10,1021 Couple,stack s;for (int i=1;i<=2*n;i++) {if (!s.empty()&&s.top()==couple[i])s.pop();elses.push(i);},2012-9-20,11,1027 MJ, Nowhere to Hide,題目大意：給出N對(duì)BBS_ID I

6、P_Address，求出IP_Address相同的BBS_ID。N<=20,2012-9-20,12,1027 MJ, Nowhere to Hide,解題思路：枚舉每?jī)蓚€(gè)BBS_ID IP_Address對(duì)，比較IP_Address是否相同；字符串比較。for (int i=0;i<n;i++) { for (int j=i;j<n;j++) if (strcmp(ip[i],ip[j

7、])==0) ans[cnt++]=make_pair(id[i],id[j]);},2012-9-20,13,1035 DNA matching,題目大意：給出n個(gè)DNA單鏈，問(wèn)可以用這些DNA單鏈組成多少個(gè)DNA雙鏈；每個(gè)DNA單鏈最多使用一次；兩個(gè)DNA單鏈能組成DNA雙鏈，當(dāng)且僅當(dāng)兩個(gè)DNA單鏈的長(zhǎng)度相等，且對(duì)應(yīng)位置上能配對(duì)，A與T配對(duì)，C與G配對(duì)；n<=100, 每個(gè)單鏈長(zhǎng)度不超過(guò)100

8、。,2012-9-20,14,1035 DNA matching,解題思路：枚舉每個(gè)沒(méi)有被匹配的DNA單鏈，再枚舉另外一個(gè)沒(méi)有被匹配的DNA單鏈，如果它們能匹配，則都標(biāo)記為匹配，答案加一。for (i = 0; i < N; i++) if (!vst[i])for (j = i + 1; j < N; j++) if (!vst[j]) {if (match(DNA[i], DNA[j])) {ans

9、++;vst[i] = vst[j] = true;break;}},2012-9-20,15,1046 Plane Spotting,題目大意：給出一個(gè)長(zhǎng)度為N的非負(fù)整數(shù)序列（所有數(shù)不超過(guò)200），還有兩個(gè)整數(shù)M和K，求前M個(gè)最優(yōu)的長(zhǎng)度不小于K的連續(xù)子序列。連續(xù)子序列的優(yōu)先級(jí)如何比較1、平均值大的序列優(yōu)于平均值小的2、條件1相同情況下，長(zhǎng)度大的序列優(yōu)于長(zhǎng)度小的3、條件1和2相同情況下，結(jié)束位置靠前的

10、序列優(yōu)于結(jié)束位置靠后的1≤N≤300，1≤M≤100，1≤K≤300,2012-9-20,16,1046 Plane Spotting,解題思路：使用結(jié)構(gòu)體表示一個(gè)子序列，重寫(xiě)比較操作“1e-6) return a.aver>b.aver;if (a.length!=b.length) return a.length>b.length;return a.ends<b.ends;},2012-9-20,17

11、,1046 Plane Spotting,for (i=0;i=k) {p[cnt].length=j-i+1;p[cnt].ends=j+1;p[cnt].aver=(double)temp/(j-i+1);cnt++;}}}sort(p,p+cnt);,2012-9-20,18,1051 Biker's Trip Odomete,題目大意：給出車(chē)前輪的直徑，轉(zhuǎn)圈數(shù)以及時(shí)間，求出

12、車(chē)行走的路程和平均速度。,2012-9-20,19,1051 Biker's Trip Odomete,解題思路：車(chē)輪周長(zhǎng) = 直徑 × 圓周率路程 = 周長(zhǎng) × 轉(zhuǎn)圈數(shù)平均速度 = 路程 / 時(shí)間,2012-9-20,20,1198 Substring,題目大意：用N個(gè)字符串拼成一個(gè)新的字符串要求新字符串字典序最小如： a ab ac則答案為：aabac1<=N<=8,每個(gè)字符串

13、長(zhǎng)度不超過(guò)100,2012-9-20,21,1198 Substring,解題思路：枚舉n!種情況，最多為8!=40320種情況；每枚舉一種情況，與當(dāng)前字典序最小字符串比較，如果字典序更小，則更新答案；遞歸求解。反例 ba bbab bba,2012-9-20,22,1198 Substring,void dfs(char now[],int lev) {if (lev==n) {update(now);ret

14、urn;}char now2[850];for (int i=0;i<n;i++) if (!used[i]) {strcpy(now2,now);strcat(now2,s[i]);used[i]=true;dfs(now2,lev+1);used[i]=false;}},2012-9-20,23,1176 Two Ends,題目大意：給出n個(gè)正整數(shù)排成一列，A和B輪流取數(shù)，只能

15、取兩端的數(shù)，最后取到的數(shù)的和較大的人勝利，A和B之間的差為分值；A可以自由選擇策略，B的貪心策略取兩端中較大的數(shù)，如果相等則取左邊的數(shù)；問(wèn)A贏(yíng)B的分值最大為多少。n<=1000,且n為偶數(shù)。,2012-9-20,24,1176 Two Ends,解題思路：A嘗試計(jì)算所有情況，并選出自己得分最多的情況；計(jì)算所有情況時(shí)，減少重復(fù)計(jì)算（動(dòng)態(tài)規(guī)劃），每個(gè)狀態(tài)為當(dāng)前數(shù)列的左右端點(diǎn)位置。,2012-9-20,25,1176 Two

16、Ends,int cal(int left,int right) { if (right < left) return 0; if (is_cal[left][right]) return ans[left][right]; int ans_left = arr[left]; if(arr[left+1]<arr[right]) ans_left += cal(left+

17、1,right-1); else ans_left += cal(left+2,right); int ans_right = arr[right]; if (arr[left]<arr[right-1]) ans_right += cal(left,right-2); else ans_right += cal(left

18、+1,right-1); is_cal[left][right] = true; return ans[left][right] = max(ans_left,ans_right);},2012-9-20,26,1433 Optimal Parking,題目大意：n個(gè)商店排在一條街上，每個(gè)商店各有一個(gè)位置。要求在街上找出一個(gè)整數(shù)表示的位置，需要從這個(gè)位置出發(fā)經(jīng)過(guò)所有商店最后回到出發(fā)位置的最短路程。n不超過(guò)20，商店位置用

19、0到99之間的整數(shù)表示。,2012-9-20,27,1433 Optimal Parking,解題思路：把街看作數(shù)軸，各個(gè)位置看作數(shù)軸上的點(diǎn)。首先想到，在選定一個(gè)位置后，必定是從這個(gè)位置開(kāi)始向數(shù)軸負(fù)方向走，到達(dá)最小位置的商店，再向數(shù)軸正方向走，到達(dá)最大位置的商店，再回到出發(fā)點(diǎn)。普通方法：枚舉每個(gè)點(diǎn)作為出發(fā)位置，計(jì)算所有位置的路程，取最小值。,2012-9-20,28,1433 Optimal Parking,更好的方法：其實(shí)只要出

20、發(fā)點(diǎn)在最小值的點(diǎn)與最大值的點(diǎn)之間，則路程是固定的，為(max-min)*2。,2012-9-20,29,1433 Optimal Parking,int cal(int x[],int n){max=-1;min=101;for (i=0;imax)max=x[i];if (x[i]<min)min=x[i];}return (max-min)*2;},2012-9-20,30,132

21、5 Digit Generator,題目大意：對(duì)于一個(gè)整數(shù)N，定義N的digit-sum:digit-sum = N + （N的各位數(shù)字）。如果M是N的digit-sum，則稱(chēng)N為M的generator。例如，245的digit-sum是256 (= 245 + 2 + 4 + 5).因此，245是256的generator。但有些數(shù)有多個(gè)generator，例如216的generator可以是198，也可以是207。問(wèn)：給

22、定一個(gè)N (1 <= N <= 100000), 求N的最小generator，如果N沒(méi)有g(shù)enerator則輸出0。,2012-9-20,31,1325 Digit Generator,解題思路：枚舉。給出一個(gè)N，則按順序枚舉從1到N的所有整數(shù)，直到找到N的一個(gè)generator，或全部數(shù)都不是N的generator。,2012-9-20,32,1325 Digit Generator,更快的方法：注意到1 <

23、= N <= 100000，在這些數(shù)中，各個(gè)數(shù)字之和最大為99999的45，因此N的generator必定在N-45到N-1之間，枚舉范圍大大減少。,2012-9-20,33,1325 Digit Generator,int generator(int n) {int i,j,k;for (k=n-45;k0) {j+=i%10;i/=10;}if (j+k==n)return k;