===== 团队 =====

2020.07.23 [[ru-winter-camp-2015-saratov-su|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-nowcoder-multi-4|2020牛客暑期多校训练营（第四场）]] ''pro: 7/7/10'' ''rk: 3/1111''

2020.07.18 [[2020-nowcoder-multi-3|2020牛客暑期多校训练营（第三场）]] ''pro: 8/12/12'' ''rk: 22/1174'' **DONE**

===== 个人 =====

==== zzh ====

=== 专题 ===

无

=== 比赛 ===

2020.07.21 [[.:zhongzihao:Codeforces_Round_658_Div._1|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 ====

=== 专题 ===

无

=== 题目 ===

  * [[https://codeforces.com/problemset/problem/1373/F|Educational Codeforces Round 90 (Rated for Div. 2) - F. Network Coverage]]

=== 比赛 ===

  * 2020/7/18 [[https://clist.by/standings/tco20-parallel-2b-20874768/|TCO20 Parallel 2B]] ''problems: 0/2/3'' ''rank: 68/143''
  * 2020/7/19 [[https://clist.by/standings/tco20-sa-parallel-20890259/|TCO20 SA Parallel]] ''problems: 3/3/3'' ''rank: 4/32''
  * 2020/7/19 [[https://codeforces.com/contest/1379|Codeforces Round #657 (Div. 2)]] ''problems: 3/4/7''
  * 2020/7/21 [[https://codeforces.com/contest/1381|Codeforces Round #658 (Div. 1)]] ''problems: 3/4/6'' ''rank: 862/1344''

===== 本周推荐 =====

==== zzh ====

[[.:zhongzihao:Codeforces_Round_658_Div._1#d_the_majestic_brown_tree_snake|Codeforces Round 658 (Div. 1) D. The Majestic Brown Tree Snake]]

**Tags**：tree, two pointers

**题意**：见链接

**题解**：见链接

**Comment**：很有趣的思维题

==== pmxm ====

**题源**：[[http://acm.hdu.edu.cn/showproblem.php?pid=6299|hdu 6299]]

**Tags**：括号序列，贪心

**题意**：给你n个只有括号的字符串，问你用哪种方法把他们相接之后可以使得构成的完美的括号最长。

**观察**：假设我们是不断向右拼的，如果")"过多的话，那么拼接是不合理的(有浪费的)

**策略**： 考虑贪心，拼接两个串
  - 左括号<右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
  - 左括号>右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
  - 左括号=右括号时 将数量多的排在前面。
  - 其他，按照1->2->3的优先级进行排序。

**Comment**：括号序列思维题，需要注意到拼接的顺序 
==== jsh ====

=== Educational Codeforces Round 90 (Rated for Div. 2) - F. Network Coverage ===

[[https://codeforces.com/problemset/problem/1373/F|题目链接]]

**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 的做法更难想，别太陷到题解的玩法里……