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

差别

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

到此差别页面的链接

--- 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)$。
-**题解**：
+**题解**：一个串 $s$ 可能会有多个 ''%%border%%''，考虑如何不重复计算贡献。容易想到对于 ''%%border%%'' $s$，其贡献为 $|s|^{2}-|b_{s}|^{2}$，其中 $b_{s}$ 为 $s$ 的最长 ''%%border%%''。而最长 ''%%border%%'' 就是 ''%%KMP%%'' 的过程中的 ''%%fail%%'' 数组。QAQ
+最终做法为，求出所有前缀、后缀的 ''%%hash%%'' 值，并适当统计贡献。
 ===== B. Boundary =====
@@ 行 43: / 行 45: @@
 出现的三种行列式都是整数，把分母统一成正的，然后都除掉 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 =====
-**题目大意**：
-**题解**：
-===== J. Just Shuffle =====
 **题目大意**：
@@ 行 95: / 行 92: @@
 这类题实现上一般不需要真的把图建出来。可以以区域相邻的长度最长的区间作为区域的表示，四个方向有一个变化量的表就行。初始时把右端点为 $n$ 的先整出来，relax 跑到左端点为 $0$ 时更新一下全局的答案。
+===== J. Just Shuffle =====
+签到题。
 ===== K. Keyboard Free =====
-**题目大意**：
-**题解**：
+**题目大意**：有三个同心圆，半径分别为 $r_{1},r_{2},r_{3}$。每个圆上等概率随机一个点，问形成的三角形面积期望。
+**题解**：形式上是一个三重积分。有一个点可当做定点，这样变为两重，最内层积分可以积出表达式，最后一维 ''%%simpson%%'' 或切割区间求和均可。

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