T1 邦布照相 [贪心]
Description
给定长度为 \(n\) 的序列和一个 \(k\)，在序列中找到字典序最小的且是 \(k\) 的排列的子序列，输出答案。
\(k\le n\le 2\times 10^5\)。
Solution
考虑贪心，遍历序列，用一个类似单调栈的东西维护答案，如果这个数在栈中出现过，便跳过，如果没出现过，先把栈顶的大于等于它的，且后面还有的数弹出去，放到后面选，然后再入栈。
显然这样是最优的。
Summary
虽然思路很简单，但考场上想太复杂了，导致耗时过长。
T2 圣诞树装饰 [记忆化搜索]
Description
给定一棵二叉树，除叶子外都有左右两个儿子。
有些叶子有权值 \(1\)，有些为 \(0\)。
定义一棵树是合法的当且仅当对于每个点，左右子树权值和之差不超过 \(1\)。
可以进行任意次操作，每次可以将一个叶子的权值移动到另一个叶子，求最小操作数，或报告无解。
Solution
无论怎么移动，所有权值的总和是不变的，所以我们可以自顶向下搜索来计算贡献。
- 设 \(f(u,j)\) 表示以 \(u\) 为根的子树 需要 有多少权值，整棵树的权值记为 \(tot\)，
- 从 \(f(root,tot)\) 开始搜，如果 \(tot\) 为偶数，说明两边只有一种情况，\(f(son,tot/2)\)，
如果为奇数，则有两种情况，分别搜索并取最小值即可。 - 边界：叶子节点，若 \(tot\) 和该叶子的权值不同，记 \(1\) 贡献，否则不计，无解则是 \(tot> 1\)。
- 最后答案除以二即可，因为取出一个权值可以和加上一个权值合并为同一操作，但是计算了重复了。
Summary
并非什么高级算法，主要是思维难度，考场上要避免过度依赖高级算法，导致想得太复杂。
T3 新闻 [差分，并查集]
Description
给定一个字符串和 \(m\) 个操作区间，每次操作可以选择一个区间，并将字符串中这个区间内的所有字符变成它的后继（a->b，z->a），问是否可以将字符串变为回文串。
Solution
对原字符串进行差分，\(a_i=s_i-s_{i-1}\)，因为要变成回文串，则每两个点是要对称的，假设分别为 \(i\) 和 \(j\)，那么 \(j=n-i+1\)，我们发现，当且仅当对于每对 \(i\)，\(j\)，都有 \((a_i+a_{j+1}) \bmod 26 = 0\) 时，该串满足回文串。
所以一开始我们可以将每对 \(a_i\) 和 \(a_{j+1}\) 合并，然后对于每个操作区间，由于原序列的区间修改等价于差分序列两点修改，所以我们将 \(a_l\) 和 \(a_{r+1}\) 合并即可。
最后对于每个连通块，判断权值和 \(\bmod 26\) 是否为 \(0\)，是则合法，否则输出无解。
Summary
并查集好题，有一定的思维难度，转换很巧妙。
T4 匹配 [图的构建]
Description
在一个二维平面上有 \(n\) 个点，两个点若横坐标或纵坐标相等，则称它们是可匹配的。
问平面上的点是否可以两两匹配。
Solution
将每个原图的点记为圆点，把坐标系中每个横纵坐标看成一个点，记为方点，每个圆点与它的横纵坐标（方点）分别连边，问题转换为在途中是否能找出 \(n/2\) 条端点互不相同的，端点都是圆点的，长度为 \(2\) 的链。
先求出该图的生成树，也可以直接 dfs，就没这么麻烦。自底向上匹配。
如果当前的是圆点，跳过。
如果是方点，将它的儿子节点（一定是圆点）且是没匹配过的点两两配对，如果最后剩一个，将剩下的那个和该方点的父亲（也一定是圆点）匹配。
最后检查一遍所有点是否都被匹配过即可。
需要离散化。
Summary
解法有很多，重点在图的构建，所以建模思维很重要。
标签：匹配,XYD1008CSPS,圆点,tot,方点,权值,序列 From： https://www.cnblogs.com/chenwenmo/p/18453543