这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
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)$。 | 定义 $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 ===== | ===== 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 ===== | ===== C. Cover the Tree ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | 简单题,懒得写了。 |
===== D. Duration ===== | ===== D. Duration ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | 签到题。 |
===== E. Exclusive OR ===== | ===== 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 ===== | ===== F. Fake Maxpooling ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | 签到题。 |
===== G. Greater and Greater ===== | ===== G. Greater and Greater ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | 签到题。 |
===== H. Happy Triangle ===== | ===== H. Happy Triangle ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | **题目大意**:一个多重集,初始为空,要求三种操作,插入、删除、给定 $x$ 查询是否能与多重集中的两个数组成三角形。 |
+ | |||
+ | **题解**:分两种情况讨论,若 $x$ 是最大的,那么在多重集中查询两次前驱即可,这个比较简单。否则,设最大值 $a>x$,那么应当有 $b\le a$ 且 $b+x>a$,显然 $b$ 应为 $a$ 的前驱。那么我们用一棵平衡树维护 $(a,a-\text{pre}(a))$,并维护第二维的区间最小值即可。 | ||
===== I. Interval ===== | ===== 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 ===== | ===== J. Just Shuffle ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | 签到题。 |
===== K. Keyboard Free ===== | ===== K. Keyboard Free ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | **题目大意**:有三个同心圆,半径分别为 $r_{1},r_{2},r_{3}$。每个圆上等概率随机一个点,问形成的三角形面积期望。 |
+ | |||
+ | **题解**:形式上是一个三重积分。有一个点可当做定点,这样变为两重,最内层积分可以积出表达式,最后一维 ''%%simpson%%'' 或切割区间求和均可。 | ||