版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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個(gè)整數(shù)b1,b2,...,bn,和一個(gè)大整數(shù)x,求x對(duì)每個(gè)數(shù)bi取模的結(jié)果。n<=100, 1<bi<=1000, x的長(zhǎng)度不超過(guò)400。,2011-10-08,4,1020 Big Integer,解題思路:對(duì)bi逐個(gè)計(jì)算;高精度,模擬豎式計(jì)算。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對(duì)夫婦站成一圈如果某對(duì)夫婦站在相鄰位置,則從圈中移走重復(fù)以上操作問(wèn)最后會(huì)不會(huì)沒(méi)人如1 3是一對(duì),2 4是一對(duì),則No如1 4是一對(duì),2 3是一對(duì),則Yes1<=N<=100,000,2011-10-08,
4、6,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操作看最后棧是否為空,2011-10-08,7,1021 Couple,如1 3是一對(duì),2 4是一對(duì),最后棧不為空,輸出No,2011-10-08,8,1021 Couple,如1 4是一對(duì),2 3是一對(duì),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對(duì)BBS_ID IP_Address,求出IP_Address相同的BBS_ID。
6、N<=20,2011-10-08,11,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])==0)ans[cnt++]=make_pair(id[i],id[
7、j]);},2011-10-08,12,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。,2011-10-08,13,1035 DNA matching,解題思路:枚舉每個(gè)沒(méi)有被匹
8、配的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++;vst[i] = vst[j] = true;break;}}
9、,2011-10-08,14,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é)束位置靠前的序列優(yōu)于結(jié)束位置靠后的1≤N≤300,1≤M≤100,1≤K≤300,2011-10-08
10、,15,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;},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,題目大意:給出車(chē)前輪的直徑,轉(zhuǎn)圈數(shù)以及時(shí)間,求出車(chē)行走的路程和平均速度。,2011-10-08,18,1051 Biker's
12、 Trip Odomete,解題思路:車(chē)輪周長(zhǎng) = 直徑 × 圓周率路程 = 周長(zhǎng) × 轉(zhuǎn)圈數(shù)平均速度 = 路程 / 時(shí)間,2011-10-08,19,1198 Substring,題目大意:用N個(gè)字符串拼成一個(gè)新的字符串要求新字符串字典序最小如: a ab ac則答案為:aabac1<=N<=8,每個(gè)字符串長(zhǎng)度不超過(guò)100,2011-10-08,20,1198 Substring,解題思
13、路:枚舉n!種情況,最多為8!=40320種情況;每枚舉一種情況,與當(dāng)前字典序最小字符串比較,如果字典序更小,則更新答案;遞歸求解。,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個(gè)正整數(shù)排成一列,A和B輪流取數(shù),只能取兩端的數(shù),最后取到的數(shù)的和較大的人勝利,A和B之間的差為分值;A可以自由選擇策略,B的貪心策略取兩端中較
15、大的數(shù),如果相等則取左邊的數(shù);問(wèn)A贏B的分值最大為多少。n<=1000,且n為偶數(shù)。,2011-10-08,23,1176 Two Ends,解題思路:A嘗試計(jì)算所有情況,并選出自己得分最多的情況;計(jì)算所有情況時(shí),減少重復(fù)計(jì)算(動(dòng)態(tài)規(guī)劃),每個(gè)狀態(tài)為當(dāng)前數(shù)列的左右端點(diǎn)位置。,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.中間四塊順時(shí)針轉(zhuǎn)一格,1150 1151 1515 魔板,題目大意:給出魔板的起始狀態(tài),并給定三種基本操作,給出一個(gè)步數(shù)上限和目標(biāo)狀態(tài),求從起始狀態(tài)到目標(biāo)狀態(tài)的操作序列,長(zhǎng)度不得超過(guò)上限。,201
20、1-10-08,27,1150 1151 1515 魔板,解題思路:對(duì)模板進(jìn)行狀態(tài)搜索;由一種狀態(tài)可以轉(zhuǎn)移到另外三種狀態(tài),搜索樹(shù)為一棵三叉樹(shù);在這棵三叉樹(shù)上搜索,目的是求出最優(yōu)解。,2011-10-08,28,1150 1151 1515 魔板,算法一:盲目DFS對(duì)這棵三叉樹(shù)進(jìn)行DFS若想求得最優(yōu)解,需要遍歷整棵樹(shù)需要進(jìn)行重復(fù)擴(kuò)展優(yōu)化:若已找到一個(gè)可行解,可剪去大于等于這個(gè)深度的所有子樹(shù)勉強(qiáng)可過(guò)1150。,2011-
21、10-08,29,1150 1151 1515 魔板,算法二:BFS對(duì)這棵三叉樹(shù)進(jìn)行BFS第一個(gè)可行解即是最優(yōu)解可以過(guò)1150,但過(guò)不了1151。,2011-10-08,30,1150 1151 1515 魔板,算法三:BFS + 判重對(duì)這棵三叉樹(shù)進(jìn)行BFS,相同的節(jié)點(diǎn)不再重復(fù)擴(kuò)展第一個(gè)可行解即是最優(yōu)解判重:BFS每經(jīng)過(guò)一個(gè)節(jié)點(diǎn),把它放進(jìn)已搜索列表中,每遇到一個(gè)節(jié)點(diǎn),如果在已搜索列表存在,則不再擴(kuò)展該節(jié)點(diǎn),共8!=4032
22、0個(gè)節(jié)點(diǎn)。判重編碼:康托展開(kāi)、自定義編碼,如初始狀態(tài)可編碼為整數(shù)12348765。可以輕松通過(guò)三個(gè)題目。,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,題目大意:給出一種加密方式,把一個(gè)字符串按列寫(xiě)成二維形式,再逐行從左到右或從右到左交替輸出。給出加密后的字符串,還原本來(lái)的字符串。,2011-10-08,34,1007 To and Fro,解題思路:按照解密規(guī)則把
26、輸入字符串寫(xiě)在二維數(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、,題目大意:給出一種加密方式,把一個(gè)字符串按行寫(xiě)成二維形式,再按照給定字符串的字符大小順序逐列替輸出。給出加密后的字符串,還原本來(lái)的字符串。,2011-10-08,36,1036 Crypto Columns,解題思路:按照解密規(guī)則把輸入字符串寫(xiě)在二維數(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,題目大意:對(duì)于兩個(gè)排列p, q,定義 distance( p, q )為在p, q中出現(xiàn)的相對(duì)次序不同的元素的對(duì)數(shù)。相當(dāng)于以p為
29、基準(zhǔn),求q的逆序數(shù)。給出n個(gè)5元排列,構(gòu)造一個(gè)排列,使得該排列對(duì)n個(gè)排列的distance之和最小。n<=100,2011-10-08,38,1006 Team Rankings,解題思路:枚舉所有5元排列,與n個(gè)排列一一比較5個(gè)元素之間順序并累加;枚舉方法可用遞歸。,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,題目大意:梅森素?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ù),并且將它們分解。k<=63,2011-10-08,42,1009 Mersenne Composite N,解題思路:方法一:通過(guò)網(wǎng)絡(luò)查找梅森素?cái)?shù)的性質(zhì):對(duì)Mq(q是素?cái)?shù))有:若a是M
34、q的因數(shù),則a有如下性質(zhì):a ≡ 1 mod 2qa ≡ ±1 mod 8對(duì)每個(gè)數(shù),枚舉所有可能的因數(shù),測(cè)試是否能分解。方法二:查找資料可知在n<=63內(nèi)有以下Mn滿足答案11,23,29,37,41,43,47,53,59只對(duì)這些數(shù)進(jìn)行分解。,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個(gè)數(shù)和
36、一個(gè)目標(biāo)數(shù),從5個(gè)數(shù)中選出一部分?jǐn)?shù)通過(guò)加減乘除運(yùn)算得到小于等于目標(biāo)數(shù)的最大數(shù)。,2011-10-08,45,1050 Numbers & Letters,解題思路:DFS求出所有可能的運(yùn)算組合和順序,得到最接近目標(biāo)數(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,題目大意:給出一個(gè)長(zhǎng)度為n的打印任務(wù)隊(duì)列,每個(gè)任務(wù)有優(yōu)先級(jí)。每次從隊(duì)列頭得到一個(gè)任務(wù),如果它是剩余任務(wù)中優(yōu)先級(jí)最高的,則打印它,否則放到隊(duì)列尾。求出其中某個(gè)特定任務(wù)是第幾個(gè)被執(zhí)行的。n<=100,2011-10-08,48,1443 Printer Queue,解題思路:
40、使用隊(duì)列直接模擬。取出隊(duì)列頭判斷是否打印,如果打印則已打印任務(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,題目大意:給出一棵二叉樹(shù)每個(gè)節(jié)點(diǎn)的編號(hào),內(nèi)容以及左右子節(jié)點(diǎn)的編號(hào),以先序遍歷二叉樹(shù)輸出每個(gè)節(jié)
42、點(diǎn)的內(nèi)容。,2011-10-08,51,1156 Binary tree,解題思路:先序遍歷:先輸出當(dāng)前節(jié)點(diǎn)的內(nèi)容,然后遍歷左子樹(shù),最后遍歷右子樹(shù)。先找出沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn),即根。從根開(kāi)始遍歷進(jìn)行先序遍歷。void preorder( node* s ) {visit(s);preorder( s->leftchild )preorder( s->rightchild )},2011-10-08,52,1
43、063 Who's the Boss,題目大意:給出n個(gè)人的編號(hào),身高和工資,一個(gè)人的直接上司是身高不比他小且工資比他高最少的人。一個(gè)人的下屬同時(shí)也是他直接上司的下屬。給出q個(gè)詢(xún)問(wèn),輸出詢(xún)問(wèn)的編號(hào)的直接上司的編號(hào),以及這個(gè)編號(hào)有多少個(gè)下屬。,2011-10-08,53,1063 Who's the Boss,解題思路:對(duì)所有人按身高從大到小排序,相同則按工資從大到小排序。枚舉每個(gè)人,在已檢查的人中找出工資比他高最
44、少的人,這個(gè)人就是他的直接上司。可以使用STL里的set。(upper_bound ())再按身高從小到大枚舉每個(gè)人,把每個(gè)人的下屬個(gè)數(shù)累加進(jìn)他的直接上司的下屬個(gè)數(shù)。對(duì)每個(gè)詢(xún)問(wèn),查找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,題目大意:給出一個(gè)有N個(gè)節(jié)點(diǎn)的樹(shù),從結(jié)點(diǎn)K開(kāi)始出發(fā),不重復(fù)經(jīng)過(guò)任意一條邊,求最遠(yuǎn)可以走的路程。,2011-10-08,57,1024 Magic Island,解題思路:樹(shù)的性質(zhì):兩個(gè)節(jié)點(diǎn)不經(jīng)過(guò)重復(fù)邊的路徑有且只有一條。從起點(diǎn)開(kāi)始BFS或DFS,求出到所有節(jié)點(diǎn)的不經(jīng)過(guò)重復(fù)邊的路徑長(zhǎng)度,取其中的最大值即為答案。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,謝
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- [學(xué)習(xí)]算法分析與設(shè)計(jì)課件:習(xí)題選講1bywxyz
- [學(xué)習(xí)]算法分析與設(shè)計(jì)課件:習(xí)題選講第六章bywxyz
- [學(xué)習(xí)]算法分析與設(shè)計(jì)課件:習(xí)題選講第七章李承乾
- 《幾何證明選講》習(xí)題
- [學(xué)習(xí)]算法設(shè)計(jì)與分析—遞歸算法
- 算法設(shè)計(jì)與分析習(xí)題輔導(dǎo)
- 黨團(tuán)知識(shí)學(xué)習(xí)題選
- 分析選講教學(xué)大綱
- [學(xué)習(xí)]算法分析與設(shè)計(jì)里的概率算法-概率算法
- [學(xué)習(xí)]算法設(shè)計(jì)與分析ch10on-line算法
- [學(xué)習(xí)]算法設(shè)計(jì)與分析ch8隨機(jī)算法
- 算法設(shè)計(jì)與分析基礎(chǔ)習(xí)題解答
- 算法設(shè)計(jì)與分析習(xí)題答案16章
- 算法設(shè)計(jì)與分析課后習(xí)題解答
- 《算法設(shè)計(jì)與分析》期末復(fù)習(xí)題
- 實(shí)用運(yùn)籌學(xué)習(xí)題選詳解
- 算法設(shè)計(jì)與分析第2版王紅梅胡明習(xí)題答案
- 字處理選講
- [學(xué)習(xí)]算法設(shè)計(jì)與分析-作業(yè)-第4章
- [學(xué)習(xí)]算法設(shè)計(jì)與分析王佳01概述
評(píng)論
0/150
提交評(píng)論