2020-2021:teams:wangzai_milk:weekly14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly14 [2020/08/06 22:38] infinity37 [Zars19] |
2020-2021:teams:wangzai_milk:weekly14 [2020/08/07 14:39] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 暂无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 因为给牛客七的 $I$ 题折磨了，所以想做一下贪心题。（虽然 $I$ 好像并不是贪心，只是一开始以为是^） | ||
| + | |||
| + | [[CF贪心练习]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 牛客七、八及cf加训。 | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| 行 85: | 行 93: | ||
| **comments**:划重点，因为矩阵乘法满足分配率所以可以直接用线段树维护，注意各类数学性质。 | **comments**:划重点，因为矩阵乘法满足分配率所以可以直接用线段树维护，注意各类数学性质。 | ||
| + | ==== _wzx27 ==== | ||
| + | |||
| + | **来源**：[[https://codeforces.com/problemset/problem/1139/E|CF1139E]] | ||
| + | |||
| + | **tag**：二分图匹配 + 建图 | ||
| + | |||
| + | **概述**： | ||
| + | |||
| + | $n$ 个学生 $m$ 个社团，每个学生有一个权值 $p_i$ 和所属社团编号 $c_i$，接下来的 $d$ 天，每天第 $k_i$ 个学生会离开所在社团，同时每个社团选出一个学生组成一个集合，求他们的最大 $\text{MEX}$。 | ||
| + | |||
| + | **答案**： | ||
| + | |||
| + | 删除不好操作，离线倒过来改成加入，那么 $\text{MEX}$ 是不降的。每个社团向内部学生的权值连边，就有一个社团-权值的二分图，然后匈牙利算法刚好对应了贪心得到最大 $\text{MEX}$ 的过程，所以每次加边进来就贪心匹配更新答案。 | ||
| + | |||
| + | **comments**：每次做匹配或者网络流的题都会感觉建图很有意思，可以多积累积累。 | ||
2020-2021/teams/wangzai_milk/weekly14.1596724683.txt.gz · 最后更改: 2020/08/06 22:38 由 infinity37
