ACM设计竞赛II第一章说课.ppt

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 方法一：数组实现 问题：数据移动太多，循环太长，超时。 方法二：链表实现 效率较高 问题:双向链指针不好操作，程序不好写 方法三：用整数实现链式操作？ 问题二 最长回文子串 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 问题三 字符串排序 对很多字符串进行排序 输入：每个字符串占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 首先抽象数学模型 数据如何存储 问题一：顺序表、链表？ 问题三：二维数组？ 对模型选择适当算法 问题one by one 求解 此处省略1万字 关于字符串 基本：长度、拷贝、连接、比较、反串、判断回文 进阶：子串（模式匹配） 排序 高效排序算法： 快速排序 归并排序 排序的应用 第k小的数（输入n个整数和一个正整数k（1=k=n）,输出这些数中从小到大排序后的第k个 逆序对数（给一列数a1,a2,...,an）,求它的逆序对数，即有多少个有序对（i,j），使ij，但aiaj，n高达10的6次幂。 第K小的数 快排划分结束后，数组A[p..r] 被分成了A[p..q] 和A[q+1..r]两部分，则可以根据左边元素的个数和k的关系来确定在左边或者右边递归求解。 int select(int p,int r,int k) { int i,j; if(p==r) return a[p]; i=partition(p,r); j=i-p+1; if(k=j) return select(p,i,k); else return select(i+1,r,k-j); } 逆序对数 void inverse_pair( int* A, int x, int y, int* cnt, int* T) { if(y-x 1){ int m = x + (y-x)/2; int p = x, q = m, i = x; inverse_pair(A, x, m, cnt, T); inverse_pair(A