2022-2023:teams:kunkunkun:2022-nowcoder-8

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2022-2023:teams:kunkunkun:2022-nowcoder-8 [2022/08/13 20:47]
sd_ltt
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-8 [2022/08/31 16:26] (当前版本)
purplewonder
@@ 行 5: / 行 5: @@
 对于每列，相当于将 $1\sim 2^{n+m}$ 映射为第一列进行求和操作。\\
 每次统计答案复杂度为 $O(n+m)$
+===== J =====
+**题目大意：给定一棵树，要求把这棵树放在二维平面上，且拥有对称轴**
+**容易想到树哈希和树的重心，首先求出树的重心，若只有一个重心则放在对称轴上，若有两个重心则放在对称轴两侧**
+**以重心为根进行树哈希，若子树的哈希值相等，则子树同构，应对称摆放**
+**对于对称轴上的点，哈希值相同的子树应该成对，重心允许两个奇数，因为可以向上向下沿对称轴摆，非重心只允许一个奇数**
+**对于不在对称轴上的点，直接把子树按哈希值排序，依次摆放**
+===== K =====
+**题目大意：给出$n$个点，需要依次求出前$i$个点围成的凸包的对称轴**
+**首先对所有$n$个点做Manacher**
+**考虑$\angle i12$，发现它在不断增大，而且如果凸包存在对称轴的话，一定有角与其相等**
+**对于前$i$个点来说，它可能和$\angle i-1i1$相等，特判一下，也有可能和最大凸包上的某个角相等，可以做个映射快速知道是哪个角**
+**根据上面的算法，最多只能找出$2*n$条对称轴，现在需要判断每条对称轴是否合法**
+**若需要判断某条对称轴是否合法，一些边界条件需要特判，中间大段可以用预处理的Manacher直接判断**
+===== Replay & Dirt =====
+因为这场一共就过俩题，所以replay和dirt写一起了。
+F算是一道有点毒的签到题。最开始是用的map，tle掉了。大概1e6用map会有些勉强。
+换成unordered_map。wa掉了。发现不应该寻找第一个匹配的，而是应该找所有匹配的的最小值，改过之后就过了。
+D是一个德州扑克题。是个很大的模拟。写了一个搜素。
+最开始wa掉了，因为判顺子大小的时候，没有判A2345最小。
+之后tle了，发现考虑了很多重复情况，写了个记忆化就过了。
+之后跑去想了很久的E，本来觉得还挺容易的，但是越想感觉越复杂，还是弃了。
+最后去做的是I，如果有更多时间兴许可以做出来的，但是之前花了挺多时间看其他题，所以到最后也没做出来。

2022-2023/teams/kunkunkun/2022-nowcoder-8.1660394843.txt.gz · 最后更改: 2022/08/13 20:47 由 sd_ltt