====== 2020.08.01-2020.08.07 周报 ======

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

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 =====

==== 专题 ====

暂无。

==== 题目 ====

因为给牛客七的 $I$ 题折磨了，所以想做一下贪心题。（虽然 $I$ 好像并不是贪心，只是一开始以为是^）

[[CF贪心练习]]

==== 比赛 ====

牛客七、八及cf加训。

===== 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 =====

==== 专题 ====

暂无。

==== 题目 ====

[[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**：每次做匹配或者网络流的题都会感觉建图很有意思，可以多积累积累。