算法分析習(xí)題課 第一章

1、算法分析習(xí)題選講(第一章)第一章Sicily 地址: http:/soj.me1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Bikers Trip Odomete1198 Substring1176 Two Ends1020 Big Integer題目大意：給出n個(gè)整數(shù)b1,b2,.,bn，和一個(gè)大整數(shù)x，求x對(duì)每個(gè)數(shù)bi取模的結(jié)果。n=100, 1bi=1000, x的長度不超過400解題思路12345678901234567890 % m1 % m =

2、112 % m = (1 * 10 + 2) % m = (1 % m * 10 + 2) % m123 % m = (12 * 10 + 3) % m = (12 % m * 10 + 3) % m12345678901234567890 % m= ( ( 1 % m * 10 + 2 ) % m*10+3 ) % m 解題思路對(duì)bi逐個(gè)計(jì)算；高精度，模擬豎式計(jì)算。int div(char x, int b) int a=0;for (int i=0;xi!=0;i+) a=(a*10+xi-0)%b;return a;1021 Couple題目大意：N對(duì)夫婦站成一圈如果某對(duì)夫婦站在相鄰位置

3、，則從圈中移走重復(fù)以上操作問最后會(huì)不會(huì)沒人如1 3是一對(duì)，2 4是一對(duì)，則No如1 4是一對(duì)，2 3是一對(duì)，則Yes1=N=100,000解題思路類似于括號(hào)匹配，可將n對(duì)夫婦看成n種括號(hào)用一個(gè)棧來模擬，將括號(hào)逐個(gè)push到棧里當(dāng)棧頂存在匹配對(duì)時(shí)進(jìn)行pop操作看最后棧是否為空例子1如1 4是一對(duì)，2 3是一對(duì)最后棧為空，輸出Yes112123114例子2如1 3是一對(duì)，2 4是一對(duì)最后棧不為空，輸出No1121231423代碼stack s;for (int i=1;i=2*n;i+) if (!s.empty()&s.top()=couplei)s.pop();elses.push(i);10

4、27 MJ, Nowhere to Hide題目大意：給出N對(duì)BBS_ID IP_Address，求出IP_Address相同的BBS_ID。N=20解題思路枚舉每兩個(gè)BBS_ID IP_Address對(duì)，比較IP_Address是否相同；字符串比較。for (int i=0;in;i+) for (int j=i;jn;j+) if (strcmp(ipi,ipj)=0) anscnt+=make_pair(idi,idj);1035 DNA matching給出n個(gè)DNA單鏈，問可以用這些DNA單鏈組成多少個(gè)DNA雙鏈；每個(gè)DNA單鏈最多使用一次；兩個(gè)DNA單鏈能組成DNA雙鏈，當(dāng)且僅當(dāng)兩

5、個(gè)DNA單鏈的長度相等，且對(duì)應(yīng)位置上能配對(duì)，A與T配對(duì)，C與G配對(duì)；n=100, 每個(gè)單鏈長度不超過100。解題思路枚舉每個(gè)沒有被匹配的DNA單鏈，再枚舉另外一個(gè)沒有被匹配的DNA單鏈，如果它們能匹配，則都標(biāo)記為匹配，答案加一。for (i = 0; i N; i+) if (!vsti)for (j = i + 1; j N; j+) if (!vstj) if (match(DNAi, DNAj) ans+;vsti = vstj = true;break;1046 Plane Spotting給出一個(gè)長度為N的非負(fù)整數(shù)序列（所有數(shù)不超過200），還有兩個(gè)整數(shù)M和K，求前M個(gè)最優(yōu)的長度不小

6、于K的連續(xù)子序列。連續(xù)子序列的優(yōu)先級(jí)如何比較1、平均值大的序列優(yōu)于平均值小的2、條件1相同情況下，長度大的序列優(yōu)于長度小的3、條件1和2相同情況下，結(jié)束位置靠前的序列優(yōu)于結(jié)束位置靠后的1N300，1M100，1K300解題思路使用結(jié)構(gòu)體表示一個(gè)子序列，重寫比較操作“”。對(duì)所有可能的子序列進(jìn)行排序。struct period double aver;int length,ends;bool operator 1e-6) return a.averb.aver;if (a.length!=b.length) return a.lengthb.length;return a.endsb.ends;f

7、or (i=0;in;i+) temp=0;for (j=i+1;j=k) pcnt.length=j-i+1;pcnt.ends=j+1;pcnt.aver=(double)temp/(j-i+1);cnt+;sort(p,p+cnt);1051 Bikers Trip Odomete給出車前輪的直徑轉(zhuǎn)圈數(shù)以及時(shí)間求出車行走的路程和平均速度解題思路車輪周長 = 直徑 圓周率路程 = 周長 轉(zhuǎn)圈數(shù)平均速度 = 路程 / 時(shí)間1198 Substring用N個(gè)字符串拼成一個(gè)新的字符串要求新字符串字典序最小如： a ab ac則答案為：aabac1=N=8,每個(gè)字符串長度不超過100解題思路枚舉n

8、!種情況，最多為8!=40320種情況從中找最優(yōu)的接用STL中的next_permutation直接排序做法反例 b ba babbbasort ( sub, sub + n ) ;do string total=“”; for (i = 0 ; i n ; + + i ) total + = sub i ; ans = min ( ans , total ) ;while(next _permutation(sub, sub + n ) ) ;1176 Two Ends給出n個(gè)正整數(shù)排成一列，A和B輪流取數(shù)，只能取兩端的數(shù)，最后取到的數(shù)的和較大的人勝利，A和B之間的差為分值；A可以自由選擇策

9、略，B的貪心策略取兩端中較大的數(shù)，如果相等則取左邊的數(shù)；問A贏B的分值最大為多少。n=1000,且n為偶數(shù)。解題思路A嘗試計(jì)算所有情況，并選出自己得分最多的情況；計(jì)算所有情況時(shí)，減少重復(fù)計(jì)算（動(dòng)態(tài)規(guī)劃），每個(gè)狀態(tài)為當(dāng)前數(shù)列的左右端點(diǎn)位置。int cal(int left,int right) if (right left) return 0; if (is_calleftright) return ansleftright; int ans_left = arrleft; if(arrleft+1arrright) ans_left += cal(left+1,right-1); else ans_left += cal(left+2,right); int ans_right = arrright; if (arrleft=dataj) fij=-data