2021-team06-C220430

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==


== submission ==



== 概述 ==

solved: 6/10  dirt: 

rank: 84



==  ==

== 总结 ==




== 题解 ==

A: 双哈希对所有可能出现的串判重即可

B: 考虑不加限制的情况下2一定能放但202不一定能放，二分答案mid，构造出MID个20后所有的2和0都优先构成202和2020。瞎J8贪心居然能贪的比答案大也是醉了。

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

D：向下行进行

E: 看懂之后

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

G：可以直接考虑正方形中是否包含顶点，于是变成一个整体二分+每次都要离散化一遍的二维数点，复杂度O((n+m)log1e8log(n)),也可以使用set和线段树，set维护X坐标，线段树维护Y上面的线段

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

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

J: 

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 6/10 dirt:

rank: 84

总结

题解

A: 双哈希对所有可能出现的串判重即可

B: 考虑不加限制的情况下2一定能放但202不一定能放，二分答案mid，构造出MID个20后所有的2和0都优先构成202和2020。瞎J8贪心居然能贪的比答案大也是醉了。

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

D：向下行进行

E: 看懂之后

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

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

G：可以直接考虑正方形中是否包含顶点，于是变成一个整体二分+每次都要离散化一遍的二维数点，复杂度O((n+m)log1e8log(n)),也可以使用set和线段树，set维护X坐标，线段树维护Y上面的线段

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

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

J: