这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 | |||
2020-2021:teams:intrepidsword:2020-nowcoder-multi-2 [2020/07/16 23:45] chielo [B. Boundary] |
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 ===== | ||
行 43: | 行 45: | ||
出现的三种行列式都是整数,把分母统一成正的,然后都除掉 gcd。三元组 count 一下数量最多的即可。 | 出现的三种行列式都是整数,把分母统一成正的,然后都除掉 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 ===== | ||
- | **题目大意**: | ||
- | |||
- | **题解**: | ||
- | |||
- | ===== J. Just Shuffle ===== | ||
**题目大意**: | **题目大意**: | ||
行 95: | 行 92: | ||
这类题实现上一般不需要真的把图建出来。可以以区域相邻的长度最长的区间作为区域的表示,四个方向有一个变化量的表就行。初始时把右端点为 $n$ 的先整出来,relax 跑到左端点为 $0$ 时更新一下全局的答案。 | 这类题实现上一般不需要真的把图建出来。可以以区域相邻的长度最长的区间作为区域的表示,四个方向有一个变化量的表就行。初始时把右端点为 $n$ 的先整出来,relax 跑到左端点为 $0$ 时更新一下全局的答案。 | ||
+ | |||
+ | ===== J. Just Shuffle ===== | ||
+ | |||
+ | 签到题。 | ||
+ | |||
===== K. Keyboard Free ===== | ===== K. Keyboard Free ===== | ||
- | **题目大意**: | ||
- | **题解**: | + | **题目大意**:有三个同心圆,半径分别为 $r_{1},r_{2},r_{3}$。每个圆上等概率随机一个点,问形成的三角形面积期望。 |
+ | |||
+ | **题解**:形式上是一个三重积分。有一个点可当做定点,这样变为两重,最内层积分可以积出表达式,最后一维 ''%%simpson%%'' 或切割区间求和均可。 | ||