CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Contest Info ======

date: 2020.07.13 12:00-17:00

[[https://ac.nowcoder.com/acm/contest/5667|practice link]]

====== Solutions ======

===== A. All with Pairs =====

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

**题解**：一个串 $s$ 可能会有多个 ''%%border%%''，考虑如何不重复计算贡献。容易想到对于 ''%%border%%'' $s$，其贡献为 $|s|^{2}-|b_{s}|^{2}$，其中 $b_{s}$ 为 $s$ 的最长 ''%%border%%''。而最长 ''%%border%%'' 就是 ''%%KMP%%'' 的过程中的 ''%%fail%%'' 数组。QAQ

最终做法为，求出所有前缀、后缀的 ''%%hash%%'' 值，并适当统计贡献。

===== 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。三元组 count 一下数量最多的即可。
===== C. Cover the Tree =====

简单题，懒得写了。

===== D. Duration =====

签到题。

===== E. Exclusive OR =====

**题目大意**：给你 $n$ 个整数，范围为 $[0,2^{18})$。对于每个 $i\in[1,n]$，求选取 $k$ 个数（可重）异或和的最大值。

**题解**：易见 $f(i+2)\ge f(i)$，选取两个相同的数即可。若 $i$ 已经满秩，则 $f(i)=f(i+2)$。任取 $i+2$ 个数的一组基，从其它数中任取两个数，可以讨论一下，不论它们被基如何表示，都能得到一组 $\le i$ 且奇偶性相同个数，异或和相同。因而，$f(i+2)\le f(i)$。

可用经典的 ''%%FWT%%'' 求解。

===== F. Fake Maxpooling =====

签到题。

===== G. Greater and Greater =====

签到题。

===== H. Happy Triangle =====

**题目大意**：一个多重集，初始为空，要求三种操作，插入、删除、给定 $x$ 查询是否能与多重集中的两个数组成三角形。

**题解**：分两种情况讨论，若 $x$ 是最大的，那么在多重集中查询两次前驱即可，这个比较简单。否则，设最大值 $a>x$，那么应当有 $b\le a$ 且 $b+x>a$，显然 $b$ 应为 $a$ 的前驱。那么我们用一棵平衡树维护 $(a,a-\text{pre}(a))$，并维护第二维的区间最小值即可。

===== I. Interval =====

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

===== J. Just Shuffle =====

签到题。

===== K. Keyboard Free =====

**题目大意**：有三个同心圆，半径分别为 $r_{1},r_{2},r_{3}$。每个圆上等概率随机一个点，问形成的三角形面积期望。

**题解**：形式上是一个三重积分。有一个点可当做定点，这样变为两重，最内层积分可以积出表达式，最后一维 ''%%simpson%%'' 或切割区间求和均可。
CVBB ACM Team

用户工具

站点工具

页面工具
