2020.07.25-2020.07.31 周报

无

CF 1900-2100 杂题训练：1156C 1155D 1154F 1154G 1152D 1147C 1385E

2020.07.24 Codeforces Round #659 (Div. 1)

2020.07.25 M-SOLUTIONS Programming Contest 2020

2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)

2020.07.30 Codeforces Round #660 (Div. 2)

• AC 自动机上的神秘分析：
  • 如果插入很多串，且这些串长度和为 $S$，则将它们建成 AC 自动机后，fail 边上最多跳 $\mathcal{O}(\sqrt S)$ 次（因为只有 $\mathcal{O}(\sqrt S)$ 种不同长度的串，fail 跳一次后串长度只减不增）
• 随机二叉树的深度期望是 $O(\sqrt n)$ 的。

无

2020.07.24 Codeforces Round #659 (Div. 1)

2020.07.25 M-SOLUTIONS Programming Contest 2020

2020.07.30 Codeforces Round #660 (Div. 2)

动态凸包

bitset 加速 $01$ 矩阵乘法

无

2020.07.29 Educational Codeforces Round 92 (Rated for Div. 2)

无

CF 1385E

• 题意：给一个图，其中有一些边定向了，而一些边无向。让你给这个图定向，使之成为 DAG。
• 题解：可以发现当且仅当原图有环时无解，于是考虑如何构造解，只要新的连边不会产生环就行。DAG 的特性是拓扑排序后，所有边都代表了一个确定的偏序关系，因此给原图有向边拓扑排序后，按照拓扑序给无向边定向即可。
• 备注：是我没想到的构造。

CF 1383E

• 题意：给一个 $n \leq 10^6$ 的 $01$ 序列，你可以任意次选择一对相邻位置的数，将它们合并为一个数，值是两者中的最大值。求最后能得到本质不同的串的个数。
• 题解：一个比较详细的题解 见此。
• 备注：主要要想到将每种本质不同的串唯一对应到原串中的一个操作上，这样才可以根据操作一一对应回本质不同的串，算是一种技巧。

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$ 的，这样我们就找到了满足条件的集合。
• 备注：将问题巧妙的转化为图论问题。

2020 Nowcoder Multi-University Training Contest 5 H - Interval

• 题意 & 题解： 点我跳转
• 备注：一种很妙的统计去重方式。