用户工具

站点工具


2020-2021:teams:intrepidsword:2020-nowcoder-multi-2

这是本文档旧的修订版!


Contest Info

date: 2020.07.13 12:00-17:00

practice link

Solutions

A. All with Pairs

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

题解

B. Boundary

题目大意: 给平面上的 $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。三元组数一下最多相同的数量即可。

C. Cover the Tree

题目大意

题解

D. Duration

题目大意

题解

E. Exclusive OR

题目大意

题解

F. Fake Maxpooling

题目大意

题解

G. Greater and Greater

题目大意

题解

H. Happy Triangle

题目大意

题解

I. Interval

题目大意

题解

J. Just Shuffle

题目大意: 当前有一个闭区间 $[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$ 时更新一下全局的答案。

K. Keyboard Free

题目大意

题解

2020-2021/teams/intrepidsword/2020-nowcoder-multi-2.1594914095.txt.gz · 最后更改: 2020/07/16 23:41 由 chielo