ACM程序设计竞赛II第一章ppt课件

.,1,ACM程序设计竞赛II,肖明霞,.,2,数据结构,什么是数据结构？数据结构的作用计算机解决问题步骤：具体问题抽象出数学模型设计解该数学模型的算法编写程序求解数据结构仅仅是个工具！,.,3,问题一：移动小球,有一些小球，从左到右依次编号为1，2，3，.，n，你可以执行两种命令，其中Axy表示把小球x移动到小球y的左边，Bxy表示把小球x移动到y的右边，指令保证合法，即x不等于y。例如原始状态：123456执行A14后变为231456执行B35后变为214536输入小球个数n，指令条数m和m条指令，从左到右输出最后的序列。样例输入62A14B35,样例输出214536,.,4,方法一：数组实现问题：数据移动太多，循环太长，超时。方法二：链表实现效率较高问题:双向链指针不好操作，程序不好写方法三：用整数实现链式操作？,.,5,#includeconstintMAXN=1000;intn,AMAXN;intfind(intX)for(inti=1;ia;i-)Ai=Ai-1;Aa=t;intmain()intm,X,Y,p,q;chartype9;scanf(%d%d,#includeconstintMAXN=1000;intn,leftMAXN,rightMAXN;voidlink(intX,intY)rightX=Y;leftY=X;intmain()intm,X,Y;chartype9;scanf(%d%d,.,6,问题二最长回文子串HDU3068,给出一个只由小写英文字符a,b,c.y,z组成的字符串S,求S中最长回文串的长度.输入：输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c.y,z组成的字符串S。两组case之间由空行隔开(该空行不用处理)字符串长度len=110000输出：每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.aaaaabab43,.,7,#include#include#defineN1000010charsN;intmain()inti,j;intmax,m;while(scanf(%s,.,8,问题三字符串排序,对很多字符串进行排序输入：每个字符串占1行，注意有的字符串非常长，有的非常短输出：将排序结果输出greenblueredblackblackblackblackblackaa,.,9,问题四：又是排序hdu1425,ProblemDescription给你n个整数，请按从大到小的顺序输出其中前m大的数。Input每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的整数。Output对每组测试数据按从大到小的顺序输出前m大的数。,.,10,问题五两倍,Description给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1432971822，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。Input输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。Output对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。SampleInput14329718220248100751113130-1SampleOutput320,.,11,#include#include#defineN1000intaN;intmain()inti,flag,count,t;while(1)memset(a,0,sizeof(a);flag=0;count=0;while(scanf(%d,.,12,首先抽象数学模型,数据如何存储问题一：顺序表、链表？问题三：二维数组？对模型选择适当算法问题onebyone求解此处省略1万字,.,13,关于字符串,基本：长度、拷贝、连接、比较、反串、判断回文进阶：子串（模式匹配）,.,14,排序,高效排序算法：快速排序归并排序排序的应用第k小的数（输入n个整数和一个正整数k（1aj，n高达10的6次幂。,.,15,第K小的数,快排划分结束后，数组Ap.r被分成了Ap.q和Aq+1.r两部分，则可以根据左边元素的个数和k的关系来确定在左边或者右边递归求解。intselect(intp,intr,intk)inti,j;if(p=r)returnap;i=partition(p,r);j=i-p+1;if(k1)intm=x+(y-x)/2;intp=x,q=m,i=x;inverse_pair(A,x,m,cnt,T);inverse_pair(A,m,y,cnt,T);while(p=y|(p24;h,inlinevoidhashit(char*str)intk,t;while(*str=0)str+;k=ELFhash(str);t=k%MAXN;while(hasht!=k,.,23,字符串哈希,很多经典方法。time33inlin