可能是省选退役前的最后一次$51nod$了

前两题水的吧

后面四题我貌似都跟题解不一样。。

$C$

首先让点$x$为随便一个端点

让点$y$使$x,y$将多边形长度分成两半

然后一直旋转，每次让距离下一个端点比较近的点移动到下一个端点

令$S$为指定的某一侧的面积

感觉它说不定可以二分

如果一次移动使$S$从小于一半变成大于一半就二分找出答案。

如果能做到两边$S$都会大于一半，但中间$S$小于一半我就错了。不知道能不能卡

复杂度$O(n+log)$

$D$

特判$2$

剩下的质数都是奇数

枚举右端点，枚举区间长度，发现左端点是隔着一个的连续的

就是说把点按奇偶分类后左端点是一个连续的区间

维护前缀和$O(1)$算

$O(n^2/logn)$

卡卡常就过了

$E$

考虑询问时枚举比较小的集合，在大的集合里$O(1)$找到前驱后继

那么如果对大于根号的集合两两求出答案，询问就是根号的

对于合并集合操作

如果合并后大于根号的话是要更新跟所有大于根号的集合的答案的

此时如果原来就大于根号的话是可以直接用原来信息的

如果原来小于根号的话就暴力枚举，$O(1)$找前驱后继

复杂度还是$n$根号

现在问题就是支持合并两个集合，$O(1)$询问某个集合中某个数的前驱后继

考虑用类似线段树合并的方法合并值域分块

就是把分块看成三层线段树的话，第二层暴力合并，叶子只有在两个都非空的时候合并

复杂度$n$根号

可能因为常数比标算大，卡常后才能过。

$F$

后缀数组水题

假如是一个字符串的话

枚举每个后缀

设长度为$len$,跟所有未枚举后缀的$lcp$长度为$mx$

它的贡献就是长度在$[mx+1,len]$的前缀

小于$k$的暴力

大于$k$的是一个区间，$O(1)$算

多个串是类似的

复杂度为$O(构建后缀数组)+O(n*k)$

$upd$

$C$正解性好像能证。。

其实就是跟题解一个证法

就是存在$f(x1)>0,f(x2)<0$的话，一定存在$f(x+1)>0,f(x)<0$

($f(x)$只是表达个大概的意思)