2020-2021:teams:wangzai_milk:weekly14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly14 [2020/08/05 20:26] zars19 |
2020-2021:teams:wangzai_milk:weekly14 [2020/08/07 14:39] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| [[20200803比赛记录]] | [[20200803比赛记录]] | ||
| + | 2020.08.06 [[https://codeforces.com/group/azDPdoF24f/contest/290092|2020.08.06codeforces加训]] ''prob:5:6:10'' ''rnk:8/18'' | ||
| + | |||
| + | [[20200806比赛记录]] | ||
| ===== _wzx27 ===== | ===== _wzx27 ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 暂无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 因为给牛客七的 $I$ 题折磨了，所以想做一下贪心题。（虽然 $I$ 好像并不是贪心，只是一开始以为是^） | ||
| + | |||
| + | [[CF贪心练习]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 牛客七、八及cf加训。 | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 牛客七 | ||
| + | | [[20200801比赛记录#h_-_dividing| H - Dividing]] | | ||
| + | codeforces加训 | ||
| + | |||
| + | | [[20200806比赛记录#a_-_hacker_cups_and_balls | A - Hacker Cups and Balls]] | [[20200806比赛记录#j_-_zero_game | J - Zero Game]] | | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 无 | ||
| ===== Zars19 ===== | ===== Zars19 ===== | ||
| 行 55: | 行 71: | ||
| comments：神奇的转换思维。 | comments：神奇的转换思维。 | ||
| + | ==== Infinity37 ==== | ||
| + | |||
| + | **来源**：codeforces719E | ||
| + | |||
| + | **tag**:线段树，矩阵乘法，数学 | ||
| + | |||
| + | **概述**： | ||
| + | |||
| + | 给出序列a1~an，有两种操作 | ||
| + | |||
| + | 操作1：区间l,r+x | ||
| + | |||
| + | 操作2：对区间l，r中的数对应的fib数列第ai项求和。 | ||
| + | |||
| + | **答案**： | ||
| + | |||
| + | 由于矩阵乘法满足分配律，于是我们可以维护一颗线段树，每个节点是一个矩阵，如果区间+x，就代表着区间向前递推x步，换句话说就是乘以了fib数列转移矩阵的k次幂。 | ||
| + | |||
| + | 我们维护线段树push_up使左区间和右区间矩阵相加，将lazy设为fib数列转移矩阵，每次区间+x就直接使$lazy*fib^k$ | ||
| + | |||
| + | **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.1596630373.txt.gz · 最后更改: 2020/08/05 20:26 由 zars19
