2013集训队论文答辩(王康宁)演示文稿

题目描述
题目描述
数据范围
对于20%的数据，N≤100，T≤100。 对于50%的数据，N≤3000，T≤1000。 对于70%的数据，N≤50000，T≤20000。 对于100%的数据，N≤200000， T≤50000，1≤Ai, Bi≤106。
保证询问合法，所有的Ai, Bi均为随机生成 的。
一些想法
因此，任意一个转折点所在行（列）的权值， 要比询问区域中左边所有行权值都小，或者 比右边所有行权值都小。 对于随机数据，第i行的权值比之前所有行权 值都小的概率为1/i。 因此期望的转折点个数为： 1/1+1/2+…+1/n=O(log n)
算法二
我们暴力找出所有可能存在转折点的行和列。 然后动态规划求解，此时，只有可能存在转 折点的行和列才为有效状态。 期望行数和列数都是O(logN)，而期望的乘 积等于乘积的期望，所以期望状态数是 O(log2N)。 记录数组A和B的部分和来加速转移。
算法一
对于每一组询问，用动态规划暴力求解。
时间复杂度：O(T*N*N) 空间复杂度：O(N*N)
期望得分：20分
一些想法
将矩形沿中间的竖线分为两半，预处理中间 竖线上的每个点到两边每个点的答案。递归 处理左右两边，交替分割横竖方向。 如果询问分别在左右两边，则枚举经过的中 间竖线上的点。否则递归处理。
时间复杂度：O(N3+T*N) 似乎ቤተ መጻሕፍቲ ባይዱ慢了。
一些想法
将方阵分成S*S块，预处理每个点到块边界 的每个点的答案，以及每个块内每对点的答 案。 询问时两个点若不在同一块，则枚举其中一 个点第一次经过块边界的位置，否则直接回 答。
时间复杂度：O(N3*(S+N/S2)+T*N/S) 同样太慢了。
一些想法
注意到，序列A和B均为随机生成的。
此时，答案的曲线的转折点似乎不会很多。
一些想法
注意一个转折点，和它相邻的两个转折点之 间的部分。 假如这个转折点所在列的权值不小于区域中 其左边的某列权值，也不小于区域中其右边 的某列权值。下面给出一种不更差的方案。
一些想法
根据两行之间的权值关系，下列方案一定有 至少一种不更差。
算法二
时间复杂度（期望）：O(T*(N+log2N)) 即O(T*N) 期望得分：50分
算法三
上个算法的瓶颈是找出可能存在转折点的行 （列），即询问一个序列某区间中比之前 （之后）所有数都小的数，只要求出每个数 之后（之前）第一个比它小的数即可，而这 一工作可以使用单调队列来完成。
方格取数 解题报告
东北师大附中 王康宁
题目描述
有一个N*N的方阵（N≤2*105），第i行第 j列的数为Ai*Bj（1≤Ai,Bj≤106），序列A 和B均为随机生成的。
有T（T≤5*104）次询问，每次询问从给定 的起始位置走到给定的终止位置，每次只能 向下或向右走一步，经过的数的最小总和。
一些想法
设转折点分别在L1,L2,…,Lk行（列），一定 存在一种最优方案，使得： Li行的权值，要么小于Li-1至Li-1所有行的权 值，要么小于Li+1至Li+1所有行的权值。 若前者成立，则Li-1行的权值一定小于Li-2至 Li-1-1所有行的权值，而Li-2行的权值一定小 于Li-3至Li-2-1所有行的权值，…，所以Li行 权值比之前所有行的权值都小。
算法三
比如求每个数之后第一个比它小的数，可以 从后向前扫描这个序列，将单调队列队尾不 小于当前数的部分出队，则这个数之后第一 个比它小的数就是当前队尾的数，然后将当 前数入队。 时间复杂度（期望）：O(N+T*log2N) 期望得分：100分