算法分析習(xí)題選講2

1、習(xí)題選講2011-10-082第一章Sicily 地址: http:/soj.me1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Bikers Trip Odomete1198 Substring1176 Two Ends2011-10-0831020 Big Integer題目大意：給出n個整數(shù)b1,b2,.,bn，和一個大整數(shù)x，求x對每個數(shù)bi取模的結(jié)果。n=100, 1bi=1000, x的長度不超過400。2011-10-0841020 Big In

2、teger 解題思路：對bi逐個計(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;2011-10-0851021 Couple題目大意：N對夫婦站成一圈如果某對夫婦站在相鄰位置，則從圈中移走重復(fù)以上操作問最后會不會沒人如1 3是一對，2 4是一對，則No如1 4是一對，2 3是一對，則Yes1=N=100,0002011-10-0861021 Couple解題思路：類似于括號匹配，可將n對夫婦看成n種括號用一個棧來模擬，將括號逐個push到棧里當(dāng)棧頂存在匹配對

3、時(shí)進(jìn)行pop操作看最后棧是否為空2011-10-0871021 Couple如1 3是一對，2 4是一對112123最后棧不為空，輸出No14232011-10-0881021 Couple如1 4是一對，2 3是一對112123114最后棧為空，輸出Yes2011-10-0891021 Couplestack s;for (int i=1;i=2*n;i+) if (!s.empty()&s.top()=couplei)s.pop();elses.push(i);2011-10-08101027 MJ, Nowhere to Hide題目大意：給出N對BBS_ID IP_Address，求出

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

5、兩個DNA單鏈的長度相等，且對應(yīng)位置上能配對，A與T配對，C與G配對；n=100, 每個單鏈長度不超過100。2011-10-08131035 DNA matching解題思路：枚舉每個沒有被匹配的DNA單鏈，再枚舉另外一個沒有被匹配的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;2011-10-08141046 Plane Spotting題目大意：

6、給出一個長度為N的非負(fù)整數(shù)序列（所有數(shù)不超過200），還有兩個整數(shù)M和K，求前M個最優(yōu)的長度不小于K的連續(xù)子序列。連續(xù)子序列的優(yōu)先級如何比較1、平均值大的序列優(yōu)于平均值小的2、條件1相同情況下，長度大的序列優(yōu)于長度小的3、條件1和2相同情況下，結(jié)束位置靠前的序列優(yōu)于結(jié)束位置靠后的1N300，1M100，1K3002011-10-08151046 Plane Spotting解題思路：使用結(jié)構(gòu)體表示一個子序列，重寫比較操作“”。對所有可能的子序列進(jìn)行排序。struct period double aver;int length,ends;bool operator 1e-6) return a.

7、averb.aver;if (a.length!=b.length) return a.lengthb.length;return a.endsb.ends;2011-10-08161046 Plane Spottingfor (i=0;in;i+) temp=0;for (j=i;j=m) pcnt.length=j-i+1;pcnt.ends=j+1;pcnt.aver=(double)temp/(j-i+1);cnt+;sort(p,p+cnt);2011-10-08171051 Bikers Trip Odomete題目大意：給出車前輪的直徑，轉(zhuǎn)圈數(shù)以及時(shí)間，求出車行走的路程和平均速度

8、。2011-10-08181051 Bikers Trip Odomete解題思路：車輪周長 = 直徑 圓周率路程 = 周長 轉(zhuǎn)圈數(shù)平均速度 = 路程 / 時(shí)間2011-10-08191198 Substring題目大意：用N個字符串拼成一個新的字符串要求新字符串字典序最小如： a ab ac則答案為：aabac1=N=8,每個字符串長度不超過1002011-10-08201198 Substring解題思路：枚舉n!種情況，最多為8!=40320種情況；每枚舉一種情況，與當(dāng)前字典序最小字符串比較，如果字典序更小，則更新答案；遞歸求解。2011-10-08211198 Substringvoi

9、d dfs(char now,int lev) if (lev=n) update(now);return;char now2850;for (int i=0;in;i+) if (!usedi) strcpy(now2,now);strcat(now2,si);usedi=true;dfs(now2,lev+1);usedi=false;2011-10-08221176 Two Ends題目大意：給出n個正整數(shù)排成一列，A和B輪流取數(shù)，只能取兩端的數(shù)，最后取到的數(shù)的和較大的人勝利，A和B之間的差為分值；A可以自由選擇策略，B的貪心策略取兩端中較大的數(shù)，如果相等則取左邊的數(shù)；問A贏B的分值最大

10、為多少。n=1000,且n為偶數(shù)。2011-10-08231176 Two Ends解題思路：A嘗試計(jì)算所有情況，并選出自己得分最多的情況；計(jì)算所有情況時(shí)，減少重復(fù)計(jì)算（動態(tài)規(guī)劃），每個狀態(tài)為當(dāng)前數(shù)列的左右端點(diǎn)位置。2011-10-08241176 Two Endsint cal(int left,int right) if (right left) return 0; if (is_calleftright) return ansleftright; int ans_left = arrleft; if (arrleft+1 arrright) ans_left += cal(left+1,

11、right-1); else ans_left += cal(left+2,right); int ans_right = arrright; if (arrleft arrright-1) ans_right += cal(left,right-2); else ans_right += cal(left+1,right-1); is_calleftright = true; return ansleftright = max(ans_left,ans_right);2011-10-0825第二章1150 1151 1515 魔板1007 To and Fro1036 Crypto Colu

12、mns1006 Team Rankings1009 Mersenne Composite N1050 Numbers & Letters1443 Printer Queue1156 Binary tree1063 Whos the Boss1024 Magic Island2011-10-0826如1150，初始狀態(tài)如右圖，三種基本操作分別是：A.上下兩行互換B.每行循環(huán)右移一格C.中間四塊順時(shí)針轉(zhuǎn)一格1150 1151 1515 魔板題目大意：給出魔板的起始狀態(tài)，并給定三種基本操作，給出一個步數(shù)上限和目標(biāo)狀態(tài)，求從起始狀態(tài)到目標(biāo)狀態(tài)的操作序列，長度不得超過上限。2011-10-0827115

13、0 1151 1515 魔板解題思路：對模板進(jìn)行狀態(tài)搜索；由一種狀態(tài)可以轉(zhuǎn)移到另外三種狀態(tài)，搜索樹為一棵三叉樹；在這棵三叉樹上搜索，目的是求出最優(yōu)解。2011-10-08281150 1151 1515 魔板算法一：盲目DFS對這棵三叉樹進(jìn)行DFS若想求得最優(yōu)解，需要遍歷整棵樹需要進(jìn)行重復(fù)擴(kuò)展優(yōu)化：若已找到一個可行解，可剪去大于等于這個深度的所有子樹勉強(qiáng)可過1150。2011-10-08291150 1151 1515 魔板算法二：BFS對這棵三叉樹進(jìn)行BFS第一個可行解即是最優(yōu)解可以過1150，但過不了1151。2011-10-08301150 1151 1515 魔板算法三：BFS + 判

14、重對這棵三叉樹進(jìn)行BFS，相同的節(jié)點(diǎn)不再重復(fù)擴(kuò)展第一個可行解即是最優(yōu)解判重：BFS每經(jīng)過一個節(jié)點(diǎn)，把它放進(jìn)已搜索列表中，每遇到一個節(jié)點(diǎn)，如果在已搜索列表存在，則不再擴(kuò)展該節(jié)點(diǎn)，共8!=40320個節(jié)點(diǎn)。判重編碼：康托展開、自定義編碼，如初始狀態(tài)可編碼為整數(shù)12348765。可以輕松通過三個題目。2011-10-08311150 1151 1515 魔板state q40320;void update(state new_state,int &head,int &tail, char opt) qhead=new_state;visithash(new_state)=true;parenthea

15、d=tail;ophead+=opt;2011-10-08321150 1151 1515 魔板void bfs(state start) int head=0,tail=0;update(start,head,tail,0);while (tailhead) state new_state=A(qtail);if (visithash(new_state)=false)update(new_state,head,tail,A)new_state=B(qtail);if (visithash(new_state)=false)update(new_state,head,tail,B)state

16、 new_state=C(qtail);if (visithash(new_state)=false)update(new_state,head,tail,C)tail+;2011-10-08331007 To and Fro題目大意：給出一種加密方式，把一個字符串按列寫成二維形式，再逐行從左到右或從右到左交替輸出。給出加密后的字符串，還原本來的字符串。2011-10-08341007 To and Fro解題思路：按照解密規(guī)則把輸入字符串寫在二維數(shù)組上，再輸出。int k = 0;for(int i = 0; i row; i+) for(int j = 0; j column; j+) i

17、f(i %2 != 0) ansij = sk+column-1-2*j; else ansij = sk; k+;2011-10-08351036 Crypto Columns題目大意：給出一種加密方式，把一個字符串按行寫成二維形式，再按照給定字符串的字符大小順序逐列替輸出。給出加密后的字符串，還原本來的字符串。2011-10-08361036 Crypto Columns解題思路：按照解密規(guī)則把輸入字符串寫在二維數(shù)組上，再輸出。for (i=0;icolumn;i+) temp=a;for (j=0;jcolumn;j+) if (keywordjtemp) temp=keywordj;n

18、ow=j;keywordnow=a;for (j=1;j=row;j+)cjnow=sk+;2011-10-08371006 Team Rankings題目大意：對于兩個排列p,q，定義 distance( p, q )為在p,q中出現(xiàn)的相對次序不同的元素的對數(shù)。相當(dāng)于以p為基準(zhǔn)，求q的逆序數(shù)。給出n個5元排列，構(gòu)造一個排列，使得該排列對n個排列的distance之和最小。n=1002011-10-08381006 Team Rankings解題思路：枚舉所有5元排列，與n個排列一一比較5個元素之間順序并累加；枚舉方法可用遞歸。2011-10-08391006 Team Rankingsvoi

19、d dfs(char rank,int lev) if (lev=5) rank5=0;cal(rank);return;for (char c=A;c=E;c+) if (!usedc) ranklev=c;usedc=true;dfs(rank,lev+1);usedc=false;2011-10-08401006 Team Rankingsvoid cal(char rank) int count=0;for (int i=0;in;i+) count+=distance(ranksi,rank);if (countans_count) ans_count=count;strcpy(an

20、s,rank);int distance(char a,char b) int cnt=0;for (int i=0;i5;i+) posaai=i; posbbi=i; for (char c1=A;c1=E;c1+) for (char c2=A;c2=E;c2+)if (posac1-posac2)*(posbc1-posbc2)0) cnt+;return cnt;2011-10-08411009 Mersenne Composite N題目大意：梅森素?cái)?shù)Mn：定義為2n-1其中n為素?cái)?shù)且2n-1也為素?cái)?shù)的數(shù)。給定k，求出所有素?cái)?shù)n=k，且滿足2n-1不是梅森素?cái)?shù)的數(shù)，并且將它們分解。

21、k=632011-10-08421009 Mersenne Composite N解題思路：方法一：通過網(wǎng)絡(luò)查找梅森素?cái)?shù)的性質(zhì)：對Mq（q是素?cái)?shù)）有：若a是Mq的因數(shù)，則a有如下性質(zhì)：a 1 mod 2qa 1 mod 8對每個數(shù)，枚舉所有可能的因數(shù)，測試是否能分解。方法二：查找資料可知在n=63內(nèi)有以下Mn滿足答案11,23,29,37,41,43,47,53,59只對這些數(shù)進(jìn)行分解。2011-10-08431009 Mersenne Composite Nvector cal(long long x) vectorfactor;long long n,i,k;n=(1LLx)-1;for

22、(i=3;i*i=n;i+=2) k=0;while (n%i=0) n/=i;k+;if (k!=0) factor.push_back(i);return factor;2011-10-08441050 Numbers & Letters題目大意：給出5個數(shù)和一個目標(biāo)數(shù)，從5個數(shù)中選出一部分?jǐn)?shù)通過加減乘除運(yùn)算得到小于等于目標(biāo)數(shù)的最大數(shù)。2011-10-08451050 Numbers & Letters解題思路：DFS求出所有可能的運(yùn)算組合和順序，得到最接近目標(biāo)數(shù)的答案。2011-10-08461050 Numbers & Lettersvoid dfs(int a, int n) if

23、(n=1) return;int b5,m=0;for (int i=0;in;i+) for (int j=i+i;jn;j+) for (int k=0;kn;k+) if (k!=i & k!=j) bm+=ak;update_answer(bm=ai+aj); dfs(b,m+1);update_answer(bm=ai-aj); dfs(b,m+1);update_answer(bm=aj-ai); dfs(b,m+1);update_answer(bm=ai*aj); dfs(b,m+1);if (aj!=0 & ai%aj=0) update_answer(bm=ai/aj);

24、dfs(b,m+1);if (ai!=0 & aj%ai=0) update_answer(bm=aj/ai); dfs(b,m+1);2011-10-08471443 Printer Queue題目大意：給出一個長度為n的打印任務(wù)隊(duì)列，每個任務(wù)有優(yōu)先級。每次從隊(duì)列頭得到一個任務(wù)，如果它是剩余任務(wù)中優(yōu)先級最高的，則打印它，否則放到隊(duì)列尾。求出其中某個特定任務(wù)是第幾個被執(zhí)行的。n0&cnthighest_priority=0) highest_priority-; 2011-10-08501156 Binary tree題目大意：給出一棵二叉樹每個節(jié)點(diǎn)的編號，內(nèi)容以及左右子節(jié)點(diǎn)的編號，以先序遍歷二叉樹輸出每個節(jié)點(diǎn)的內(nèi)容。2011-10-08511156 Binary tree解題思路：先序遍歷：先輸出當(dāng)前節(jié)點(diǎn)的內(nèi)容，然后遍歷左子樹，最后遍歷右子樹。先找出沒有父節(jié)點(diǎn)的節(jié)點(diǎn)，即根。從根開始遍歷進(jìn)行先序遍歷。void preorder( node* s ) visit(s);preorder( s-leftchild )preorder( s-rightchild )2011-10-08521063 Whos the Boss題目大意：給出n個人的編號，身高和工資，一個人的直接上司是身高不比他小且工資比他高最少的人。一個人的