====== 2020.07.11-2020.07.17 周报 ======


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

^  比赛时间  ^  比赛名称  ^
|  2020.07.10  |  [[JagiellonianU2020 | 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest]]  |
|  2020.07.12  |  [[multi2020-nowcoder-1 | 2020 Nowcoder Multi-University Training Contest 1]]  |
|  2020.07.13  |  [[multi2020-nowcoder-2 | 2020 Nowcoder Multi-University Training Contest 2]]  |



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

无




===== 个人训练 - nikkukun =====

==== 专题 ====

树专题

==== 比赛 ====

=== 2020.07.11 AIsing Programming Contest 2020 ===

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √   |  √  |     |     |
|  补题  |     |     |      |     |     |     |

==== 题目 ====

无





===== 个人训练 - qxforever =====


==== 专题 ====

无
==== 比赛 ====


=== 2020.07.11 AIsing Programming Contest 2020 ===

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √   |  √  |  √  |     |
|  补题  |     |     |      |     |     |     |

=== 2020.07.11 Codeforces Round #655 (Div. 2) ===

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √   |  √  |     |     |
|  补题  |     |     |      |     |  √  |     |


==== 题目 ====

无


===== 个人训练 - Potassium =====
本周主要进行复健

==== 专题 ====

无

==== 比赛 ====

无
==== 题目 ====

无










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


==== nikkukun ====

To argue, or not to argue

    * 标签：容斥、插头 DP
    * 题意 & 题解：[[jagiellonianu2020#k_-_to_argue_or_not_to_argue | 点我跳转]]
    * 推荐理由：当做是复习了容斥和插头 DP 的写法。

==== qxforever ====

[[https://codeforces.com/contest/1372/problem/E | CF1372E Omkar and Last Floor]]

  * 题意：给一个 $n\times m$ 的网格，每个位置能填 $0$ 或 $1$ 。有如下一些限制，第 $i$ 行从 $j$ 到 $k$ 的和不能超过 $1$ 。设第 $c$ 列的和为 $q_c$ ，求 $\max \sum_{i = c}^m q_c^2$ 
  * 题解：区间 dp ，设 $dp_{l,r}$ 为所有限制都在 $[l,r]$ 范围内的最优答案。由于求的是平方的和，那么把一列都填上 $1$ 是最优的。于是转移是 $dp_{l,r} =\max(dp_{l,k-1},+dk_{k+1,r}+[l,r]区间内包含 k 的限制^2)$ 。复杂度是 $O(n\times m^3) $ 。
  * 推荐理由：比较巧妙的状态设计。
==== Potassium ====

[[https://codeforces.com/problemset/problem/763/B | CF763B Timofey and rectangles]]

  * 题意：给 $5 \times 10^5$ 个奇数边长矩形，相邻矩形不能同色，要求将所有矩形染为 $[0,3]$ 中的颜色，求方案。
  * 题解：朴素的建图不容易进行染色，故考虑奇技淫巧。观察到矩形边长是奇数，于是考虑一个田字格染四种不同颜色，由于奇数边长这题就做完了。