10/12
Person trainning
题目链接
A
贪心即可。
B
C
题意
消消乐，$x+x=2x$，问消光至少要加几个
题解
除掉 $gcd$ 以后都是 $2$ 的幂，贪心从小到大合并，优先队列维护这个过程少的就加。
D
题意
把若干个整数分解成互不相同的二元组的积。
题解
相同的数一起搞，只用暴力枚举因子到 $sqrt(n)$，剩下的和前面一半相反。
E
题意
给出一个数列，每次询问一个数的最左和最右出现位置，将这两个位置之间的数都改成这个数。
题解
- 可以用链表模拟，每次修改相当于删去一段，修改头尾指针跨过修改区间。
- 也可以 $set$ 直接 $erase$ 和 $insert$ 实现起来容易些。
F
签到
G
题意
给出一棵树上移除每一条边后形成的两个连通块的最大顶点标号对，构造这棵树
题解
H
算最少需要几块 1x1 的，然后除以 2 取上整就好了
I
签到
J
签到
K
题意
求一个数列最多可以分成几部分(不打乱顺序)，使得每部分的中位数（偶数个取小的）都大于 $m$。
题解
- 定义：$dp[i]:$ 前 $i$ 个最多可以分成及部分
- 转移：转移时显然的，预处理出 $n^2$ 个区间能否转移，暴力 $n^2$ 的 $dp$。
- 优化的解法：令 $b_j=b_{j-1}+(a_i\le m)$，对于区间 $[i,j]$ 可以转移，则有
$b_i-b_j>\left \lfloor \frac{i-j}{2} \right \rfloor$，可以用一个树状数组或者线段树优化成 $log$ 的转移。( $ kblack$ 牛逼)