2020-2021:teams:i_dont_know_png:week_summary_13
目录
2020.07.25-2020.07.31 周报
团队训练
| 比赛时间 | 比赛名称 |
|---|---|
| 2020.07.25 | 2020 Nowcoder Multi-University Training Contest 5 |
| 2020.07.27 | 2020 Nowcoder Multi-University Training Contest 6 |
团队会议
无
个人训练 - nikkukun
专题
CF 1900-2100 杂题训练：1156C 1155D 1154F 1154G 1152D 1147C 1385E
比赛
2020.07.24 Codeforces Round #659 (Div. 1)
| 题目 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 通过 | √ | √ | ||||
| 补题 | √ |
2020.07.25 M-SOLUTIONS Programming Contest 2020
| 题目 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 通过 | √ | √ | √ | √ | √ | |
| 补题 | √ |
2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)
| 题目 | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 通过 | √ | √ | √ | √ | |||
| 补题 | √ | √ |
2020.07.30 Codeforces Round #660 (Div. 2)
| 题目 | A | B | C | D | E |
|---|---|---|---|---|---|
| 通过 | √ | √ | √ | √ | |
| 补题 | √ |
学习总结
- AC 自动机上的神秘分析：
- 如果插入很多串，且这些串长度和为 $S$，则将它们建成 AC 自动机后，fail 边上最多跳 $\mathcal{O}(\sqrt S)$ 次（因为只有 $\mathcal{O}(\sqrt S)$ 种不同长度的串，fail 跳一次后串长度只减不增）
- 随机二叉树的深度期望是 $O(\sqrt n)$ 的。
个人训练 - qxforever
专题
无
比赛
2020.07.24 Codeforces Round #659 (Div. 1)
| 题目 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 通过 | √ | √ | ||||
| 补题 |
2020.07.25 M-SOLUTIONS Programming Contest 2020
| 题目 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 通过 | √ | √ | √ | √ | √ | |
| 补题 | √ |
2020.07.30 Codeforces Round #660 (Div. 2)
| 题目 | A | B | C | D | E |
|---|---|---|---|---|---|
| 通过 | √ | √ | √ | √ | |
| 补题 | √ |
学习总结
动态凸包
bitset 加速 $01$ 矩阵乘法
个人训练 - Potassium
专题
无
比赛
2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)
| 题目 | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 通过 | √ | ||||||
| 补题 | √ |
学习总结
无
本周推荐
nikkukun
- 题意：给一个图，其中有一些边定向了，而一些边无向。让你给这个图定向，使之成为 DAG。
- 题解：可以发现当且仅当原图有环时无解，于是考虑如何构造解，只要新的连边不会产生环就行。DAG 的特性是拓扑排序后，所有边都代表了一个确定的偏序关系，因此给原图有向边拓扑排序后，按照拓扑序给无向边定向即可。
- 备注：是我没想到的构造。
- 题意：给一个 $n \leq 10^6$ 的 $01$ 序列，你可以任意次选择一对相邻位置的数，将它们合并为一个数，值是两者中的最大值。求最后能得到本质不同的串的个数。
- 题解：一个比较详细的题解 见此。
- 备注：主要要想到将每种本质不同的串唯一对应到原串中的一个操作上，这样才可以根据操作一一对应回本质不同的串，算是一种技巧。
qxforever
- 题意：给一个序列 $a$，满足 $i - n\le a_i\le i -1 $，求该序列的一个和为 $0$ 的子集。
- 题解：条件等价于 $1\le i - a_i \le n$，对每个 $i$ ，连一条 $i$ 到 $i - a_i$ 的边。每个点出度均为 $1$，这样图中一定有环。可以证明环上的和是为 $0$ 的，这样我们就找到了满足条件的集合。
- 备注：将问题巧妙的转化为图论问题。
Potassium
2020 Nowcoder Multi-University Training Contest 5 H - Interval
- 题意 & 题解： 点我跳转
- 备注：一种很妙的统计去重方式。
2020-2021/teams/i_dont_know_png/week_summary_13.txt · 最后更改: 2020/07/31 19:18 由 nikkukun
