P7987 [USACO21DEC] Paired Up G首先考虑我们匹配肯定是相邻匹配的，之后还有一种可能是间隔一个匹配的。 对于这样进行 $\tt Dp$ 设 $f(i, j)$ 其中 $j$ 是 $0/1$ 表示 $1 \sim i$ 未匹配点的奇偶性。 考虑如下 $4$ 种类转移，设 z = i & 1，$las$ 表示最大的 $x_i - x_{las} > K$ 的位置。 中间有一段是可以内部匹配的 $f(i, z) = f(las, !z) + y_i$。 $x_i - x_{i - 1} \le K$ ，考虑让 $i, i - 1$ 匹配 $f(i, z) = f(i - 1, z)$。 $x_{i + 1} - x_i \le K$，考虑让 $i, i + 1$ 匹配，那么匹配点的奇偶性改变 $f(i, !z) = f(i - 1, !z)$。 $x_{i + 1} - x_i \le K$，考虑跳过这个位置，有 $f(i, !z) = f(las, z) + y_i$。 123456789 ...

P8099 [USACO22JAN] Minimizing Haybales P考虑交换操作会自然想到贪心，考虑贪心选择。 现在对于贪心有一个唯一的问题：是否存在 $i < j, h_i > h_j$ 在 $i$ 进行交换之后 $j$ 不能到达 $j$ 先手操作的最优位置。 考虑 $i$ 向左操作的过程，其可以经过的是 $[h_i - k, h_i + k]$ 的部分，$j$ 经过的是 $[h_j - k, h_j + k]$。 仔细想想确实也没有影响，那么我们可以得到一个贪心。 从左向右扫维护最小字典序的序列，之后二分到一个最大的可以移动的位置，之后再次二分找到最优位置，也就是使得后缀没有 $< h_i$ 的位置。 我们使用平衡树上二分就可以解决这题。 一开始我做的时候，我贪心证伪了 $\cdots$ 这样显得我很呆 $\cdots$ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 ...

CF917E Upside Down 比较有趣的一个题。 对于 $i \to j$ 的路径我们很容易想到分成两部分进行计算： $i \to lca$ $lca \to j$ 跨过 $lca$ 对于前面的部分我们建立 $\tt ac$ 自动机，之后本质上就是单点加区间查询，我们树状数组维护一下。 我们方便处理的是从 $lca \to i$ 的路径，那么我们考虑对于不方便的情况直接建立反串的 $\tt ac$ 自动机即可。 对于跨过的部分我们不妨考虑字符串的分界点为 $x$，那么左边就是 $[1, x]$ 右边是 $[x + 1, n]$。对于两边发现有一个端点是固定的，我们考虑根据这个进行计算。 我们先考虑找到一个合法的串，我们不妨只考虑 $[x + 1, n]$ 的情况另一种情况同理，贪心考虑可以知道这个串右端点是固定的，考虑两段从 $\tt lca$ 经过若干步走到字符串末尾的串设长度为 $a, b, a < b$。因为末尾部分是相同的，所以 $a$ 是 $b$ 的 $\tt border$，那么我们贪心可以考虑选取尽可能长的串。 选取串我们可以考虑尽可能长的串，经过简单 ...

P5287 [HNOI2019]JOJO 加入 $x$ 个字符 $c$，保证相邻加入操作 $c$ 不同。 查询每个前缀的 $\tt border$ 长度和。 如果不看输入感觉没有什么优秀的做法，输入提示了 $x$ 个 $c$ 肯定和做法有关。 我们尝试计算加入 $c$ 的 $\tt border$，首先找到加入前串 $S$ 的 $\tt border$，之后如果后面恰好有 $\ge x$ 个 $c$ 说明是可以匹配的，如果没有说明这个不是 $\tt border$，考虑继续向前找当前 $\tt border$ 的 $\tt border$。 既然相邻操作 $c$ 是不同的，考虑将一次操作看成一个点，$S$ 的 $\tt border$ 的结尾肯定恰好是一个完整点，不然之后不可能跟上 $c$。考虑跳 $\tt border$ 后每次后面跟着的 $c$ 是逐渐变多的，考虑如果减少的话 $\tt border$ 是可以增长的。 然后对于一段都能匹配是一个等差数列求和。 我们考虑暴力跳 $\tt border$ 是不行的，考虑优化，我们如果 $\tt border$ 的长度 $\ge \fr ...

CF700E Cool Slogans首先子串变成 $\tt SAM$，我们考虑出现两次不妨考虑在区间 $[l, r]$ 那么我们的串肯定也是 $[l, r]$ 多了肯定是不优的。 然后对于 $s_i, s_{i - 1}$ 可以发现 $s_{i - 1}$ 是顶着 $s_i$ 的左右侧的，我们可以随便钦定一个进行考虑，不妨考虑 $s_{i - 1}$ 是 $s_{i}$ 的后缀。 考虑后缀自动机上 $x, y$ 其中 $y$ 是 $x$ 的祖先。如何描述 $x$ 中出现了两次 $y$。 我们明确 $\tt endpos$ 集合在 $\tt parent$ 树上就是子树，对于一条链根据定义有上边串是下面串的后缀，所以肯定出现一次的。 我们只需要考虑另外一个点的情况，不妨考虑 $x$ 长度为 $len(x)$，可以发现如果 $y$ 的另外结束节点是在 $[pos(x) - len(x) + len(y), pos(x) - 1]$ 那么肯定是合法的。 我们可以使用经典套路线段树合并来查询。 考虑如何计算答案，如果上述 $x, y$ 是合法的我们考虑设 $f(x)$ 表示以 $x$ 结尾的 ...

P4351 [CERC2015]Frightful Formula 首先将原来的式子看成网格的贡献，发现 $c$ 比较难处理，我们先不管 $c$。 那么 $a, b$ 本质就是向右走一步和向下走一步的贡献。 那么对于位置 $(x, y)$ 其最终的贡献是 $\dbinom{2n - x - y}{n - x} \times a^{n - x} b^{n - y}$。 我们只需要考虑 $(1, i), (i, 1)$ 即可。 之后考虑 $c$ 的贡献怎么计算，发现位置 $\forall i, j, i \ge 2, j \ge 2$ 会产生贡献。 显然 $c$ 的贡献同上。$$ans = \sum_{i = 1} ^ n \binom{2n - 1 - i}{i} (a^{n - 1} b^{n - i} + a^{n - i}b^{n - 1} ) + c\sum_{i = 2} ^ n \sum_{j = 2} ^ n \binom{2n - i - j}{n - j} a^{n - i}b^{n - j}$$前面部分可以直接计算，考虑计算后 ...

AT3956 [AGC023E] Inversions 首先来看总方案数怎么算，如果将每个数按照 $a_i$ 排序其排名为 $b_i$，设 $c_i = a_{b_i}$。$$f(n) = \prod_{i = 1} ^ n (c_i - i + 1)$$考虑对于每个逆序对单独计算贡献，考虑 $i < j, a_i < a_j$。 可以让 $a_j = a_i$ 之后进行计算。$$g(i, j) = \frac{1}{2} \times f(n) \times \frac{a_i - b_i}{a_j - b_j + 1} \times \prod_{k = b_i + 1} ^ {b_j - 1} \frac{c_k - k}{c_k - k + 1}$$对于 $i > j, a_i < a_j$ 的情况，考虑逆序对不好计算使用补集转化。$$f(n) - g(i, j)$$那么我们只需要求出 $g(i, j)$ 即可。 考虑对于每个 $j$ 考虑其前缀的贡献，对于 $\dfrac{f(n) \time ...

P3296 [SDOI2013]刺客信条 题目简化： 给定一棵树，每个点有两个 $0, 1$ 权值，合适地安排节点在同构树中的顺序，使得前后对应的权值不同节点个数最小，并输出。 本质上就是对于同构树来考虑每棵子树如何配对的问题，所以先找到中重心之后使用树 $\tt Hash$ 判断出同构。 对于同构的两棵树考虑分成若干组子树，每组子树都是同构的，对于每组子树我们事实上可以任意匹配，需要选择出最优解保证每棵子树都有匹配且边权最小。这个本质就是最小权二分图匹配，直接使用 $\tt KM$ 即可。 复杂度是 $O(n^3)$ 的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114 ...