ACM程序設(shè)計(jì)競(jìng)賽II第一章

1、ACM程序設(shè)計(jì)競(jìng)賽II肖明霞數(shù)據(jù)結(jié)構(gòu) 什么是數(shù)據(jù)結(jié)構(gòu)？ 數(shù)據(jù)結(jié)構(gòu)的作用 計(jì)算機(jī)解決問題步驟： 具體問題抽象出數(shù)學(xué)模型 設(shè)計(jì)解該數(shù)學(xué)模型的算法 編寫程序求解 數(shù)據(jù)結(jié)構(gòu)僅僅是個(gè)工具！問題一：移動(dòng)小球 有一些小球，從左到右依次編號(hào)為1，2，3，.，n，你可以執(zhí)行兩種命令，其中A x y 表示把小球x移動(dòng)到小球y的左邊，B x y 表示把小球x移動(dòng)到y(tǒng)的右邊，指令保證合法，即x不等于y。 例如原始狀態(tài)：1 2 3 4 5 6 執(zhí)行A 1 4 后變?yōu)? 3 1 4 5 6 執(zhí)行B 3 5 后變?yōu)? 1 4 5 3 6 輸入小球個(gè)數(shù)n，指令條數(shù)m和m條指令，從左到右輸出最后的序列。 樣例輸入 6 2 A

2、1 4 B 3 5 樣例輸出 2 1 4 5 3 6 方法一：數(shù)組實(shí)現(xiàn) 問題：數(shù)據(jù)移動(dòng)太多，循環(huán)太長(zhǎng)，超時(shí)。 方法二：鏈表實(shí)現(xiàn) 效率較高 問題:雙向鏈指針不好操作，程序不好寫 方法三：用整數(shù)實(shí)現(xiàn)鏈?zhǔn)讲僮鳎?includeconst int MAXN = 1000;int n, AMAXN;int find(int X) for(int i = 1; i = n; i+) if(Ai = X) return i; return 0;void shift_circular_left(int a, int b) int t = Aa; for(int i = a; i a; i-) Ai = Ai-

3、1; Aa = t;int main() int m, X, Y, p, q; char type9; scanf(%d%d, &n, &m); for(int i = 1; i = n; i+) Ai = i; for(int i = 0; i p) shift_circular_left(p, q-1); else shift_circular_right(q, p); else if(q p) shift_circular_left(p, q); else shift_circular_right(q+1, p); for(int i = 1; i = n; i+) pr

4、intf(%d , Ai); printf(n); return 0;#includeconst int MAXN = 1000;int n, leftMAXN, rightMAXN;void link(int X, int Y) rightX = Y; leftY = X;int main() int m, X, Y; char type9; scanf(%d%d, &n, &m); for(int i = 1; i = n; i+) lefti = i-1; righti = i+1; for(int i = 0; i m; i+) scanf(%s%d%d, &t

5、ype, &X, &Y); link(leftX, rightX); if(type0 = A) link(leftY, X); link(X, Y); else link(X, rightY); link(Y, X); for(int X = right0; X != n+1; X = rightX) printf(%d , X); printf(n); return 0;問題二 最長(zhǎng)回文子串 HDU3068 給出一個(gè)只由小寫英文字符a,b,c.y,z組成的字符串S,求S中最長(zhǎng)回文串的長(zhǎng)度. 輸入：輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c.y,

6、z組成的字符串S。兩組case之間由空行隔開(該空行不用處理)字符串長(zhǎng)度len = 110000 輸出：每一行一個(gè)整數(shù)x,對(duì)應(yīng)一組case,表示該組case的字符串中所包含的最長(zhǎng)回文長(zhǎng)度.aaaa abab4 3#include#include#define N 1000010char sN;int main()int i,j; int max,m; while(scanf(%s,&s)!=EOF) max=0;m=strlen(s);for(i=0;i=0&i+jmax)max=j*2-1;for(j=0;i-j=0&i+j+1max)max=j*2; printf(

7、%dn,max); return 0;問題三 字符串排序 對(duì)很多字符串進(jìn)行排序 輸入：每個(gè)字符串占1行，注意有的字符串非常長(zhǎng)，有的非常短 輸出：將排序結(jié)果輸出 green blue red blackblackblackblackblack aa問題四：又是排序 hdu1425Problem Description給你n個(gè)整數(shù)，請(qǐng)按從大到小的順序輸出其中前m大的數(shù)。Input每組測(cè)試數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n,m (0n,m1000000)，第二行包含n個(gè)各不相同，且都處于區(qū)間-500000,500000的整數(shù)。Output對(duì)每組測(cè)試數(shù)據(jù)按從大到小的順序輸出前m大的數(shù)。問題五問題五 兩倍De

8、scription 給定2到15個(gè)不同的正整數(shù)，你的任務(wù)是計(jì)算這些數(shù)里面有多少個(gè)數(shù)對(duì)滿足：數(shù)對(duì)中一個(gè)數(shù)是另一個(gè)數(shù)的兩倍。 比如給定1 4 3 2 9 7 18 22，得到的答案是3，因?yàn)?是1的兩倍，4是2個(gè)兩倍，18是9的兩倍。 Input 輸入包括多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出2到15個(gè)兩兩不同且小于100的正整數(shù)。每一行最后一個(gè)數(shù)是0，表示這一行的結(jié)束后，這個(gè)數(shù)不屬于那2到15個(gè)給定的正整數(shù)。輸入的最后一行只包括一個(gè)整數(shù)-1,這行表示輸入數(shù)據(jù)的結(jié)束，不用進(jìn)行處理。Output 對(duì)每組輸入數(shù)據(jù)，輸出一行，給出有多少個(gè)數(shù)對(duì)滿足其中一個(gè)數(shù)是另一個(gè)數(shù)的兩倍。Sample Input 1 4

9、 3 2 9 7 18 22 02 4 8 10 07 5 11 13 1 3 0-1 Sample Output 320 #include #include#define N 1000int aN;int main() int i,flag,count,t; while(1) memset(a,0,sizeof(a); flag=0; count=0; while(scanf(%d,&t) if(t=-1) flag=1; if(t=0|t=-1) break; at=1; if(flag=1) break; for(i=1;i=1&ai/2=1) count+; print

10、f(%dn,count); return 0;首先抽象數(shù)學(xué)模型 數(shù)據(jù)如何存儲(chǔ) 問題一：順序表、鏈表？ 問題三：二維數(shù)組？ 對(duì)模型選擇適當(dāng)算法 問題one by one 求解 此處省略1萬字關(guān)于字符串 基本：長(zhǎng)度、拷貝、連接、比較、反串、判斷回文 進(jìn)階：子串（模式匹配）排序 高效排序算法： 快速排序 歸并排序 排序的應(yīng)用 第k小的數(shù)（輸入n個(gè)整數(shù)和一個(gè)正整數(shù)k（1=k=n）,輸出這些數(shù)中從小到大排序后的第k個(gè) 逆序?qū)?shù)（給一列數(shù)a1,a2,.,an）,求它的逆序?qū)?shù)，即有多少個(gè)有序?qū)Γ╥,j），使iaj，n高達(dá)10的6次冪。第K小的數(shù)快排劃分結(jié)束后，數(shù)組Ap.r 被分成了Ap.q 和Aq+1.r

11、兩部分，則可以根據(jù)左邊元素的個(gè)數(shù)和k的關(guān)系來確定在左邊或者右邊遞歸求解。int select(int p,int r,int k)int i,j;if(p=r) return ap;i=partition(p,r);j=i-p+1;if(k 1) int m = x + (y-x)/2; int p = x, q = m, i = x; inverse_pair(A, x, m, cnt, T); inverse_pair(A, m, y, cnt, T); while(p m | q = y | (p m & Ap = Aq)/右邊空，或者兩邊都不空且右邊大 Ti+ = Ap+;/復(fù)

12、制左邊的 else Ti+ = Aq+;/復(fù)制右邊的 *cnt += m-p;/是逆序數(shù)的數(shù)目 for(i = x; i y; i+) Ai = Ti; 哈希表 哈?？紤]問題 哈希函數(shù)設(shè)置 哈希表長(zhǎng)度設(shè)置 沖突解決方案 數(shù)字哈希 字符串哈希數(shù)字哈希l 直接定址l 問題四，問題五l 電話號(hào)碼4873279l 除留余數(shù)H(k ) = k mod p (p一般選取適當(dāng)大的素?cái)?shù))487-3279Description 企業(yè)喜歡用容易被記住的電話號(hào)碼。讓電話號(hào)碼容易被記住的一個(gè)辦法是將它寫成一個(gè)容易記住的單詞或者短語。例如，你需要給滑鐵盧大學(xué)打電話時(shí)，可以撥打TUT-GLOP。有時(shí)，只將電話號(hào)碼中部分?jǐn)?shù)

13、字拼寫成單詞。當(dāng)你晚上回到酒店，可以通過撥打310-GINO來向Ginos訂一份pizza。讓電話號(hào)碼容易被記住的另一個(gè)辦法是以一種好記的方式對(duì)號(hào)碼的數(shù)字進(jìn)行分組。通過撥打必勝客的“三個(gè)十”號(hào)碼3-10-10-10，你可以從他們那里訂pizza。 電話號(hào)碼的標(biāo)準(zhǔn)格式是七位十進(jìn)制數(shù)，并在第三、第四位數(shù)字之間有一個(gè)連接符。電話撥號(hào)盤提供了從字母到數(shù)字的映射，映射關(guān)系如下： A, B, 和C 映射到 2 D, E, 和F 映射到 3 G, H, 和I 映射到 4 J, K, 和L 映射到 5 M, N, 和O 映射到 6 P, R, 和S 映射到 7 T, U, 和V 映射到 8 W, X, 和Y

14、映射到 9 Q和Z沒有映射到任何數(shù)字，連字符不需要撥號(hào)，可以任意添加和刪除。 TUT-GLOP的標(biāo)準(zhǔn)格式是888-4567，310-GINO的標(biāo)準(zhǔn)格式是310-4466，3-10-10-10的標(biāo)準(zhǔn)格式是310-1010。 如果兩個(gè)號(hào)碼有相同的標(biāo)準(zhǔn)格式，那么他們就是等同的（相同的撥號(hào)） 你的公司正在為本地的公司編寫一個(gè)電話號(hào)碼薄。作為質(zhì)量控制的一部分，你想要檢查是否有兩個(gè)和多個(gè)公司擁有相同的電話號(hào)碼。 Input 輸入的格式是，第一行是一個(gè)正整數(shù)，指定電話號(hào)碼薄中號(hào)碼的數(shù)量（最多100000）。余下的每行是一個(gè)電話號(hào)碼。每個(gè)電話號(hào)碼由數(shù)字，大寫字母（除了Q和Z）以及連接符組成。每個(gè)電話號(hào)碼中只會(huì)

15、剛好有7個(gè)數(shù)字或者字母。Output 對(duì)于每個(gè)出現(xiàn)重復(fù)的號(hào)碼產(chǎn)生一行輸出，輸出是號(hào)碼的標(biāo)準(zhǔn)格式緊跟一個(gè)空格然后是它的重復(fù)次數(shù)。如果存在多個(gè)重復(fù)的號(hào)碼，則按照號(hào)碼的字典升序輸出。如果輸入數(shù)據(jù)中沒有重復(fù)的號(hào)碼，輸出一行： No duplicates (注意N大寫) Sample Input 124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279 Sample Output 310-1010 2 487-3279 4 888-4567 3 問題

16、六(HDOJ-1800)Flying to the Mars 字符串哈希 HDOJ-1800題 除去馬甲，本題的本質(zhì)是求相同級(jí)別（level）的人最多是幾個(gè)。 如果level的范圍不大的話（64位整數(shù)可以表示）本題很簡(jiǎn)單，簡(jiǎn)單貪心 本題的難點(diǎn)：level的范圍較大，需用大數(shù)或者字符串比較（去首0） 效率較高、編程簡(jiǎn)單的方法：Hash! 此外，字典樹也是不錯(cuò)的選擇參考源碼(HDOJ-1800)/ by linle#include stdio.h#include memory.h#define MAXN 7003inline int ELFhash(char *key) unsigned long

17、 h = 0; unsigned long g; while( *key ) h =( h 24; h &= g; return h;int hashMAXN,countMAXN;int maxit,n;inline void hashit(char *str) int k,t; while( *str = 0 ) str+; k = ELFhash(str); t = k % MAXN; while( hasht != k & hasht != -1 ) t = ( t + 10 ) % MAXN; if( hasht = -1 ) countt = 1,hasht = k; else if( +countt maxit ) maxit = countt;int main() char str100; while(scanf(%d,&n)!=EOF) memset(hash,-1,sizeof(hash); for(maxit=1,gets(str);n0;n-) gets(str); hashit(str); printf(%dn,maxit); 字符串哈希 很多經(jīng)典方法。 time33 inline UINT CMyMap:HashKey(LPCTSTR key) const UINT nHash =