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 ...

P4003 无限之环 如果直接来做其实一点头绪都没有，于是我们可以点开 Infinity Loop 玩了一会。 玩的过程中发现一个明显的性质不管最终答案是什么样的，每个插头都是被另外一个插头配对的。 那么本质上就是每个格子的 $4$ 个位置有若干个是插头，每个插头需要被配对，每次旋转需要代价，求最小代价使得所有插头被配对。 显然对于一个插头我们被配对当且仅当其和 $1$ 个另外的插头配对。 我们考虑拆点限制这个 $1$，考虑使用费用流。 我们可以考虑对于每个格子拆成 $5$ 个点，一个点来限制其他点的 $1$ 次流量，然后剩下 $4$ 个点表示插头，因为需要有源点和汇点我们不妨仿照骑士共存问题进行染色。 考虑旋转是怎么表示的，本质上就是看这个 $1$ 的流流到哪里去，就是简单连边。 一个插头，相邻位置费用为 $1$，对面为 $2$。 $\tt L$ 形插头，考虑最上面的位置顺时针旋转 $1$ 次可以使最下面插头合法，所以是对面连边费用为 $1$。费用为 $2$ 的情况可以不考虑，因为本质上就是两次费用为 $1$ 的旋转。 三个插头，可以通过一次相邻旋转或者一次相对旋转，费用为 $1, ...

USACO - Au - T1 考虑要么是奶牛去匹配苹果要么是苹果取匹配奶牛。 有一个很简单的贪心，能接住就接。 考虑对于 $x = x, y = t$ 建立笛卡尔坐标系。 对于一个苹果 $(a, b)$ 其能被奶牛接住当且仅当其在 $y = x + b - a$ 的直线下方。 这个东西本质上就是一个三角形，考虑将平面旋转 $(a, b) \to (\frac{a + b}{\sqrt 2}, \frac{a - b}{\sqrt 2})$。 这个 $\frac{1}{\sqrt 2}$ 其实本质上是没有关系的，放缩一下答案不会变化。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>#include ...

USACO - Ag - T1 内向基环树森林，既然可以自己给定排列我们对于链的答案肯定是全部都能算上的。 对于环发现只会有 $1$ 个点没有算上贡献取最小的即可。 或者使用最大生成树也可以，因为本质上一个基环树断掉一条环上的边即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <bits/stdc++.h>#include <bits/extc++.h>using namespace std;using namespace __gnu_cxx;using namespace __gnu_pbds;namespace Legendgod { namespace Read {// #define Fread #ifdef Fread const ...

USACO - Cu - T1 发现翻转是改变一个区间的奇偶性，其声明只能对于偶数位置进行前缀区间翻转，所以考虑直接对于相邻两个数进行考虑。 翻转只会对于两个位置不同生效，考虑对于连续的一段一起翻转即可。 翻转贡献可能为 $1, 2$。看是否是一个前缀的形式。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <bits/stdc++.h>#include <bits/extc++.h>using namespace std;using namespace __gnu_cxx;using namespace __gnu_pbds;namespace Legendgod { namespace Read {// #define Fread #ifdef Fread const int Siz = (1 << 21) + ...