2021-team06-C220426

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==


== submission ==



== 概述 ==

solved: 6/12  dirt: 

rank: 



==  ==

== 总结 ==




== 题解 ==

A: 树剖，节点记录A的和，Dist到左右端点的和，A*Dist到左右端点的和。

B: 按边权从小到大加边，维护前i个点构成的连通块数量，若小于等于K+1则计入答案。

C: 二分答案mid, two pointers把所有x距离≤mid的点纳入考察范围，每插入一个点就寻找它当前在考察同色点集中的前驱和后继，修改线段树上(max(it--w+1, y),min(it2-1, y+w))区间，然后check全局最大值是否为k即可。

D：考虑每个点是上出还是下出，对于每一对点正好有四种可能。枚举i,j判断两者形状：li, ri, lj, rj不处理， li, lj, rj, ri需要lj, rj同上同下, li, lj, ri, rj需要lj, ri异上下。然后跑一遍二分图判断NO，最后同上下和异上下的点参考样例输出。

E: 数学题，归纳法证明对于y>x，点y连到点x的概率均为ax/sx，后面随便写。

F：每对路径转化为dfs树根到两点的距离加上若干个环，于是可以跑一遍tarjan把环&自环放入线性基。
训练时发现性质：设mx(a)为a到一个线性基异或出来的最大值, mx(a)^mx(b)^mx(0) = mx(a^b).

G：区间DP+斜率优化

H：维护每对点的间隔，对每个点求当其取到最大的半径时，向左和向右拓展且半径递减的可行圆序列，则对于每个点得到一系列的半径candidate，最后递推一下即可。

I：log2[转折点]个数，手动模拟找规律

J: 观察发现A3到A7连在一起，考虑枚举A2，单调栈维护右边的(A4+A5+..+A7-A3), 二分左边的A1.

K: 使用两个set，一个装供“反悔”操作的区间2，一个装当前匹配好的区间对。

L：二分答案，爆搜。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 6/12 dirt:

rank:

总结

题解

A: 树剖，节点记录A的和，Dist到左右端点的和，A*Dist到左右端点的和。

B: 按边权从小到大加边，维护前i个点构成的连通块数量，若小于等于K+1则计入答案。

C: 二分答案mid, two pointers把所有x距离≤mid的点纳入考察范围，每插入一个点就寻找它当前在考察同色点集中的前驱和后继，修改线段树上(max(it--w+1, y),min(it2-1, y+w))区间，然后check全局最大值是否为k即可。

D：考虑每个点是上出还是下出，对于每一对点正好有四种可能。枚举i,j判断两者形状：li, ri, lj, rj不处理， li, lj, rj, ri需要lj, rj同上同下, li, lj, ri, rj需要lj, ri异上下。然后跑一遍二分图判断NO，最后同上下和异上下的点参考样例输出。

E: 数学题，归纳法证明对于y>x，点y连到点x的概率均为ax/sx，后面随便写。

F：每对路径转化为dfs树根到两点的距离加上若干个环，于是可以跑一遍tarjan把环&自环放入线性基。

训练时发现性质：设mx(a)为a到一个线性基异或出来的最大值, mx(a)^mx(b)mx(0) = mx(a^b).

G：区间DP+斜率优化

H：维护每对点的间隔，对每个点求当其取到最大的半径时，向左和向右拓展且半径递减的可行圆序列，则对于每个点得到一系列的半径candidate，最后递推一下即可。

I：log2[转折点]个数，手动模拟找规律

J: 观察发现A3到A7连在一起，考虑枚举A2，单调栈维护右边的(A4+A5+..+A7-A3), 二分左边的A1.

K: 使用两个set，一个装供“反悔”操作的区间2，一个装当前匹配好的区间对。

L：二分答案，爆搜。