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

1、習(xí)題選講,趙浩泉wxyz202@soj.me,2011-10-08,2,第一章,Sicily 地址: http://soj.me1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Biker's Trip Odomete1198 Substring1176 Two Ends,201

2、1-10-08,3,1020 Big Integer,題目大意：給出n個整數(shù)b1,b2,...,bn，和一個大整數(shù)x，求x對每個數(shù)bi取模的結(jié)果。n<=100, 1<bi<=1000, x的長度不超過400。,2011-10-08,4,1020 Big Integer,解題思路：對bi逐個計算；高精度，模擬豎式計算。int div(char x[], int b) {int a=0;for (int

3、i=0;x[i]!='\0';i++) {a=(a*10+x[i]-'0')%b;return a;},2011-10-08,5,1021 Couple,題目大意：N對夫婦站成一圈如果某對夫婦站在相鄰位置，則從圈中移走重復(fù)以上操作問最后會不會沒人如1 3是一對，2 4是一對，則No如1 4是一對，2 3是一對，則Yes1<=N<=100,000,2011-10-08,

4、6,1021 Couple,解題思路：類似于括號匹配，可將n對夫婦看成n種括號用一個棧來模擬，將括號逐個push到棧里當棧頂存在匹配對時進行pop操作看最后棧是否為空,2011-10-08,7,1021 Couple,如1 3是一對，2 4是一對,最后棧不為空，輸出No,2011-10-08,8,1021 Couple,如1 4是一對，2 3是一對,1,1,2,1,2,3,1,1,4,最后棧為空，輸出Yes,2011-10-08

5、,9,1021 Couple,stack s;for (int i=1;i<=2*n;i++) {if (!s.empty()&&s.top()==couple[i])s.pop();elses.push(i);},2011-10-08,10,1027 MJ, Nowhere to Hide,題目大意：給出N對BBS_ID IP_Address，求出IP_Address相同的BBS_ID。

6、N<=20,2011-10-08,11,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])==0)ans[cnt++]=make_pair(id[i],id[

7、j]);},2011-10-08,12,1035 DNA matching,題目大意：給出n個DNA單鏈，問可以用這些DNA單鏈組成多少個DNA雙鏈；每個DNA單鏈最多使用一次；兩個DNA單鏈能組成DNA雙鏈，當且僅當兩個DNA單鏈的長度相等，且對應(yīng)位置上能配對，A與T配對，C與G配對；n<=100, 每個單鏈長度不超過100。,2011-10-08,13,1035 DNA matching,解題思路：枚舉每個沒有被匹

8、配的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++;vst[i] = vst[j] = true;break;}}

9、,2011-10-08,14,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相同情況下，結(jié)束位置靠前的序列優(yōu)于結(jié)束位置靠后的1≤N≤300，1≤M≤100，1≤K≤300,2011-10-08

10、,15,1046 Plane Spotting,解題思路：使用結(jié)構(gòu)體表示一個子序列，重寫比較操作“1e-6) return a.aver>b.aver;if (a.length!=b.length) return a.length>b.length;return a.ends<b.ends;},2011-10-08,16,1046 Plane Spotting,for (i=0;i=m) {p[cn

11、t].length=j-i+1;p[cnt].ends=j+1;p[cnt].aver=(double)temp/(j-i+1);cnt++;}}}sort(p,p+cnt);,2011-10-08,17,1051 Biker's Trip Odomete,題目大意：給出車前輪的直徑，轉(zhuǎn)圈數(shù)以及時間，求出車行走的路程和平均速度。,2011-10-08,18,1051 Biker's

12、 Trip Odomete,解題思路：車輪周長 = 直徑 × 圓周率路程 = 周長 × 轉(zhuǎn)圈數(shù)平均速度 = 路程 / 時間,2011-10-08,19,1198 Substring,題目大意：用N個字符串拼成一個新的字符串要求新字符串字典序最小如： a ab ac則答案為：aabac1<=N<=8,每個字符串長度不超過100,2011-10-08,20,1198 Substring,解題思

13、路：枚舉n!種情況，最多為8!=40320種情況；每枚舉一種情況，與當前字典序最小字符串比較，如果字典序更小，則更新答案；遞歸求解。,2011-10-08,21,1198 Substring,void dfs(char now[],int lev) {if (lev==n) {update(now);return;}char now2[850];for (int i=0;i<n;i++) if (

14、!used[i]) {strcpy(now2,now);strcat(now2,s[i]);used[i]=true;dfs(now2,lev+1);used[i]=false;}},2011-10-08,22,1176 Two Ends,題目大意：給出n個正整數(shù)排成一列，A和B輪流取數(shù)，只能取兩端的數(shù)，最后取到的數(shù)的和較大的人勝利，A和B之間的差為分值；A可以自由選擇策略，B的貪心策略取兩端中較

15、大的數(shù)，如果相等則取左邊的數(shù)；問A贏B的分值最大為多少。n<=1000,且n為偶數(shù)。,2011-10-08,23,1176 Two Ends,解題思路：A嘗試計算所有情況，并選出自己得分最多的情況；計算所有情況時，減少重復(fù)計算（動態(tài)規(guī)劃），每個狀態(tài)為當前數(shù)列的左右端點位置。,2011-10-08,24,1176 Two Ends,int cal(int left,int right) { if (right <

16、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+1,right-1); else ans

17、_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+1,right-1); is_cal[left][right] = tru

18、e; return ans[left][right] = max(ans_left,ans_right);},2011-10-08,25,第二章,1150 1151 1515 魔板1007 To and Fro1036 Crypto Columns1006 Team Rankings1009 Mersenne Composite N1050 Numbers & Letters1443 Printer Queue

19、1156 Binary tree1063 Who's the Boss1024 Magic Island,2011-10-08,26,如1150，初始狀態(tài)如右圖，三種基本操作分別是：A.上下兩行互換B.每行循環(huán)右移一格C.中間四塊順時針轉(zhuǎn)一格,1150 1151 1515 魔板,題目大意：給出魔板的起始狀態(tài)，并給定三種基本操作，給出一個步數(shù)上限和目標狀態(tài)，求從起始狀態(tài)到目標狀態(tài)的操作序列，長度不得超過上限。,201

20、1-10-08,27,1150 1151 1515 魔板,解題思路：對模板進行狀態(tài)搜索；由一種狀態(tài)可以轉(zhuǎn)移到另外三種狀態(tài)，搜索樹為一棵三叉樹；在這棵三叉樹上搜索，目的是求出最優(yōu)解。,2011-10-08,28,1150 1151 1515 魔板,算法一：盲目DFS對這棵三叉樹進行DFS若想求得最優(yōu)解，需要遍歷整棵樹需要進行重復(fù)擴展優(yōu)化：若已找到一個可行解，可剪去大于等于這個深度的所有子樹勉強可過1150。,2011-

21、10-08,29,1150 1151 1515 魔板,算法二：BFS對這棵三叉樹進行BFS第一個可行解即是最優(yōu)解可以過1150，但過不了1151。,2011-10-08,30,1150 1151 1515 魔板,算法三：BFS + 判重對這棵三叉樹進行BFS，相同的節(jié)點不再重復(fù)擴展第一個可行解即是最優(yōu)解判重：BFS每經(jīng)過一個節(jié)點，把它放進已搜索列表中，每遇到一個節(jié)點，如果在已搜索列表存在，則不再擴展該節(jié)點，共8!=4032

22、0個節(jié)點。判重編碼：康托展開、自定義編碼，如初始狀態(tài)可編碼為整數(shù)12348765?？梢暂p松通過三個題目。,2011-10-08,31,1150 1151 1515 魔板,state q[40320];void update(state new_state,int &head,int &tail, char opt) {q[head]=new_state;visit[hash(new_state)]=tru

23、e;parent[head]=tail;op[head++]=opt;},2011-10-08,32,1150 1151 1515 魔板,void bfs(state start) {int head=0,tail=0;update(start,head,tail,'\0');while (tail<head) {state new_state=A(q[tail]);if (vis

24、it[hash(new_state)]==false)update(new_state,head,tail,'A')new_state=B(q[tail]);if (visit[hash(new_state)]==false)update(new_state,head,tail,'B')state new_state=C(q[tail]);if (visit[has

25、h(new_state)]==false)update(new_state,head,tail,'C')tail++;}},2011-10-08,33,1007 To and Fro,題目大意：給出一種加密方式，把一個字符串按列寫成二維形式，再逐行從左到右或從右到左交替輸出。給出加密后的字符串，還原本來的字符串。,2011-10-08,34,1007 To and Fro,解題思路：按照解密規(guī)則把

26、輸入字符串寫在二維數(shù)組上，再輸出。int k = 0;for(int i = 0; i < row; i++) for(int j = 0; j < column; j++) { if(i %2 != 0) ans[i][j] = s[k+column-1-2*j]; else ans[i][j] = s[k]; k++;},2011-10-08,35,1036 Crypto Columns

27、,題目大意：給出一種加密方式，把一個字符串按行寫成二維形式，再按照給定字符串的字符大小順序逐列替輸出。給出加密后的字符串，還原本來的字符串。,2011-10-08,36,1036 Crypto Columns,解題思路：按照解密規(guī)則把輸入字符串寫在二維數(shù)組上，再輸出。for (i=0;i<column;i++) {temp='a';for (j=0;j<column;j++) if (keywo

28、rd[j]<temp) {temp=keyword[j];now=j;}keyword[now]='a';for (j=1;j<=row;j++)c[j][now]=s[k++];},2011-10-08,37,1006 Team Rankings,題目大意：對于兩個排列p,　q，定義 distance( p, q )為在p,　q中出現(xiàn)的相對次序不同的元素的對數(shù)。相當于以p為

29、基準，求q的逆序數(shù)。給出n個5元排列，構(gòu)造一個排列，使得該排列對n個排列的distance之和最小。n<=100,2011-10-08,38,1006 Team Rankings,解題思路：枚舉所有5元排列，與n個排列一一比較5個元素之間順序并累加；枚舉方法可用遞歸。,2011-10-08,39,1006 Team Rankings,void dfs(char rank[],int lev) {if (lev==5)

30、{rank[5]='\0';cal(rank);return;}for (char c='A';c<='E';c++) if (!used[c]) {rank[lev]=c;used[c]=true;dfs(rank,lev+1);used[c]=false;}},2011-10-08,40,1006 Team Rankings

31、,void cal(char rank[]) {int count=0;for (int i=0;i<n;i++) count+=distance(ranks[i],rank);if (count<ans_count) {ans_count=count;strcpy(ans,rank);}}int distance(char a[],char b[]) {int cnt=0;for (

32、int i=0;i<5;i++) { posa[a[i]]=i; posb[b[i]]=i; }for (char c1='A';c1<='E';c1++) for (char c2='A';c2<='E';c2++)if ((posa[c1]-posa[c2])*(posb[c1]-posb[c2])<0) cnt++;return

33、 cnt;},2011-10-08,41,1009 Mersenne Composite N,題目大意：梅森素數(shù)Mn：定義為2n-1其中n為素數(shù)且2n-1也為素數(shù)的數(shù)。給定k，求出所有素數(shù)n<=k，且滿足2n-1不是梅森素數(shù)的數(shù)，并且將它們分解。k<=63,2011-10-08,42,1009 Mersenne Composite N,解題思路：方法一：通過網(wǎng)絡(luò)查找梅森素數(shù)的性質(zhì)：對Mq（q是素數(shù)）有：若a是M

34、q的因數(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ù)進行分解。,2011-10-08,43,1009 Mersenne Composite N,vector cal(long long x) {vectorfactor;

35、long long n,i,k;n=(1LL<<x)-1;for (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-08,44,1050 Numbers & Letters,題目大意：給出5個數(shù)和

36、一個目標數(shù)，從5個數(shù)中選出一部分數(shù)通過加減乘除運算得到小于等于目標數(shù)的最大數(shù)。,2011-10-08,45,1050 Numbers & Letters,解題思路：DFS求出所有可能的運算組合和順序，得到最接近目標數(shù)的答案。,2011-10-08,46,1050 Numbers & Letters,void dfs(int a[], int n) {if (n==1) return;int b[5],m=0;

37、for (int i=0;i<n;i++) for (int j=i+i;j<n;j++) {for (int k=0;k<n;k++) if (k!=i && k!=j) b[m++]=a[k];update_answer(b[m]=a[i]+a[j]); dfs(b,m+1);update_answer(b[m]=a[i]-a[j]); dfs(b,m+1);update_

38、answer(b[m]=a[j]-a[i]); dfs(b,m+1);update_answer(b[m]=a[i]*a[j]); dfs(b,m+1);if (a[j]!=0 && a[i]%a[j]==0) {update_answer(b[m]=a[i]/a[j]); dfs(b,m+1);}if (a[i]!=0 && a[j]%a[i]==0) {upda

39、te_answer(b[m]=a[j]/a[i]); dfs(b,m+1);}}},2011-10-08,47,1443 Printer Queue,題目大意：給出一個長度為n的打印任務(wù)隊列，每個任務(wù)有優(yōu)先級。每次從隊列頭得到一個任務(wù)，如果它是剩余任務(wù)中優(yōu)先級最高的，則打印它，否則放到隊列尾。求出其中某個特定任務(wù)是第幾個被執(zhí)行的。n<=100,2011-10-08,48,1443 Printer Queue,解題思路：

40、使用隊列直接模擬。取出隊列頭判斷是否打印，如果打印則已打印任務(wù)數(shù)加一。直到特定的任務(wù)完成，輸出答案。,2011-10-08,49,1443 Printer Queue,while(true) { cur = q.front(); if(cur.priority != highest_priority) { q.push(cur); } else { minute++;

41、 if (cur.number==m) break; while (highest_priority>0&&cnt[highest_priority]==0) highest_priority--; }},2011-10-08,50,1156 Binary tree,題目大意：給出一棵二叉樹每個節(jié)點的編號，內(nèi)容以及左右子節(jié)點的編號，以先序遍歷二叉樹輸出每個節(jié)

42、點的內(nèi)容。,2011-10-08,51,1156 Binary tree,解題思路：先序遍歷：先輸出當前節(jié)點的內(nèi)容，然后遍歷左子樹，最后遍歷右子樹。先找出沒有父節(jié)點的節(jié)點，即根。從根開始遍歷進行先序遍歷。void preorder( node* s ) {visit(s);preorder( s->leftchild )preorder( s->rightchild )},2011-10-08,52,1

43、063 Who's the Boss,題目大意：給出n個人的編號，身高和工資，一個人的直接上司是身高不比他小且工資比他高最少的人。一個人的下屬同時也是他直接上司的下屬。給出q個詢問，輸出詢問的編號的直接上司的編號，以及這個編號有多少個下屬。,2011-10-08,53,1063 Who's the Boss,解題思路：對所有人按身高從大到小排序，相同則按工資從大到小排序。枚舉每個人，在已檢查的人中找出工資比他高最

44、少的人，這個人就是他的直接上司?？梢允褂肧TL里的set。(upper_bound ())再按身高從小到大枚舉每個人，把每個人的下屬個數(shù)累加進他的直接上司的下屬個數(shù)。對每個詢問，查找ID給出答案。,2011-10-08,54,1063 Who's the Boss,struct employee{int height,id,earn,number,farther,sub;};bool cmp(const emplo

45、yee &a,const employee &b){if (a.height!=b.height)return a.height h;set::iterator it;,2011-10-08,55,1063 Who's the Boss,sort(a,a+n,cmp);for (i=0;i=0;i--) {it=h.upper_bound(a[i]);if (it==h.end()) a[

46、i].farther=-1;else a[i].farther=(*it).number;h.insert(a[i]);}for (i=0;i<n;i++) {if (a[i].farther!=-1) {a[a[i].farther].sub+=a[i].sub+1;a[i].farther=a[a[i].farther].id;}else a[i].farther=0;}sort(a,a

47、+n,cmp2);,2011-10-08,56,1024 Magic Island,題目大意：給出一個有N個節(jié)點的樹，從結(jié)點K開始出發(fā)，不重復(fù)經(jīng)過任意一條邊，求最遠可以走的路程。,2011-10-08,57,1024 Magic Island,解題思路：樹的性質(zhì)：兩個節(jié)點不經(jīng)過重復(fù)邊的路徑有且只有一條。從起點開始BFS或DFS，求出到所有節(jié)點的不經(jīng)過重復(fù)邊的路徑長度，取其中的最大值即為答案。void dfs(int curren

48、t,int parent,int l) { if (l>ans) ans=l; for (int i=0;i<edge[current].length();i++) if (edge[current][i].number!=parent) dfs(edge[current][i].number,current,l+edge[current][i].l);},2011-10-08,58,謝