差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:2020.07.17-2020.07.23_周报 [2020/07/23 23:22]
prime21 [pmxm]
+++ 2020-2021:teams:intrepidsword:2020.07.17-2020.07.23_周报 [2020/07/24 16:01] (当前版本)
admin update
@@ 行 1: / 行 1: @@
 ===== 团队 =====
+.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''
+.07.20 [[2020-nowcoder-multi-4|2020牛客暑期多校训练营（第四场）]] ''pro: 7/7/10'' ''rk: 3/1111''
+.07.18 [[2020-nowcoder-multi-3|2020牛客暑期多校训练营（第三场）]] ''pro: 8/12/12'' ''rk: 22/1174'' **DONE**
 ===== 个人 =====
 ==== zzh ====
 === 专题 ===
+无
 === 比赛 ===
+.07.21 [[.:zhongzihao:Codeforces_Round_658_Div._1|Codeforces Round 658 (Div. 1)]] ''pro:4/6/6'' ''rank:74/1344''
 === 题目 ===
+无
 ==== pmxm ====
@@ 行 33: / 行 36: @@
 === 题目 ===
-【BZOJ2310】ParkII 插头dp
+  * 【BZOJ2310】ParkII 插头dp
-【BZOJ 2960】 跨平面 平面图转对偶图求最小有向图
+  * 【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''
 ===== 本周推荐 =====
@@ 行 42: / 行 60: @@
 ==== 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 ====
-题源：hdu 6299 [[http://acm.hdu.edu.cn/showproblem.php?pid=6299]]
+**题源**：[[http://acm.hdu.edu.cn/showproblem.php?pid=6299|hdu 6299]]
-题意：给你n个只有括号的字符串，问你用哪种方法把他们相接之后可以使得构成的完美的括号最长。
+**Tags**：括号序列，贪心
-观察：假设我们是不断向右拼的，如果")"过多的话，那么拼接是不合理的(有浪费的)
+**题意**：给你n个只有括号的字符串，问你用哪种方法把他们相接之后可以使得构成的完美的括号最长。
-策略： 考虑贪心，拼接两个串
+**观察**：假设我们是不断向右拼的，如果")"过多的话，那么拼接是不合理的(有浪费的)
-     -  左括号<右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
-     -  左括号>右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
+**策略**： 考虑贪心，拼接两个串
-     - 左括号=右括号时 将数量多的排在前面。
+  - 左括号<右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
-     - 其他，按照1->2->3的优先级进行排序。
+  - 左括号>右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
+  - 左括号=右括号时 将数量多的排在前面。
+  - 其他，按照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 的做法更难想，别太陷到题解的玩法里……

CVBB ACM Team

用户工具

站点工具

差别

页面工具