比赛链接

AC 9题，Rank 21th

这次还是犯了太急躁的毛病，没有想完全就直接上手了，结果发现问题重重。以后切记耐心。

也是不算很难的一道题，需要一些几何想象，但是一开始想法不完全就开打了。绕了很大弯路TAT。另外审题要仔细！没有注意到题面对于圆形的边界的描述。

其实考虑套住的圆形一个逐步放大和调整的过程，这个圆一般情况下调整过后会够到三个点（例如一般可以先缩小到触碰一个红点，再沿着这条半径反向移动圆心缩小到触碰另一个红点，再把圆心沿着红点中垂线平移，直到触碰一个蓝点，也有其他变化方法）。也就是说我们挑选不共线的三个点来做外接圆就可以了。特殊情况下，比如所有点共线的情况，可以变成以两个点为直径作圆。$n=1$特殊讨论下即可。

三点外接代码见个人页面。

题意描述诡异

但根据样例分析是给定$n$段$[l,r]$区间,将$[lmin,rmax]$划分成小区间,$[l,r]$可能会相同

然后需要找到一段递增的$l_{i_{1}}\leq r_{i_{1}} \leq l_{i_{2}} \leq r_{i_{3}} \leq \ldots$,使总长度最大

将区间变为$[l,r]=[l^{'},r^{'})$型,每段贡献就为$r^{'}-l^{'}$,且划分点为$r^{'}$

根据划分点$r^{'}$离散化后树状数组进行$dp$即可

by Hardict

首先将这个问题变成一个dp问题，dp值为到这一点的方案情况，如果多于1，则标记为2，否则为0或1,1的话还需要维护当前具体方案。我们观察$\le1000$间隔所组成的每一段，发现转移只能从段的最后一个元素进行，否则不可能。转移最多只有两种可能，$i-2$和$i-3$，并且要注意这连续的间隔不能$\ge 2000$才行，转移的时候，如果源头状态可能性多于1，则直接标记不用求方案，否则要求出新的方案值，为方案值去重合并，再看这一个点的dp值。

总体来说难度不大，注意思路要清晰。

by Max.D.

水题