如果 Latex 挂了多刷新awa。
这道题最开始读题的时候并没有理解题意，读题十分重要！之后并没有想到可以将长宽转换成面积和长，也没有想到新状态的面积与长的整除关系，这道题完全挂了。
AC code
这道题最开始思路想复杂了，但是应该能写的出来，代价是花费大量的时间。考虑讲两个集合分别定义为，已经询问过的特征和询问过且拥有的特征，这样子就可以方便的对每一个数进行与来快速判断。我并没有想到这一点，我是分别将两个集合定义成拥有的特征和不拥有的特征。这样在转移上拥有一些困难，比较复杂。
定义了状态之后对状态的转移出了一点小差错，想到了是两种情况取上一个 max 但是却没有想到对于每一种集合都可以取得 min，由于我并没有考虑到两种情况之一已经包含必要的的操作导致的，毕竟都取了 max。
AC code
看到这道题，很容易想到最长公共子序列的转移方法 $F[i][j] = \min(F[i - 1][j], F[i][j - 1])$ + 1 。
但是造成的贡献不方便计算，因为我们不知道一种颜色什么时候开始，也不知道什么时候结束。
考虑引入一个数组，$C[i][j]$ 代表字符串 $a$ 前 $i$ 个字符，字符串 $b$ 前 $j$ 个字符中，已经出现过但在接下来的字符中还会出现的字符的个数。
为了计算这个数组，我们需要记录两个字符串中每一个字符第一次出现的次数，和最后一次出现的次数。
这样转移方程式就变为 $F[i][j] = \min(F[i - 1][j] + C[i - 1][j], F[i][j - 1] + C[i][j - 1])$。
还有一点值得注意：先转移 $F$ 再转移 $C$，在转移 $C$ 时还需要考虑两个字符串的情况。
总结：
- 有两个串的动态规划问题往往需要 $i$ 和 $j$ 分别代表两个串的信息。
- 花费往往就是题目中我们需要求解的值。
AC code
定义 $F(i, j, 0)$ 代表从 $i$ 访问到 $j$ 最后停留在 $i$ 点所需要的最小时间。$F(i, j, 1)$ 代表停留在 $j$ 点所需的最小时间。可以得到如下转移方程：
F(i,j , 0) = \min(F(i + 1, j, 0) + x_{i + 1}-x_i, F(i + 1, j, 1) + x_j - x_i)，分别表示从 $i + 1$ 移动到 $i$ 或从 $j$ 移动到 $i$ 。F(i, j, 1) = \min(F(i, j- 1, 1) + x_j - x_{j - 1},F(i, j - 1, 0) + x_j - x_i) ，分别表示从 $j - 1$ 移动到 $j$，或从 $j- 1$ 移动到 $i$。
时间复杂度 $O(n ^ 2)$
区间 DP 三维挺常见的。
AC code
题目大意
给定若干个 $1\times 2$ 和 $2\times 1$ 的地毯，现有若干个特殊点，用 * 表示，求覆盖这些点最小需要多少张地毯。
解题思路
正难则反，由题意可知：设由 $n$ 个特殊点，则覆盖掉所有的特殊点最多需要 $n$ 张地毯。若有 $m$ 张地毯能覆盖两个特殊点，则需要的地毯数最少，此时问题转化为求 $m$ 的最大值。
很显然，对于 o 来说，无需过多处理，忽略掉即可。
对于每一个特殊点，我们将与其相邻的特殊点连边，可以得到一个二部图，图的每一条边代表一种放置地毯的方案，而其两侧的点则代表其覆盖的特殊点。
我们要求得 $m$ 的最大值，但很显然覆盖已经覆盖过的点对答案不会产生任何贡献，我们大胆一点，直接把每一个点想成只能使用一次，此问题就被转化成了二分图最大匹配。
可以使用匈牙利解决此问题，但有一点值得注意：我们建的是无向图，固最大匹配边数会重复计算一次，需要除以二解决。
TSP 问题+记忆化搜索+状态压缩
TSP 问题是组合优化中的一个经典问题，给定一 个城市列表及每两个城市之间的距离，一个旅行推销员希望从某个城市出发，经过所有的城市各一次后，最 终返回起始城市。目标是找到总旅行距离最短的路线。
对于这道题，定义 $F(i, S)$ ：当前在节点 $i$ 的位置，还需要访问集合 $S$ 中的点各一次最后回到节点 0（也就是起点）的最短长度。边界条件为 $D(i, {}) = dis(i, 0)$ 。对于 $S$ 非空，考虑从 $i$ 走到 $S$ 中的点 $j$ ：$D(i, S) = \min_{j\in s} {D(i, S - j) + dis(i, j)}$ ，其中 $dis(i, j)$ 是 $i$ 到 $j$ 的距离。
时间复杂度 $O(n^22^n)$
AC code
一个标准的最短路，但是在计算距离这一方面需要注意，当我们来当一个赛道上时，会有以下几种情况：
- 赛道正在开放，且在通过赛道之前赛道不会关闭，时间即为通过赛道的时间
- 赛道正在开放，但是剩余时间不足以通过赛道，时间即为等待时间加上关闭时间加上通过时间。
- 注意连边的时候，若开放时间小于所通过的时间，那么这条边就不用链接了。
总结：看到最短路的题目，认真分析新的距离，无需多虑，直接跑最短路就可以，但是对于2023年CSP的一道题目，就需要认真分析性质，然后作答。
最短路的贪心已经是证明过的了，无需再多虑。
数论题，我们需要知道：
- $a \oplus b = c $ 等价于 $a\oplus c = b$。
那么我们就可以枚举 $a$ 和枚举 $c$，然后算出 $b$，接着验证是否有 $\gcd(a, b) = c$, 因为 $c$ 时 $a$ 的约数，时间复杂度 $O(n\log n)$，而计算 $\gcd$ 的时间是 $O(\log n)$，总体时间复杂度 $O(n(\log n)^2)$。
时间复杂度过高，无法通过本题，考虑如何优化。
此时我们暴力打出 $a$、$b$、$c$ 之间的关系，我们可以发现出一个规律 $c = a - b$。
证明：易得 $a - b\le a\oplus b$，且 $a\oplus b \ge \gcd(a, b) = c$，考虑使用反证法，假设 $a -b > c $，可以得到 $c < a - b \le a\oplus b$，与 $c = a\oplus b$ 矛盾，故 $a - b = c$ 得证。
时间复杂度 $O(n \log n)$。
值得注意的是：$\oplus$ 的运算优先级是低于 $=$ ，在进行判断的时候需要加 $()$。
但在考场上，我们就不能这么做，我们不需要管证明，我们直接打表看规律！！！
总结：
- 我们应当牢记：暴力出奇迹，打表出省一！ 谁告诉了我难题一定要推公式才能做呢？