差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:2020-nowcoder-multi-2 [2020/07/16 22:51]
chielo [A. All with Pairs]
+++ 2020-2021:teams:intrepidsword:2020-nowcoder-multi-2 [2020/07/17 00:44] (当前版本)
admin update
@@ 行 12: / 行 12: @@
 定义 $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

用户工具

站点工具

差别

页面工具