《CY分治解题报告》PPT课件.ppt

1、ACM竞赛宣讲会,陈研 数计学院团委学生会主办,内容概要,介绍ACM/ICPC及其赛制 如何加入ACM队 ACM竞赛涉及的知识 如何准备 首届福州大学程序设计竞赛试题讲解 Question int main() int a,b; ifstream fin(“sum.in”); while (finab) couta+bendl; return 0; ,评测方法,Time Limit,对程序的要求,程序执行所需要的时间要短 (Time Complexity) 程序执行所使用的内存要少 (Space Complexity) 结果(Output)要完全正确,ACM .vs. 校程序设计竞赛,ACM竞

2、赛 团队合作精神 即时提交，通过所有数据才能得分 全英文题目，题目考察范围广 校程序设计竞赛 个人编程能力的比拼 赛后提交，可得部分分数 中文题目，考察编程基本功,福州大学ACM队选拔过程,校程序设计竞赛,数学基础笔试,日常训练,暑期集训,福州大学ACM/ICPC队选拔赛 (每年8月),ACM队队员的基本原则,基本要求 人品好 愿意花时间在这项赛事上 有团队合作精神 能力要求 程序设计 英语科技文献阅读 数学,相关的知识,数学知识 离散、组合 数论、图论 计算几何 算法,算法,int vn; int count=0; for (i = 0; i vj) count+; 运算量(n-1)+(n-

3、2)+2+1=n(n-1)/2,算法效率分析,1=N=2.5*105 运算量 = n(n-1)/2=3.1*1010 次 1GHz = 109 次/秒 解决该问题，本算法约需要半分钟。 本题时限1秒！ 算法低效的原因：每次只能计算1个逆序对。,算法优化分治策略,思想：将规模为n的问题分解为k个规模较小的子问题，这些子问题与原问题相互独立且与原问题相同，递归的解这些子问题，然后将子问题的解合并，得到原问题的解。 典型例子：二分法 难点：合并,算法优化分治策略,思想：将n个元素分成大小大致相同的两个子序列，分别对2个子序列求逆序对数，再将2个子序列合并得到原序列的逆序对数。 难点：如何合并？ 原序

4、列逆序对数=2个子序列逆序对之和+满足ViVj(0in/2+1,n/2jn+1)的数对数,算法优化分治策略,满足ViVj(0vj+) 还是O(n2)的复杂度 方法2：如果两个子序列是有序的 6 4 2 5 3 1 如何保证有序？边合并边排序即可,例子,6 4 2,5 3 1,6 4 2,5 3 1,6 4 2,5 3 1,6 4 2,5 3 1,逆序对=3,逆序对=3 排序：6,逆序对=3+2 排序：6,5,逆序对=5+1 排序：6,5,4,3,2,1,6 5 4 3 2 1,更新原序列,算法效率分析,T(n)=2T(n/2)+O(n) 用迭代法解该递推方程得T(n)=O(nlogn) 计算量

5、=nlogn=2.5*106log(2.5*106) = 4.5*106 效率提高的原因：充分利用有序性，每次可计算多个逆序对。 如果想不到这种方法怎么办？,另一种解法,在一个问题无法得到解决时，就需要换一个角度看问题。 切入点： 1、尝试将逆序对问题转化为已有现成的算法的经典模型，即排序模型。 2、尝试换一种数据结构，改变问题的表示方法往往能收到意想不到的效果。,充分注意数据范围,它能在零时间内加速到最大速度Vi (Vi100) 其他的数据范围都很大，唯独这个数据范围很小，这个矛盾往往是解题的突破口。 在现实问题，也往往存在这样现象，大家应该对此充分重视。 Trade-off,新的数据结构,

6、原来是用车的编号来表达问题。e.g. ViVj, XiXj, 能否考虑用速度的值来表示问题？ numv：表示当前车之前速度为v的车有多少辆 如何定义超车： 车辆i能被超过的次数为,算法,int num100; int count=0; memset(num,0,sizeof(num); for (i=0;ixv; numv+; for (k=v+1;k100;k+) count+=numk; ,运算量=O(nk) 2.5*107,编制测试数据,用手工可以检验的小数据，验证程序的正确性 编写程序随机生成大数据，检验程序的执行效率（使用随机函数） 注意检验边界条件。例如，本题中只有1辆车时算法能否

7、得到正确结果。,小结,整个超车的过程实际上就是一个不断交换相邻元素的排序过程。这个排序方法就是冒泡法。因此超车次数就是冒泡法中元素一共要被交换的次数。 通过两种算法的比较，我们可以看出归并排序比冒泡法效率高就是因为归并排序排一次操作可以减少多个逆序对。 如果本题中Vi的规模进一步扩大，你能想出解决的办法吗？,三色二叉树,一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”： 对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉

8、树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。,S=21200110,数据结构,二叉树的表示 给二叉树上所有节点标号，从1N; 用Soni0和Soni1分别表示编号是i的节点，其左右两个子节点的编号（如果不存在，则用-1表示）。 如何将输入串转化为我们定义的数据结构？ 能否记录每个节点的父亲？,建立数据结构,int pl=0; void build() int i; if (pln) if (strpl=0) sonpl0=-1; sonpl1=-1; pl+;return; if (strpl=1) sonpl0=pl+1; sonpl+1=-1; build();return;

9、 ,/*strpl=2*/ sonpl0=pl+1; i=pl+; build(); soni1=pl; build(); ,S=21200110,搜索算法,思想：穷举所有的合法着色方案，并计算每种方案的绿色节点数，从而求出最值。 如何系统的、不遗漏的穷举所有方案？ 尝试找出问题的递归结构： 设f(i,j)表示以编号是i、颜色是j的节点为根节点的子树，在满足约束条件的情况下染色，绿色节点最多（最少）有多少个。,搜索算法,F(i,j)表示以编号是i、颜色是j的节点为根节点的子树，在满足约束条件的情况下染色，绿色节点最多有多少个，则有：,源程序,int maximal(int i,int j) i

10、nt k1,k2,t,m; if (i=-1) return 0; m=-1; for (k1=0;k1m) m=t; if (j=0) m+; return m;,算法效率分析,每个节点可以染3种颜色，最坏情况的计算量为O(3n)。 n10000 本算法在几年之内无法得出结果！,算法改进,(1,red),(1,green),(0,blue),(2,blue),(2,green),(2,red),(2,blue),可以用一个数组记录下已经搜索过的子问题的答案，避免重复搜索,记忆化搜索,int maximal(int i,int j) int k1,k2,t,m; if (i=-1) return 0; if (maxij!=-1) return maxij; m=-1; for (k1=0;k1m) m=t; if (j=0) m+; maxij=m; return m; ,复杂度分析： 最坏情况是max数组的所有 值均被计算过，即至多计算 10000*3次。,编制测试数据,用手工可以检验的小数据，验证程序的正确性 编写程序随机生成大数据，检验程序的执行效率（使用随机函数） 注意检验边界条件。例如，本题中0或200，判断程序是否正确。,小结,本题