差别

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

--- 2022-2023:teams:kunkunkun:2022-nowcoder-8 [2022/08/13 20:32]
sd_ltt 创建
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-8 [2022/08/31 16:26] (当前版本)
purplewonder
@@ 行 2: / 行 2: @@
 ===== A-Puzzle: X-Sums Sudoku =====
 给出一个数独，求在其字典序最小时的 $X-num$。\\
-设坐标从 $(0,0)$ 开始，将数独分为 $2^m\times 2^n$ 个区域，且每个区域大小为 $2^n\times 2^m$，给每个区域编号 $A_{a,b}$，显然区域 $A_{0,0}$ 的编号已知，找规律发现 $(i,j)$ 对应的数应该为区域 $A_{0,0}$ 中坐标为 $(i%(2^n) \oplus b,j%(2^m)\xor a)$
+设坐标从 $(0,0)$ 开始，将数独分为 $2^m\times 2^n$ 个区域，且每个区域大小为 $2^n\times 2^m$，给每个区域编号 $A_{a,b}$，显然区域 $A_{0,0}$ 的编号已知，找规律发现 $(i,j)$ 对应的数应该为区域 $A_{0,0}$ 中坐标为 $(i\%(2^n) \oplus b,j\%(2^m)\oplus a)$ 所对应的数，其中 $(a,b)$ 为 $(i,j)$ 所在区域编号，即 $a=\left\lfloor\dfrac i{2^n}\right\rfloor,\ b=\left\lfloor\dfrac j{2^m}\right\rfloor$。于是可以 $O(1)$ 计算 $X$，根据题意需要求长度为 $X$ 的前缀和。对于每行，发现每 $2^p$ 个数中前 $2^{p-1}$ 个数与后 $2^{p-1}$ 个数都小于等于或者大于一个数 $k$，即可以根据变化关系倍增求出前缀和。
+对于每列，相当于将 $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，如果有更多时间兴许可以做出来的，但是之前花了挺多时间看其他题，所以到最后也没做出来。

CVBB ACM Team

用户工具

站点工具

差别

页面工具