这是本文档旧的修订版!
date: 2020.07.13 12:00-17:00
题目大意: 定义 $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$ 时更新一下全局的答案。
题目大意:
题解: