ACM程序設計競賽II第一章

1、ACM程序設計競賽II肖明霞數據結構 什么是數據結構？ 數據結構的作用 計算機解決問題步驟： 具體問題抽象出數學模型 設計解該數學模型的算法 編寫程序求解 數據結構僅僅是個工具！問題一：移動小球 有一些小球，從左到右依次編號為1，2，3，.，n，你可以執(zhí)行兩種命令，其中A x y 表示把小球x移動到小球y的左邊，B x y 表示把小球x移動到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 輸入小球個數n，指令條數m和m條指令，從左到右輸出最后的序列。 樣例輸入 6 2 A

2、1 4 B 3 5 樣例輸出 2 1 4 5 3 6 方法一：數組實現 問題：數據移動太多，循環(huá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;問題二 最長回文子串 HDU3068 給出一個只由小寫英文字符a,b,c.y,z組成的字符串S,求S中最長回文串的長度. 輸入：輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c.y,

6、z組成的字符串S。兩組case之間由空行隔開(該空行不用處理)字符串長度len = 110000 輸出：每一行一個整數x,對應一組case,表示該組case的字符串中所包含的最長回文長度.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;問題三 字符串排序 對很多字符串進行排序 輸入：每個字符串占1行，注意有的字符串非常長，有的非常短 輸出：將排序結果輸出 green blue red blackblackblackblackblack aa問題四：又是排序 hdu1425Problem Description給你n個整數，請按從大到小的順序輸出其中前m大的數。Input每組測試數據有兩行，第一行有兩個數n,m (0n,m1000000)，第二行包含n個各不相同，且都處于區(qū)間-500000,500000的整數。Output對每組測試數據按從大到小的順序輸出前m大的數。問題五問題五 兩倍De

8、scription 給定2到15個不同的正整數，你的任務是計算這些數里面有多少個數對滿足：數對中一個數是另一個數的兩倍。 比如給定1 4 3 2 9 7 18 22，得到的答案是3，因為2是1的兩倍，4是2個兩倍，18是9的兩倍。 Input 輸入包括多組測試數據。每組數據包括一行，給出2到15個兩兩不同且小于100的正整數。每一行最后一個數是0，表示這一行的結束后，這個數不屬于那2到15個給定的正整數。輸入的最后一行只包括一個整數-1,這行表示輸入數據的結束，不用進行處理。Output 對每組輸入數據，輸出一行，給出有多少個數對滿足其中一個數是另一個數的兩倍。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;首先抽象數學模型 數據如何存儲 問題一：順序表、鏈表？ 問題三：二維數組？ 對模型選擇適當算法 問題one by one 求解 此處省略1萬字關于字符串 基本：長度、拷貝、連接、比較、反串、判斷回文 進階：子串（模式匹配）排序 高效排序算法： 快速排序 歸并排序 排序的應用 第k小的數（輸入n個整數和一個正整數k（1=k=n）,輸出這些數中從小到大排序后的第k個 逆序對數（給一列數a1,a2,.,an）,求它的逆序對數，即有多少個有序對（i,j），使iaj，n高達10的6次冪。第K小的數快排劃分結束后，數組Ap.r 被分成了Ap.q 和Aq+1.r

11、兩部分，則可以根據左邊元素的個數和k的關系來確定在左邊或者右邊遞歸求解。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+;/復

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

13、字拼寫成單詞。當你晚上回到酒店，可以通過撥打310-GINO來向Ginos訂一份pizza。讓電話號碼容易被記住的另一個辦法是以一種好記的方式對號碼的數字進行分組。通過撥打必勝客的“三個十”號碼3-10-10-10，你可以從他們那里訂pizza。 電話號碼的標準格式是七位十進制數，并在第三、第四位數字之間有一個連接符。電話撥號盤提供了從字母到數字的映射，映射關系如下： 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沒有映射到任何數字，連字符不需要撥號，可以任意添加和刪除。 TUT-GLOP的標準格式是888-4567，310-GINO的標準格式是310-4466，3-10-10-10的標準格式是310-1010。 如果兩個號碼有相同的標準格式，那么他們就是等同的（相同的撥號） 你的公司正在為本地的公司編寫一個電話號碼薄。作為質量控制的一部分，你想要檢查是否有兩個和多個公司擁有相同的電話號碼。 Input 輸入的格式是，第一行是一個正整數，指定電話號碼薄中號碼的數量（最多100000）。余下的每行是一個電話號碼。每個電話號碼由數字，大寫字母（除了Q和Z）以及連接符組成。每個電話號碼中只會

15、剛好有7個數字或者字母。Output 對于每個出現重復的號碼產生一行輸出，輸出是號碼的標準格式緊跟一個空格然后是它的重復次數。如果存在多個重復的號碼，則按照號碼的字典升序輸出。如果輸入數據中沒有重復的號碼，輸出一行： 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題 除去馬甲，本題的本質是求相同級別（level）的人最多是幾個。 如果level的范圍不大的話（64位整數可以表示）本題很簡單，簡單貪心 本題的難點：level的范圍較大，需用大數或者字符串比較（去首0） 效率較高、編程簡單的方法：Hash! 此外，字典樹也是不錯的選擇參考源碼(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); 字符串哈希 很多經典方法。 time33 inline UINT CMyMap:HashKey(LPCTSTR key) const UINT nHash =