可能是省选退役前的最后一次$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(\mathrm{构}\mathrm{建}\mathrm{后}\mathrm{缀}\mathrm{数}\mathrm{组})+O(n\ast k)$

$upd$

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

其实就是跟题解一个证法

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

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

打了这么久，好像第一次rank1啊

t1

我打的50分dp

不过好像加常数优化后可以拿60-70分(我拿了60)

t2

f[i]表示gcd(边权)是i的倍数的方案数

如果把f[i]搞出来了，那么就可以nlogn求出答案。

f[i]其实就是矩阵树n^3求啊

不过加一个，如果不连通就直接退出

我也不会算复杂度

t3

一开始想打fwt拿50分，不知道为什么拿了40

后来想到，就枚举i,j和n,m的二进制的最长公共前缀

之后就可以搞了

t4

就是max-min=r-l

且不存在重复的数

把每对相邻重复的数l,r

以r为下标放到线段树里

就可以了

t5

分治

对两边所有不同的gcd,or暴力枚举

似乎是nlog^3的

但跑的挺快。。

t6

一开始把那个o(N)的方法看了一遍

后来发现构建笛卡尔树空间会开不下

分块 块间st+前后缀min是可以o(1)的

但询问在块内怎么办呢

答案就是块内直接暴力(因为随机，假设块大小为k，那么复杂度就是k/n n k=k * k)

upd:

t5复杂度是nlog的

t4 fwt中间没有取模 爆了long long 加了后拿到50分

第一次参加zjoi，30+30。我果然太弱了。

感觉这应该是很长一段时间里对我最重要的比赛了，还是记录一下吧。

day1

是在我们学校的。

看到第一题觉得可以dp 之后就花了大概3个小时想了现在也不知道对不对的dp

后来虽然过了很小数据的对拍，但忘了测大样例

最后也只有20分

第三题本来想打30分，但fft有点记不清了，后来就打了10分。

第二题我没发现他就是个单点修改，后缀求和。

不知道他在干什么，然后就在最后快没时间的时候想打个10分，结束时还差个逆元没打，所以就0分了。

龙爷t2发现了那个性质，似乎拿了70分。

day2

t1，我想先把n-1块看成一块，假如得到了他移动的代价，

之后就记忆化搜索搜出来他和第n块一起移动的代价。

但我没考虑到移动的过程是先颠倒在最后才达到目标的。

最后拿了10分。

不少人推出了k=2时如何移动，拿了40分。

t2，我就打了20分。先把询问的人在线段树走一遍打上标记，之后把[l,r]走一遍，走的时候顺便得到lca。

龙爷想了个O(nlog^2)的做法，

就是发现如果一个左端点被区间[l,r]覆盖，那么l<=他的l，r>=他的r且r<他爸爸的r。

而求的东西类似带权距离和，是可以用点分树做的。

那么这题就是个矩形修改单点询问。

枚举右端点，线段树套点分树维护左端点。

然而实际上常数较大，很难跑过去，最后也只拿了10分。。。。。

以为稳进队的龙爷就这样挂了。

第三题我随便打了个线段树维护区间最小后缀，比较两个后缀的时候用二分lcp，线段树维护hash来检验的方法。

不知道怎么支持区间加，所以也不知道怎么才能拿随机和10^4的分(现在还是不知道这两个部分分什么意思)

但没修改是nlog^2的，以为30分总有的吧。

然而会t。原因大概是我觉得数值太大，hash有点虚，于是用了3个取模的hash。

如果用后缀数组初始化复杂度就是nlogn+mlog^2，应该就没问题了。但我也没时间打了。

特别厉害的sjj学长也没能进队。

zjoi怎么这么难啊。