2020-2021:teams:wangzai_milk:weekly14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly14 [2020/08/02 18:46] zars19 创建 |
2020-2021:teams:wangzai_milk:weekly14 [2020/08/07 14:39] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| + | 2020.08.01 [[https://ac.nowcoder.com/acm/contest/5672|2020牛客暑期多校训练营（第七场）]] ''prob:4:5:10'' ''rnk:95/1090'' | ||
| + | |||
| + | [[20200801比赛记录]] | ||
| + | |||
| + | 2020.08.03 [[https://ac.nowcoder.com/acm/contest/5673|2020牛客暑期多校训练营（第八场）]] ''prob:3:4:11'' ''rnk:265/685'' | ||
| + | |||
| + | [[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 ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 暂无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | [[CF2100-2800泛做1]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 牛客七、八及cf加训。 | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| + | ==== Zars19 ==== | ||
| + | |||
| + | **来源**：[[http://codeforces.com/problemset/problem/1326/E|CF1326E - Bombs]] | ||
| + | |||
| + | **tag**：思维，线段树。 | ||
| + | |||
| + | **概述**：给出长度为 $n$ 的两个排列 $p,q$ ，按照顺序从 $1$ 到 $n$ ，把 $p_i$ 加入集合，如果位置 $i$ 有炸弹则从集合中取出一个最大值，结果是最后集合中的最大值。第 $i$ 个答案回答的是 $q_1,q_2,\ldots q_{i-1}$ 处有炸弹时的结果。 | ||
| + | |||
| + | **答案**：我们观察到答案是单调不上升的，如果答案至多为 $x$ ，我们就需要让 $x+1,x+2,\ldots,n$ 都被炸掉，条件就是对于每个位置右边大于 $x$ 的 $p_i$ 的数量都不多于右边的炸弹数量。可以线段树维护 $右面不小于当前答案的p_i的数量-右面炸弹数量$ ，如果小于等于 $ 0 $ 则减小当前答案。 | ||
| + | |||
| + | 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.1596365206.txt.gz · 最后更改: 2020/08/02 18:46 由 zars19
