2015年集训队论文答辩(王康宁)演示文稿【荐】.pptVIP

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