ACM程序设计竞赛II第一章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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 1 4,B 3 5,样例输出,2 1 4 5 3 6,方法一：数组实现,问题：数据移动太多，循环太长，超时。,方法二：链表实现,效率较高,问题,:,双向链指针不好操作，程序不好写,方法三：用整数实现链式操作？,#include,const 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-1;,Aa=t;,int main(),int m,X,Y,p,q;,char type9;,scanf(%d%d,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+),printf(%d,Ai);,printf(n);,return 0;,#include,const 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,for(int i=1;i=n;i+),lefti=i-1;righti=i+1;,for(int i=0;i m;i+),scanf(%s%d%d,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,z组成的字符串S,。,两组case之间由空行隔开(该空行不用处理)字符串长度len=110000,输出：,每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.,aaaa,abab,4,3,#include,#include,#define N 1000010,char sN;,int main(),int i,j;,int max,m;,while(scanf(%s,&s)!=EOF),max=0;,m=strlen(s);,for(i=0;i=0j+),if(si-j!=si+j),break;,if(j*2-1max),max=j*2-1;,for(j=0;i-j=0j+),if(si-j!=si+j+1),break;,if(j*2max),max=j*2;,printf(%dn,max);,return 0;,问题三 字符串排序,对很多字符串进行排序,输入：每个字符串占1行，注意有的字符串非常长，有的非常短,输出：将排序结果输出,green,blue,red,blackblackblackblackblack,aa,问题四：又是排序,hdu1425,Problem Description,给你,n,个整数，请按从大到小的顺序输出其中前,m,大的数。,Input,每组测试数据有两行，第一行有两个数,n,m(0n,m1000000),，第二行包含,n,个各不相同，且都处于区间,-500000,500000,的整数。,Output,对每组测试数据按从大到小的顺序输出前,m,大的数。,问题五,两倍,Description,给定,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 3 2 9 7 18 22 0,2 4 8 10 0,7 5 11 13 1 3 0,-1,Sample Output,3,2,0,#include,#include,#define N 1000,int 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+;,printf(%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,两部分，则可以根据左边元素的个数和,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+;/,复制左边的,else,Ti+=Aq+;/,复制右边的,*,cnt+=m-p;/,是逆序数的数目,for(i=x;i y;i+)Ai=Ti;,哈希表,哈希考虑问题,哈希函数设置,哈希表长度设置,冲突解决方案,数字哈希,字符串哈希,数字哈希,直接定址,问题四，问题五,电话号码,4873279,除留余数,H(k)=k mod p(p一般选取适当大的,素数,),487-3279,Description,企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打,TUT-GLOP,。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打,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,映射到,9 Q,和,Z,没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。,TUT-GLOP,的标准格式是,888-4567,，,310-GINO,的标准格式是,310-4466,，,3-10-10-10,的标准格式是,310-1010,。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。,Input,输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多,100000,）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了,Q,和,Z,）以及连接符组成。每个电话号码中只会刚好有,7,个数字或者字母。,Output,对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：,No duplicates(,注意,N,大写,),Sample Input,12,4873279,ITS-EASY,888-4567,3-10-10-10,888-GLOP,TUT-GLOP,967-11-11,310-GINO,F101010,888-1200,-4-8-7-3-2-7-9-,487-3279,Sample Output,310-1010 2 487-3279 4 888-4567 3,问题六(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 7003,inline int ELFhash(char*key),unsigned long h=0;,unsigned long g;,while(*key),h=(h 24;,h,return h;,int hashMAXN,countMAXN;,int maxit,n;,inline void hashit(char*str),int k,t;,while(*str=0)str+;,