CVBB ACM Team

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

用户工具

站点工具

页面工具
