ACM程序设计竞赛II第一章 PPT.ppt

ACM程序设计竞赛II肖明霞1数据结构什么是数据结构?数据结构的作用计算机解决问题步骤:具体问题抽象出数学模型设计解该数学模型的算法编写程序求解数据结构仅仅是个工具!2问题一:移动小球有一些小球,从左到右依次编号为1,2,3,...,n,你可以执行两种命令,其中Axy表示把小球x移动到小球y的左边,Bxy表示把小球x移动到y的右边,指令保证合法,即x不等于y。例如原始状态:123456执行A14后变为231456执行B35后变为214536输入小球个数n,指令条数m和m条指令,从左到右输出最后的序列。样例输入62A14B35样例输出2145363方法一:数组实现问题:数据移动太多,循环太长,超时。方法二:链表实现效率较高问题:双向链指针不好操作,程序不好写方法三:用整数实现链式操作?4#include<>constintMAXN=1000;intn,A[MAXN];intfind(intX){for(inti=1;i<=n;i++)if(A[i]==X)returni;return0;}voidshift_circular_left(inta,intb){intt=A[a];for(inti=a;i<b;i++)A[i]=A[i+1];A[b]=t;}voidshift_circular_right(inta,intb){intt=A[b];for(inti=b;i>a;i--)A[i]=A[i-1];A[a]=t;}intmain(){intm,X,Y,p,q;chartype[9];scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)A[i]=i;for(inti=0;i<m;i++){scanf("%s%d%d",&type,&X,&Y);p=find(X);q=find(Y);if(type[0]=='A'){if(q>p)shift_circular_left(p,q-1);elseshift_circular_right(q,p);}else{if(q>p)shift_circular_left(p,q);elseshift_circular_right(q+1,p);}}for(inti=1;i<=n;i++)printf("%d",A[i]);printf("\n");return0;}#include<>constintMAXN=1000;intn,left[MAXN],right[MAXN];voidlink(intX,intY){right[X]=Y;left[Y]=X;}intmain(){intm,X,Y;chartype[9];scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){left[i]=i-1;right[i]=i+1;}for(inti=0;i<m;i++){scanf("%s%d%d",&type,&X,&Y);link(left[X],right[X]);if(type[0]=='A'){link(left[Y],X);link(X,Y);}else{link(X,right[Y]);link(Y,X);}}for(intX=right[0];X!=n+1;X=right[X])printf("%d",X);printf("\n");return0;}5问题二最长回文子串HDU3068给出一个只由小写英文字符a,b,c...y,z组成的字符串S,:输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S。两组case之间由空行隔开(该空行不用处理)字符串长度len<=110000输出:每一行一个整数x,对应一组case,#include<>#include<>#defineN1000010chars[N];intmain(){inti,j; intmax,m;while(scanf("%s",&s)!=EOF){ max=0; m=strlen(s); for(i=0;i<m;i++) { for(j=0;i-j>=0&&i+j<m;j++) if(s[i-j]!=s[i+j]) break; if(j*2-1>max) { max=j*2-1; } for(j=0;i-j>=0&&i+j+1<m;j++) if(s[i-j]!=s[i+j+1]) break; if(j*2>max) { max=j*2; } } printf("%d\n",max);}return0;}7大家应该也有点累了,稍作休息大家有疑问的,可以询问和交流8问