目录
团队
2020.07.23 2020-2021 BUAA ICPC Team Supplementary Training 01 (2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest) pro: 7/8/11
2020.07.20 2020牛客暑期多校训练营（第四场） pro: 7/7/10 rk: 3/1111
2020.07.18 2020牛客暑期多校训练营（第三场） pro: 8/12/12 rk: 22/1174 DONE
个人
zzh
专题
无
比赛
2020.07.21 Codeforces Round 658 (Div. 1) pro:4/6/6 rank:74/1344
题目
无
pmxm
专题
topcoder dynamic programming 补完 (200 300 400 500 600 700 800)
比赛
vp: Codeforces Round #647
题目
- 【BZOJ2310】ParkII 插头dp
- 【BZOJ 2960】 跨平面 平面图转对偶图求最小有向图
jsh
专题
无
题目
比赛
- 2020/7/19 Codeforces Round #657 (Div. 2)
problems: 3/4/7
本周推荐
zzh
Codeforces Round 658 (Div. 1) D. The Majestic Brown Tree Snake
Tags：tree, two pointers
题意：见链接
题解：见链接
Comment：很有趣的思维题
pmxm
题源：hdu 6299
Tags：括号序列，贪心
题意：给你n个只有括号的字符串，问你用哪种方法把他们相接之后可以使得构成的完美的括号最长。
观察：假设我们是不断向右拼的，如果“)“过多的话，那么拼接是不合理的(有浪费的)
策略： 考虑贪心，拼接两个串
- 左括号<右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
- 左括号>右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
- 左括号=右括号时 将数量多的排在前面。
- 其他，按照1→2→3的优先级进行排序。
Comment：括号序列思维题，需要注意到拼接的顺序
jsh
Educational Codeforces Round 90 (Rated for Div. 2) - F. Network Coverage
Tags：Hall's marriage theorem，单调队列
题意：有 $n$ 个小区，第 $i$ 个小区有 $a_i$ 个住户，网络供应商在第 $i$ 个位置上有 $b_i$ 个网口，第 $i$ 个位置的网口可以给第 $i$ 个小区和第 $((i + 1) \bmod n) + 1$ 个小区的住户用，每个口只能给一个住户用，一个住户也只需要一个口。问是不是所有住户都能上网。
题解：
Tutorial 给了一个不是用 Hall 定理做的玩法，那我给一个用 Hall 定理做的玩法。
Hall 定理简单来讲就是如果一个二分图有完美匹配，那说明左部节点集合 $L$ 的任意一个子集 $W$，记与 $W$ 相邻的右部节点的集合 $E_W$，满足 $\left|E_W\right| \ge \left|W\right|$。
考虑我们选若干段 $b_i$，这几段 $b_i$ 不相邻，即至少隔着一个 $b_i$，容易发现每一段所对应的 $a_i$ 是不相交的，也就是说只要段内是满足 Hall 定理的条件，那么若干段放在一起也是满足条件的。
因此我们需要判断各种 $b_i$ 段，所相邻的 $a_i$ 的总和到底够不够。
换句话讲，我们把序列复制一下，弄成 $2n$ 个，需要计算一下 $\max_{1 \le l < r < 2 n, r - l < n}{\left(\sum_{l \le i \le r}{a_i}\right) - \left(\sum_{l \le i < r}{b_i}\right)}$，如果这个值大于零，则说明存在有一段，对应的 $a_i$ 的和是大于 $b_i$ 的，也就是说有一段内的住户，能用到的网口数量是不够的。
另外还需要判断一下 $a_i$ 的和是不是小于或等于 $b_i$，因为上面那里没办法算上长度为 $n$ 的段。
至于那个最大值，你可以卡住 $r$ 之后，干掉 $a_r$，然后算一下最大的、右端点为 $r - 1$、长度小于 $n$ 的 $a_i - b_i$ 区间和。可以用前缀和+单调队列来实现。
Comment：这种题，实际上 Tutorial 的做法更难想，别太陷到题解的玩法里……
