ACM程序设计竞赛II第一章

1、ACM程序设计竞赛II肖明霞数据结构 什么是数据结构？ 数据结构的作用 计算机解决问题步骤： 具体问题抽象出数学模型 设计解该数学模型的算法 编写程序求解 数据结构仅仅是个工具！问题一：移动小球 有一些小球，从左到右依次编号为1，2，3，.，n，你可以执行两种命令，其中A x y 表示把小球x移动到小球y的左边，B x y 表示把小球x移动到y的右边，指令保证合法，即x不等于y。 例如原始状态：1 2 3 4 5 6 执行A 1 4 后变为2 3 1 4 5 6 执行B 3 5 后变为2 1 4 5 3 6 输入小球个数n，指令条数m和m条指令，从左到右输出最后的序列。 样例输入 6 2 A

2、1 4 B 3 5 样例输出 2 1 4 5 3 6 方法一：数组实现 问题：数据移动太多，循环太长，超时。 方法二：链表实现 效率较高 问题:双向链指针不好操作，程序不好写 方法三：用整数实现链式操作？#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个各不相同，且都处于区间-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 企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打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 =