这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2022-2023:teams:kunkunkun:2022-nowcoder-7 [2022/08/12 19:35] sd_ltt 创建 |
2022-2023:teams:kunkunkun:2022-nowcoder-7 [2022/08/31 16:01] (当前版本) purplewonder |
||
---|---|---|---|
行 1: | 行 1: | ||
====== 2022 牛客暑期多校训练营7 ====== | ====== 2022 牛客暑期多校训练营7 ====== | ||
+ | ====== B ====== | ||
+ | |||
+ | **题目大意:给定二维平面上的一个凸包,该凸包可绕对称轴任意旋转,求最终形成的立体的体积** | ||
+ | |||
+ | **若没有对称轴,则没有体积** | ||
+ | |||
+ | **若只有一条对称轴,则只需要找到这条对称轴,然后求若干圆台的体积和** | ||
+ | |||
+ | **若对称轴超过一条,则最终的立体是个球,其半径为凸包几何重心距凸包边界的最远点** | ||
+ | |||
+ | **求多边形对称轴** | ||
+ | |||
+ | **对于$n$个点的多边形,依次将夹角和边长存入数组,得到长为$2*n$的数组,然后将数组复制一遍接在后面,保证成环** | ||
+ | |||
+ | **用Manacher处理上述长为$4*n$的数组,不需要加入间隔符** | ||
+ | |||
+ | **对于位下标为$n+1$到$3*n$的位置,若其回文半径$\geq n$,则该位置存在一条对称轴,若位置对应为角,则经过该角顶点,若对应位置为边,则经过该边中点** | ||
+ | |||
+ | **为了避免精度误差,夹角可用点积,边长可用边长平方,这样可用保证数组内全为整数** | ||
+ | |||
===== I-Suffix Sort ===== | ===== I-Suffix Sort ===== | ||
按照题目给定的最小表示法对字符串进行后缀排序。\\ | 按照题目给定的最小表示法对字符串进行后缀排序。\\ | ||
行 5: | 行 25: | ||
单次判断复杂度 $O(26)$,排序总复杂度 $O(26\times n\log n$) | 单次判断复杂度 $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时的答案。 |