李超2012国家集训队命题答辩

《李超2012国家集训队命题答辩》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、拆弹计划杭州学军中学李超题目大意在平面上给定N个点每个点有一个权值要求找到三个点使这三个点两两之间曼哈顿距离和加上每个点的权值的总和最小最小值为(1+1+2)+(1+2+3)=10数据范围数据编号NX,Y,Z注释1~6N<=3000<=Xi<=10^80<=Yi<=10^80<=Zi<=10^8无7~10N<=100011~14N<=1500015~16N<=100000所有点权值相同17~20无为不失一般性假设所有点的X坐标与Y坐标均互不相同枚举枚举三个点，计算并更新答案时间复杂度为O(N^3)可以通过数据1~6，期望得到3

2、0分对于100%的数据，我们能够找到怎么样的算法呢？复杂简单、特殊简单的情况考虑两个点的情况先不考虑权值计算一个点在另一个点的左下角时的答案X2+Y2-(X1+Y1)只和X+Y最大值有关！按Y坐标从小往大加入点维护前缀最大值X2-X1Y2-Y1(X2,Y2)(X1,Y1)简单的情况可以求每个点在四个方向上的最优值时间复杂度O(NlogN)点带权值的情况令点i的权值为Zi考虑答案的表达式X2-X1+Y2-Y1+Z1+Z2=(X2+Y2+Z2)-(X1+Y1-Z1)维护X+Y-Z的最大值X2-X1Y2-Y1(X2,Y2)(X1,Y

3、1)Z2Z1包含三个点最小矩形的周长！三个点只有两种情况两个点在矩形的对角上一个点在矩形的内部一个点在矩形的角上两个点在矩形的边上三个点的情况第一种情况预处理每个点在四个方向的最优点枚举每个点作为中间点合并左上与右下的最优解合并右上与左下的最优解时间复杂度O(NlogN)空间复杂度O(N)(X2,Y2)(X1,Y1)(X3,Y3)X1

4、节点(X2,Y2)(X1,Y1)(X3,Y3)第二种情况2*(X1+Y1-(X2+Y3))查询节点：查询该点左下所有点的X2+Y3最大值更新节点：用X更新该点右下所有点的X2+Y3插入节点：记录该点的Y坐标算法步骤：1.查询左下X+Y最大值2.更新右下X+Y最大值3.记录Y值Answer=6*2=12YX+Y122335475(3,1)(1,2)(5,3)(2,4)(4,5)第二种情况暴力查询、修改是O(N^2)的区间查询最大值区间更新最大值单点插入线段树！带权值？仍然考虑答案的表达式2*(X1+Y1-X2-Y3)=(2*X1

5、+2*Y1+Z1)-((2*X2-Z2)+(2*Y3-Z3))维护维护方式不变+Z1+Z2+Z3X2+Y3(2*X2-Z2)+(2*Y3-Z3)复杂度分析求区间最大值：O(logN)区间更新：O(logN)插入一个点：O(logN)总时间复杂度为O(NlogN)空间复杂度为O(N)至此，我们已经完美解决了原问题回顾原问题考虑本质情况二线段树区间操作情况一简单情况顺序关系顺序关系难以入手？解决问题要点对题目本质的深刻探讨对顺序关系的巧妙应用对数据结构的恰当选择预计得分情况扩展特殊情况：所有点权值相同时，也可以使用经典的分治算法解

6、决三个点变为多个点二维变为多维曼哈顿距离变为欧几里得距离……欢迎提问