CF623_牛客博客

<br >
这真是一套极好的题目啊.....~~虽然我不会做~~
<br >

<br >

显然的，存在边的两个点，当且仅当两个字母分别为a和c的时候不满足

那么，我们把这道题目转换到补图上去求解

对于原图中度数为n-1的点，在补图中这个点一定是独立的，对于这样的点，他一定是b

其余的点，我们直接验证其所在联通块是否为二分图即可

验证的方法很简单，对于一个联通块，任意的把一个点设为a，那么与他直接相连的为相反的c，以此类推，最后验证即可

当然，不可能整个数列都被删除，而因为只能删除一段连续的区间，也就是说，a[1]和a[n]一定有其中之一被保留

那么，我们可以直接枚举a[1]和a[n]以及\(a[1] \pm 1\)和\(a[n] \pm 1\)的因子

不能注意的枚举，会TLE，我们要统一枚举好，去个重

最后剩下的问题，就是通过调整，使得整个数列包含一个共同的因子\(x\)了

我们考虑dp

f[i][0]表示到第i位，没有任何删除操作的花费；f[i][1]表示当前第i位处于删除序列中的花费；f[i][2]表示到第i位，删除操作已经结束的的花费

非常基础的dp，转移就很显然了

这道题目的思路也不是很难想啊

直接考虑二分答案，假设，当前我们二分的值为\(x\)

很简单的，我们可以根据\(x\)轴的左右界和\(y\)轴的上下界来得到答案

暴枚\(x\)轴的左端点\(x_l\)，显然，最优情况下，\(x\)轴的右界是横坐标\(x_t\)满足\(0\leq |x_t-x_l|\leq x\)且\(|x_t|\leq |x_l|\)的最右端点（可以直接二分来找到）

确定了\(x\)轴的左右端点，接下来的问题就是怎么确定\(y\)轴的上下端点了

显然，为了快速的求解上述的\(x\)轴右端点，我们对所有的坐标按照\(x\)排了序

那么，我们所选取的一段映射在\(x\)轴上的坐标一定是连续的一段

这样的话，我们只需要\(O(n)\)预处理关于排序后坐标的前后缀的\(y\)轴上的最大值和最小值就可以得到答案了

............然后....不要忘了全部在\(y\)轴上的情况，不要忘了为这样的情况的距离平方！~

似乎是......玄学题啊？

我们先来看看怎么计算吧，我们用\(f[i]\)表示第i回合及第i回合前结束的概率，\(k[i]\)表示第i个人被捉住的回数，\(p[i]\)表示第i个人每回合中被捉的概率

可以倒着来算

\[f[i]=(1-q[1]^{k[1]})*(1-q[2]^{k[2]})*\cdots *(1-q[n]^{k[n]})(q[i]=1-p[i])\]

用意就是用1减去所有猜不中的概率

那么，我们要求的答案就是

\[ans=(f[1]-f[0])*1+(f[2]-f[1])*2+\cdots +(f[T]-f[T-1])*T(T\rightarrow \infty )\]

那么，我们可以通过调整T的大小，来满足题目要求的绝对误差

现在的问题，就是怎么使得\(f[i]\)尽量的大，也就是满足最有情况

这个也比较显然，通过观察\(f[i]\)的式子即可发现，我们每一回合都会对一个\(q[i]\)，进行\(*(1-p[i])\)的操作

现在就是要经过这个操作以后，f[i]尽量变到最大

我们只需要找到最大的

\[\frac{1-q[i]*(1-p[i])}{1-q[i]}\]

所对应的第i项进行\(*(1-p[i])\)操作即为最优

最后还需要一个证明，那就是\(T\)究竟应该取多少.....我也不会啊，给个证明，自己看吧QAQ

不过，我的代码T只去了1e6，就过去了

然后还有一个long double的使用技巧(frank_c1太强辣)

好像是道多项式啊？弃坑....