2015年集训队论文答辩(张闻涛)演示文稿【荐】.pptVIP

aaa 有了离线的想法，再利用分块的思想，不难想到一种复杂度稍优于暴力法的算法。 通常，分块处理是在一些复杂度更优的算法存在，但思维复杂度比较高时的一个有效处理手段。 Catch The Penguins 杭州学军中学 张闻涛 问题简述 给出四维空间上N个企鹅坐标。 有Q个询问，每次给出一个点，问有多少企鹅每一维坐标都小于等于这个点。 样例输入 １ 0 0 0 0 2 1 1 1 1 1 1 1 -1 样例输出 １ ０ 数据范围 数据编号 N Ｑ 1 ~ 2 N = ５0 0 0 Ｑ＜＝５０００ 3 ~ 6 N = 1０0 0 0 Ｑ＜＝１００００ 7～１４ Ｎ＜＝３００００ Ｑ＜＝１００００ １５～１８ Ｎ＜＝１００００ Ｑ＜＝３００００ １９～２０ Ｎ＜＝３００００ Ｑ＜＝３００００ 算法０ 暴力枚举询问 暴力枚举企鹅 判断 时间复杂度O(n^2) 期望得分10分。 算法０优化 企鹅按四维坐标排序 得到四个排序数组 对于每个询问，每一维在这四个数组里二分 得出这一维小于询问坐标的企鹅的个数 取其中最小的进行枚举（常数优化） 期望得分3０分。 * 继续优化？ 在线算法难以再继续下去 离线处理 分块算法 离散化。 离线。 分别将询问和企鹅按照第一维坐标排序 按第一维坐标从小到大枚举询问。 对于每个询问： 加入所有第一维比它小的企鹅。 按照第二维排序 每加入sqrt(n)个企鹅，就暴力进行一次排序 其余：暴力。 这部分总复杂度Ｏ(nsqrt(n))。 当进行一次暴力排序时： 已经加入排序的企鹅的个数为M 分成大小为sqrt(M)的块 按照第三维坐标排序 按第四维维护前缀的权值线段树 函数式线段树 询问： 整块：二分+查询 非整块：暴力 总复杂度O(nsqrt(n)log(n)) 期望得分80分 更优算法 离散化。 离线 更优算法 将询问和企鹅一起按第一维坐标排序。 分治： 按照第二维坐标进行“归并”。 更优算法 设排好序后的编号序列为id[L]~id[R]，令MID为其中点。 先递归处理L~MID，MID+1~R部分的答案 归并，每次选取左右两部分中的较小值： 左边的企鹅：将其加入一个集合 右边的询问：询问集合中第三、四维坐标比它小的企鹅数 * 2 , 3 3 , 3 2 , 3 3 , 3 3 , 1 4 , 4 3 , 1 4 , 4 3 , 5 2 , 3 4 , 5 4 , 2 2 , 6 5 , 5 3 , 3 1 , 4 3 , 5 2 , 3 4 , 5 4 , 2 2 , 6 5 , 5 3 , 3 1 , 4 经过分治，第二维坐标有序 由于初始按第一维排序，所以左侧第一维坐标=右侧 开始按第二维“归并” 6 , 6 3 , 7 6 , 6 3 , 7 * 2 , 3 3 , 3 2 , 3 3 , 3 3 , 1 4 , 4 3 , 1 4 , 4 3 , 5 2 , 3 2 , 6 5 , 5 3 , 5 2 , 3 4 , 5 4 , 2 2 , 6 5 , 5 3 , 3 1 , 4 开始按第二维“归并” 6 , 6 3 , 7 6 , 6 3 , 7 3,3 5,5 4,4 ans+=1 ans+=3 3 , 1 4 , 4 4 , 5 4 , 2 ans+=1 2 , 3 3 , 3 3 , 3 1 , 4 3 , 5 2 , 3 2 , 6 5 , 5 6 , 6 3 , 7 ans+=3 实现： 树状数组/线段树 套平衡树。 总时间复杂度 O(nlog^3(n)) 期望得分100分。 回顾 原问题 无实质性优化 在线暴力算法 一眼看出 寻求优化 分块算法 尝试离线 寻找更优算法 分治 树套树 解决问题 aaa 有了离线的想法，再利用分块的思想，不难想到一种复杂度稍优于暴力法的算法。 通常，分块处理是在一些复杂度更优的算法存在，但思维复杂度比较高时的一个有效处理手段。 Sheet1 分数 人数 .00 10.00 20.00 30.00 40.00 50.00 60.00 70.00 80.00 90.00 100.00 15.00 30.00 40.00 42.00 10.00 23.00 12.00 15.00 14.00 2.00 9.00 212.00 人数 分数 人数