2020-2021:teams:i_dont_know_png:week_summary_13
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_13 [2020/07/31 15:22] qxforever [学习总结] |
2020-2021:teams:i_dont_know_png:week_summary_13 [2020/07/31 19:18] (当前版本) nikkukun add contest |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ~~NOTOC~~ | ||
| - | |||
| ====== 2020.07.25-2020.07.31 周报 ====== | ====== 2020.07.25-2020.07.31 周报 ====== | ||
| 行 7: | 行 5: | ||
| + | ^ 比赛时间 ^ 比赛名称 ^ | ||
| + | | 2020.07.25 | [[multi2020-nowcoder-5 | 2020 Nowcoder Multi-University Training Contest 5]] | | ||
| + | | 2020.07.27 | [[multi2020-nowcoder-6 | 2020 Nowcoder Multi-University Training Contest 6]] | | ||
| - | ===== 团队会议 ===== | ||
| + | ===== 团队会议 ===== | ||
| + | |||
| + | 无 | ||
| 行 19: | 行 22: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | CF 1900-2100 杂题训练：1156C 1155D 1154F 1154G 1152D 1147C 1385E | ||
| + | |||
| 行 24: | 行 30: | ||
| - | === 2020.07.24 Codeforces Round #659 (Div. 1) === | + | **2020.07.24 Codeforces Round #659 (Div. 1)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| 行 30: | 行 36: | ||
| | 补题 | | | | | √ | | | | 补题 | | | | | √ | | | ||
| - | === 2020.07.25 M-SOLUTIONS Programming Contest 2020 === | + | **2020.07.25 M-SOLUTIONS Programming Contest 2020** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| 行 36: | 行 42: | ||
| | 补题 | | | | | √ | | | | 补题 | | | | | √ | | | ||
| - | === 2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2) === | + | **2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ | ||
| 行 42: | 行 48: | ||
| | 补题 | | | | √ | | √ | | | | 补题 | | | | √ | | √ | | | ||
| + | **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)$ 的。 | ||
| + | |||
| + | |||
| 行 56: | 行 73: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === 2020.07.24 Codeforces Round #659 (Div. 1) === | + | **2020.07.24 Codeforces Round #659 (Div. 1)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| 行 65: | 行 83: | ||
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| - | === 2020.07.25 M-SOLUTIONS Programming Contest 2020 === | + | **2020.07.25 M-SOLUTIONS Programming Contest 2020** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| | 通过 | √ | √ | √ | √ | | √ | | | 通过 | √ | √ | √ | √ | | √ | | ||
| | 补题 | | | | | √ | | | | 补题 | | | | | √ | | | ||
| + | |||
| + | **2020.07.30 Codeforces Round #660 (Div. 2)** | ||
| + | |||
| + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ | ||
| + | | 通过 | √ | √ | √ | √ | | | ||
| + | | 补题 | | | | | √ | | ||
| + | |||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 动态凸包 | ||
| + | ''bitset'' 加速 $01$ 矩阵乘法 | ||
| 行 84: | 行 111: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === 2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2) === | + | **2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ | ||
| 行 97: | 行 125: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| - | 动态凸包 | + | 无 |
| - | + | ||
| - | ''bitset'' 加速 $01$ 矩阵乘法 | + | |
| 行 109: | 行 135: | ||
| ==== nikkukun ==== | ==== nikkukun ==== | ||
| - | [[https://codeforces.com/gym/102576/problem/D | 这是题目]] | ||
| - | * **题意**： | + | [[https://codeforces.com/contest/1385/problem/E | CF 1385E]] |
| - | * **题解**： | + | |
| - | * **备注**： | + | * **题意**：给一个图，其中有一些边定向了，而一些边无向。让你给这个图定向，使之成为 DAG。 |
| + | * **题解**：可以发现当且仅当原图有环时无解，于是考虑如何构造解，只要新的连边不会产生环就行。DAG 的特性是拓扑排序后，所有边都代表了一个确定的偏序关系，因此给原图有向边拓扑排序后，按照拓扑序给无向边定向即可。 | ||
| + | * **备注**：是我没想到的构造。 | ||
| + | |||
| + | [[https://codeforces.com/contest/1383/problem/E | CF 1383E]] | ||
| + | |||
| + | * **题意**：给一个 $n \leq 10^6$ 的 $01$ 序列，你可以任意次选择一对相邻位置的数，将它们合并为一个数，值是两者中的最大值。求最后能得到本质不同的串的个数。 | ||
| + | * **题解**：一个比较详细的题解 [[https://www.cnblogs.com/Patt/p/13394766.html | 见此]]。 | ||
| + | * **备注**：主要要想到将每种本质不同的串唯一对应到原串中的一个操作上，这样才可以根据操作一一对应回本质不同的串，算是一种技巧。 | ||
| + | |||
| + | |||
| ==== qxforever ==== | ==== qxforever ==== | ||
| - | [[https://codeforces.com/gym/102576/problem/D | 这是题目]] | + | [[https://codeforces.com/contest/1270/problem/G | CF 1270G]] |
| - | * **题意**： | + | * **题意**：给一个序列 $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 ==== | ==== Potassium ==== | ||
| - | [[https://codeforces.com/gym/102576/problem/D | 这是题目]] | ||
| - | * **题意**： | + | [[https://ac.nowcoder.com/acm/problem/209992 | 2020 Nowcoder Multi-University Training Contest 5 H - Interval]] |
| - | * **题解**： | + | |
| - | * **备注**： | + | * **题意 & 题解**：[[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:multi2020-nowcoder-5#h_-_interval | 点我跳转]] |
| + | * **备注**：一种很妙的统计去重方式。 | ||
2020-2021/teams/i_dont_know_png/week_summary_13.1596180158.txt.gz · 最后更改: 2020/07/31 15:22 由 qxforever
