====== 2020.07.25-2020.07.31 周报 ======


===== 团队训练 =====


^  比赛时间  ^  比赛名称  ^
|  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]]  |



===== 团队会议 =====

无




===== 个人训练 - 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 ====


[[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 ====

[[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 ====


[[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 | 点我跳转]]
  * **备注**：一种很妙的统计去重方式。