Ptz2022 Summer Day4 Ivan Kazmenko Contest 3
B：若 \(n\) 为奇数，我们只需取补集；否则我们保留 \(n\) 是否存在，并将 \(2\cdots n\) 取反（std 做法：插入删除 \(1\)）。
D：信息量只有 \(2^{70}\) 级别，将值域分为 \(70\) 块，每个块分别决定是否保留所有数，一个块期望会有比较多的数，被失真后仍然大概率保留这个 bit。
F：给一个点关于邻居度数的估价函数，将函数值最大的点连 \(5\) 个度数较大的点，询问取样一下算一算随机图期望权值（std 做法：图中有 \(K_5\) 的概率非常低，可以直接造一个 \(K_5\)）。
G：xor hashing。
C：划分成若干 \(5\times 5\) 的小方格，计算哈希值，询问矩阵一定包含至少一个整格。（另一个做法：保存所有 \(10\) 的倍数列的信息）
A：dp 方案数。
I：按照 \(d\) 分块，本地搜索/爬山/退火一下块的每个方案对应的最优策略，不过 \(d=3\) 已经足够了。
H：希尔排序/快排/std::stable_sort（timsort 是啥，不会）。
E：按照边数排序然后嗯贪。
J：不会搜索，听说要 beam search。
K：保证 \(n\ne 2^k-1\) 就是保证卡特兰数是偶数，于是我们可以使某个组合结构的奇数位置对应上一个组合结构的偶数位置，偶数位置对应上一个组合结构的奇数位置。把组合结构与长为 \(2n\) 的括号序列建立双射，这样就能给这组组合结构一个序关系：
- Skew polyminoes：我们只关心其轮廓线对应的两条不越过格路，写出两条格路的括号序列并交错归并；
- 321-avoiding permutations：贪心取出一个上升序列 \(S\)，其剩余部分 \(T\) 一定也是上升序列。我们从前往后扫描序列，维护一个集合 \(P\)，遇到 \(S\) 中元素加一个
(并插入 \(P\)，遇到 \(T\) 中元素加一个()，同时将 \(P\) 中比当前元素小的元素删去并插入)。 - Triangulations of an (n + 2)-gon：比较经典？考察 \((1,n+2)\) 所在三角形，递归三角形分割两个区域（可空）左右侧处理，最后将左侧外面套一层括号拼接上右侧。