2020.08.01 2020牛客暑期多校训练营（第七场） prob:4:5:10 rnk:95/1090

20200801比赛记录

2020.08.03 2020牛客暑期多校训练营（第八场） prob:3:4:11 rnk:265/685

20200803比赛记录

2020.08.06 2020.08.06codeforces加训 prob:5:6:10 rnk:8/18

20200806比赛记录

暂无。

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

CF贪心练习

牛客七、八及cf加训。

无

牛客七

codeforces加训

无

暂无。

CF2100-2800泛做1

牛客七、八及cf加训。

来源：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：神奇的转换思维。

来源：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:划重点，因为矩阵乘法满足分配率所以可以直接用线段树维护，注意各类数学性质。

来源：CF1139E

tag：二分图匹配 + 建图

概述：

$n$ 个学生 $m$ 个社团，每个学生有一个权值 $p_i$ 和所属社团编号 $c_i$，接下来的 $d$ 天，每天第 $k_i$ 个学生会离开所在社团，同时每个社团选出一个学生组成一个集合，求他们的最大 $\text{MEX}$。

答案：

删除不好操作，离线倒过来改成加入，那么 $\text{MEX}$ 是不降的。每个社团向内部学生的权值连边，就有一个社团-权值的二分图，然后匈牙利算法刚好对应了贪心得到最大 $\text{MEX}$ 的过程，所以每次加边进来就贪心匹配更新答案。

comments：每次做匹配或者网络流的题都会感觉建图很有意思，可以多积累积累。