2020-team12-029

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-huaweiday1standing.png, 1000px)]]



== 问题 ==

我们的问题就是菜。

== 题解 == 

A:全场无人过，听说就是推式子，找结论？待补。

B:在n=2的情况下，对角的两个点的最短路显然严格在其确定的矩形内，可以分治后取中点劈开，O(n)扫一遍计算两边的点到Mid列的点1,2转移。

即取sum(min(dis(mid1,i)+dis(mid1,j),dis(mid2,i)+dis(mid2,j))，这显然可以排序解决。

n=3时，两个点的距离有可能绕路。注意到绕出的那个弯肯定是从第一行绕到第三行（但不意味着第一行的点到第二行的点最短路一定不用绕路）

因此需要预处理每一列向左/右绕一圈从第一行到第三行的路径，以此进行O(n)dp.在此基础上，

求sum(min(dis(mid1,i)+dis(mid1,j),dis(mid2,i)+dis(mid2,j),dis(mid0,i)+dis(mid0,j))（以下简记为dis1(i),dis2(i),dis0(i) ）时，

可以发现dis(0)比dis(1)更优的时候有dis0(j)-dis1(j) < dis1(i)-dis0(i) ，把(dis0(j)-dis1(j),dis0(j)-dis2(j))作为点，(dis1(i)-dis0(i),dis2(i)-dis0(i))作为询问。dis1,dis2同理，因此需要进行三次静态二维数点。

编程时遇到的细节：

①为了在dis0,dis1,dis2相同时顺利去重，可以第一次取两个<=,第二次取一个<=一个<(询问-1），第三次取两个<

②O(n)预处理时，相邻列的1行到3行转移就要考虑绕路（因为上面的注意到，O（n)预处理仍然成立，但是转移这里有细节）**对拍一小时小数据拍不出的细节

③由于路径是点权，两边合并到中间时需要避免中间列算两遍。


C:签到题，观察+思考+识破。

D:ctc暴力剪枝踩标程。

E:szb

F: 不可做

G:不可做

H: 看到数列+处理最大值最小值要想笛卡尔树。这题是有趣的笛卡尔树上dp.

建出小根笛卡尔树，然后就在merge父亲a与左右儿子A,B信息的时候确定了区间最小在父亲，然后考虑转移：

每个节点记录max(区间最大值）、len(区间长度）、ans（区间答案）

假设A.max<B.max, 则如果a+B.max-1>B.len，则结果可以得到一个至少占据B全段和父亲并向A延伸的数列。

ans = max(A.ans, 1+B+len+min(a+B.max-1-(B.len+1),A.len)

否则答案就是左右最大值max(A.ans,B.ans).

I: 不可做

J: 不可做

[/wiki/2020-team12 返回]

问题

我们的问题就是菜。

题解

A:全场无人过，听说就是推式子，找结论？待补。

B:在n=2的情况下，对角的两个点的最短路显然严格在其确定的矩形内，可以分治后取中点劈开，O(n)扫一遍计算两边的点到Mid列的点1,2转移。

即取sum(min(dis(mid1,i)+dis(mid1,j),dis(mid2,i)+dis(mid2,j))，这显然可以排序解决。

n=3时，两个点的距离有可能绕路。注意到绕出的那个弯肯定是从第一行绕到第三行（但不意味着第一行的点到第二行的点最短路一定不用绕路）

因此需要预处理每一列向左/右绕一圈从第一行到第三行的路径，以此进行O(n)dp.在此基础上，

求sum(min(dis(mid1,i)+dis(mid1,j),dis(mid2,i)+dis(mid2,j),dis(mid0,i)+dis(mid0,j))（以下简记为dis1(i),dis2(i),dis0(i) ）时，

可以发现dis(0)比dis(1)更优的时候有dis0(j)-dis1(j) < dis1(i)-dis0(i) ，把(dis0(j)-dis1(j),dis0(j)-dis2(j))作为点，(dis1(i)-dis0(i),dis2(i)-dis0(i))作为询问。dis1,dis2同理，因此需要进行三次静态二维数点。

编程时遇到的细节：

①为了在dis0,dis1,dis2相同时顺利去重，可以第一次取两个<=,第二次取一个<=一个<(询问-1），第三次取两个<

②O(n)预处理时，相邻列的1行到3行转移就要考虑绕路（因为上面的注意到，O（n)预处理仍然成立，但是转移这里有细节）**对拍一小时小数据拍不出的细节

③由于路径是点权，两边合并到中间时需要避免中间列算两遍。

C:签到题，观察+思考+识破。

D:ctc暴力剪枝踩标程。

E:szb

F: 不可做

G:不可做

H: 看到数列+处理最大值最小值要想笛卡尔树。这题是有趣的笛卡尔树上dp.

建出小根笛卡尔树，然后就在merge父亲a与左右儿子A,B信息的时候确定了区间最小在父亲，然后考虑转移：

每个节点记录max(区间最大值）、len(区间长度）、ans（区间答案）

假设A.maxB.len，则结果可以得到一个至少占据B全段和父亲并向A延伸的数列。

ans = max(A.ans, 1+B+len+min(a+B.max-1-(B.len+1),A.len)

否则答案就是左右最大值max(A.ans,B.ans).

I: 不可做

J: 不可做

附加文件