CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2022 牛客暑期多校训练营7 ======
====== B ======

**题目大意：给定二维平面上的一个凸包，该凸包可绕对称轴任意旋转，求最终形成的立体的体积**

**若没有对称轴，则没有体积**

**若只有一条对称轴，则只需要找到这条对称轴，然后求若干圆台的体积和**

**若对称轴超过一条，则最终的立体是个球，其半径为凸包几何重心距凸包边界的最远点**

**求多边形对称轴**

**对于$n$个点的多边形，依次将夹角和边长存入数组，得到长为$2*n$的数组，然后将数组复制一遍接在后面，保证成环**

**用Manacher处理上述长为$4*n$的数组，不需要加入间隔符**

**对于位下标为$n+1$到$3*n$的位置，若其回文半径$\geq n$，则该位置存在一条对称轴，若位置对应为角，则经过该角顶点，若对应位置为边，则经过该边中点**

**为了避免精度误差，夹角可用点积，边长可用边长平方，这样可用保证数组内全为整数**

===== I-Suffix Sort =====
按照题目给定的最小表示法对字符串进行后缀排序。\\
考虑在较短时间内对后缀 $S[i:]$ 和 $S[j:]$ 排序，要求在短时间内能求出两后缀的 $Lcp$ 即可。先预处理出每个后缀对应的字符大小关系，并求出每个字符出现位置的差分数组，并建立后缀自动机，在求 $Lcp$ 时需要按相对大小枚举每个字符，求出最早的失配位置，再取最小值就能得到 $Lcp$，注意特判第一个字符。\\
单次判断复杂度 $O(26)$，排序总复杂度 $O(26\times n\log n$)

===== Replay =====

首先是C，因为题面是Constructive云云，所以直接脑补了一个对1-n的序列进行平移，直到平移出一个合法的解。

仔细想想会被hack，于是再把n-1的序列进行平移。

发现也被hack了，于是又随机了一大堆序列一起平移，这下总该hack不动了。于是过了。

之后是F，罗皓天之前一直在玩，发现i和x-i是等价的。于是就是一个简单链表操作。

于是就忘了判删空的情况了。判了之后就过了。

之后高湘一开始写J，他用的是一个dp做法。是个$O(n^{5})$的做法。

之后是G，罗皓天之前也一直在玩。玩了一会之后大概把结论玩出来了，很好写，于是抢过高湘一的键盘开始写G，很快过了。

高湘一tle了一发。看来$O(n^{5})$想过64稍微有点难度。我有个O(玄学)的搜索写法，于是打算写写。

wa了一发，感觉自己应该是有小数据错了，于是把高湘一的代码复制了一份，小数据跑dp，大数据跑搜索，就过了。

在那之前先写了个K，是个改编nim游戏。玩了一会猜出一个结论，之后跑了个莫队就过了。

期间高湘一和罗皓天在玩A。但是A题有两个k=5的数据，直接大力待定系数法。然后高湘一把k=4的推出来了。辛苦。

之后开始写B。整出来一个自己口胡的对称轴做法（居然跟正解差不太多？），然后尝试写，因为对于manacher不够熟悉，没有写完。

===== Dirt =====

C、F、J：见Replay

K:玩出的结论是所有数-1之后的值，但是在实际写代码的时候忘记了。

A:疯狂枚举k=4时的答案。
CVBB ACM Team

用户工具

站点工具

页面工具
