[學習]算法分析與設計課件：習題選講1bywxyz

1、算法分析習題選講,,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個整數(shù)b1,b2,...,bn，和一個大整數(shù)x，求x對每個數(shù)bi取模的結果。n<=100, 1<bi<=1000, x的長度不超過400。,2012-9-20,5,1020 Big Integer,解題思路：對bi逐個計算；高精度，模擬豎式計算。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對夫婦站成一圈如果某對夫婦站在相鄰位置，則從圈中移走重復以上操作問最后會不會沒人如1 3是一對，2 4是一對，則No如1 4是一對，2 3是一對，

4、則Yes1<=N<=100,000,2012-9-20,7,1021 Couple,解題思路：類似于括號匹配，可將n對夫婦看成n種括號用一個棧來模擬，將括號逐個push到棧里當棧頂存在匹配對時進行pop操作看最后棧是否為空,2012-9-20,8,1021 Couple,如1 3是一對，2 4是一對,最后棧不為空，輸出No,2012-9-20,9,1021 Couple,如1 4是一對，2 3是一對,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對BBS_ID I

6、P_Address，求出IP_Address相同的BBS_ID。N<=20,2012-9-20,12,1027 MJ, Nowhere to Hide,解題思路：枚舉每兩個BBS_ID IP_Address對，比較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個DNA單鏈，問可以用這些DNA單鏈組成多少個DNA雙鏈；每個DNA單鏈最多使用一次；兩個DNA單鏈能組成DNA雙鏈，當且僅當兩個DNA單鏈的長度相等，且對應位置上能配對，A與T配對，C與G配對；n<=100, 每個單鏈長度不超過100

8、。,2012-9-20,14,1035 DNA matching,解題思路：枚舉每個沒有被匹配的DNA單鏈，再枚舉另外一個沒有被匹配的DNA單鏈，如果它們能匹配，則都標記為匹配，答案加一。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,題目大意：給出一個長度為N的非負整數(shù)序列（所有數(shù)不超過200），還有兩個整數(shù)M和K，求前M個最優(yōu)的長度不小于K的連續(xù)子序列。連續(xù)子序列的優(yōu)先級如何比較1、平均值大的序列優(yōu)于平均值小的2、條件1相同情況下，長度大的序列優(yōu)于長度小的3、條件1和2相同情況下，結束位置靠前的

10、序列優(yōu)于結束位置靠后的1≤N≤300，1≤M≤100，1≤K≤300,2012-9-20,16,1046 Plane Spotting,解題思路：使用結構體表示一個子序列，重寫比較操作“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,題目大意：給出車前輪的直徑，轉圈數(shù)以及時間，求出

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

13、長度不超過100,2012-9-20,21,1198 Substring,解題思路：枚舉n!種情況，最多為8!=40320種情況；每枚舉一種情況，與當前字典序最小字符串比較，如果字典序更小，則更新答案；遞歸求解。反例 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個正整數(shù)排成一列，A和B輪流取數(shù)，只能

15、取兩端的數(shù)，最后取到的數(shù)的和較大的人勝利，A和B之間的差為分值；A可以自由選擇策略，B的貪心策略取兩端中較大的數(shù)，如果相等則取左邊的數(shù)；問A贏B的分值最大為多少。n<=1000,且n為偶數(shù)。,2012-9-20,24,1176 Two Ends,解題思路：A嘗試計算所有情況，并選出自己得分最多的情況；計算所有情況時，減少重復計算（動態(tài)規(guī)劃），每個狀態(tài)為當前數(shù)列的左右端點位置。,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個商店排在一條街上，每個商店各有一個位置。要求在街上找出一個整數(shù)表示的位置，需要從這個位置出發(fā)經(jīng)過所有商店最后回到出發(fā)位置的最短路程。n不超過20，商店位置用

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

20、發(fā)點在最小值的點與最大值的點之間，則路程是固定的，為(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,題目大意：對于一個整數(shù)N，定義N的digit-sum:digit-sum = N + （N的各位數(shù)字）。如果M是N的digit-sum，則稱N為M的generator。例如，245的digit-sum是256 (= 245 + 2 + 4 + 5).因此，245是256的generator。但有些數(shù)有多個generator，例如216的generator可以是198，也可以是207。問：給

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

23、= N <= 100000，在這些數(shù)中，各個數(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;