date: 2020.07.13 12:00-17:00

practice link

题目大意： 定义 $f(s, t)$ 为 $s$ 的前缀与 $t$ 的后缀中，长度最长的公共元素的长度，给 $n$ 个串，求一下 $\sum_i \sum_j f^2(s_i, s_j)$。

题解：

题目大意： 给平面上的 $n$ 个点，求一个过原点的圆，使得落在圆边界上的点尽可能多，输出一下最多的情况下，在圆上的点的数量。

题解： 首先枚举一个点 $P$，因为给的点都是不同的，那么原点 $O$、$P$，再与其它的某个点 $Q$，就能确定一个圆了。那么再枚举点 $Q$，记录下与 $O$、$P$ 所共的圆的方程的两个参数 $D$, $E$（常数项 0）： $$ D = -\frac{\left|\begin{array}{ccc} x_P^2 + y_P^2 & y_P \\ x_Q^2 + y_Q^2 & y_Q \end{array}\right|} {\left|\begin{array}{ccc} x_P & y_P \\ x_Q & y_Q \end{array}\right|}, \quad E = \frac{\left|\begin{array}{ccc} x_P^2 + y_P^2 & x_P \\ x_Q^2 + y_Q^2 & x_Q \end{array}\right|} {\left|\begin{array}{ccc} x_P & y_P \\ x_Q & y_Q \end{array}\right|} $$

出现的三种行列式都是整数，记下来后把分母统一成正的，然后都除掉 gcd。三元组数一下最多相同的数量即可。

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意： 当前有一个闭区间 $[1, n]$，现在可以对该区间任意进行操作，操作有两种，一种是左端点 $\pm 1$，一种是右端点 $\pm 1$。

现在不想让该区间能被操作到两个端点相等，所以题目给出了 $m$ 条规则，第 $i$ 条规则是花费 $c_i$ 的代价，若 $d_i = L$ 则 ban 掉区间 $[l_i, r_i]$ 与 $[l_i + 1, r_i]$ 之间的变化操作，若 $d_i = R$ 则 ban 掉区间 $[l_i, r_i]$ 与 $[l_i, r_i - 1]$ 之间的变化操作。

求使得区间 $[1, n]$ 操作不到两个端点相等情况下的最小花费。

题解：

太明显的最小割，每个合法的区间作为点的集合，让 $S$ 集合必有 $[1, n]$，让 $T$ 集合必有 $[i, i], \forall i$。互相可以变化的区间之间连一条边，如果规则中能干掉这个变化则以相应的费用作为边权；否则以无穷大作为边权。源点和 $[1, n]$ 连一条无穷大的边，$[i, i]$ 与汇点连无穷大的边。

好，$\mathcal{O}(n^2)$ 个点，直接跑大概会死。（试了一下 ISAP，确实会死）

发现这个图也就是半个格点图，即平面图，平面图最小割 = 对偶图最短路。做完了。

这类题实现上一般不需要真的把图建出来。可以以区域相邻的长度最长的区间作为区域的表示，四个方向有一个变化量的表就行。初始时把右端点为 $n$ 的先整出来，relax 跑到左端点为 $0$ 时更新一下全局的答案。

题目大意：

题解：