用户工具

站点工具


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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:intrepidsword:2020-nowcoder-multi-2 [2020/07/16 23:44]
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 =====
行 41: 行 43:
 $$ $$
  
-出现的三种行列式都是整数,把分母统一成正的,然后都除掉 gcd。三元组一下最多相同数量即可。+出现的三种行列式都是整数,把分母统一成正的,然后都除掉 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%%''​ 或切割区间求和均可。
  
2020-2021/teams/intrepidsword/2020-nowcoder-multi-2.1594914272.txt.gz · 最后更改: 2020/07/16 23:44 由 chielo