Contest Info
[Practice Link](https://codeforces.com/contest/1250)
| 9/14 | O | O | O | - | O | O | - | O | - | O | - | O | - | O |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Berstagram
题意：
给出\(n\)个数，刚开始第\(i\)个数在第\(i\)个位置，有\(m\)次操作，将标号为\(a_i\)的数和它前面那个数交换位置，如果它已经在最前面了，那么不操作。
最后输出\(n\)行，表示每个数所待过的位置的下标的最小值和最大值
思路：
每次交换只会影响两个数，暴力即可。
代码：
C. Trip to Saint Petersburg
题意：
给出\(n\)个工作，和一个参数\(k\)。
每个工作的工作时间为\([l_i, r_i]\)，可以获得\(p_i\)的利润，并且工作随便选，工作时间可以重叠。
唯一的代价就是所选择的工作中的最小的\(L = l_i\)，最大的\(R = r_i\)，代价就是\(k \cdot (R - L + 1)\)。
问所能获得的最大利润。
思路：
枚举右端点\(R\)，然后线段树维护左端点的贡献，每次要将\(r_i = R\)的工作的贡献加给左端点在\([1, l_i]\)范围内的。
然后查询区间最值即可。
代码：
E. The Coronation
题意：
给出\(n\)个\(01\)串，每个\(01\)串可以\(reverse\)，求最少的\(reverse\)次数，使得任意两个串的有大于等于\(k\)个位置的字符是相同的。
代码：
F. Data Center
题意：
给出一个矩形的面积\(n\)，求所有合法矩形中的最小周长。
思路：
暴力分解。
代码：
G. Discarding Game
题意：
有两个人玩游戏，刚开始两个人的分数都是\(0\)，每一轮，\(A\)的分数会加上\(a_i\)，\(B\)的分数会加上\(b_i\)，如果某个人的分数大于等于\(k\)，它就输了，如果两个人都大于等于\(k\)，两个人都输了。
如果最后过完了\(n\)轮，两人的分数都小于\(k\)，那么是平局。
赢的情况是其中某个人输了，那么另一个人就赢了。
现在\(A\)有超能力，它可以在每一轮加分结束后按下一个按钮，假定此时\(A\)的分数为\(x\)，\(B\)的分数为\(y\), \(A\)的分数变成\(max(0, x - y)\)，\(B\)的分数变成\(max(0, y - x)\)。
现在求最少次数使得\(A\)赢了。
H. Happy Birthday
题意：
给出\([0, 9]\)每种数字的个数，问最小的不能被拼出来的数是多少。
代码：
J. The Parade
代码：
L. Divide The Students
题意：
有三类人，每类人有\(a, b, c\)个。
现在要将这三类人分成三组，使得第一类和第三类人不能在同一组，并且使得所有组的最大人数最少。
思路：
令\(a > c\)，那么将\(c\)单独放在一组，将\(a\)均分成两组，然后\(b\)每次选一个人数最少的组放。
代码：
M. SmartGarden
题意：
给出一个\(n \cdot n\)的矩形，其中对角线和对角线下面一条线是墙，其他地方是蔬菜，类似这样：
现在每次可以选择若干个行，若干个列，将这些行列相交的地方浇上水，次数最多为\(50\)次，并且不能浇到墙，并且每棵蔬菜都要被浇到。
N. Wires
题意：
给出\(n\)条边，点的标号在\([1, 10^9]\)，现在可以修改某条边的某个端点，使得这\(n\)条边所构成的图是一个连通块。
使得修改次数最少。
思路：
显然最少修改次数为连通块个数 - 1。
随便选取一个连通块出来，让其他连通块都连向这个连通块。
然后考虑每个连通块里：
- 如果有\(1\)度顶点，直接改掉这个\(1\)度顶点
- 那么没有\(1\)度顶点，那么必然有环，随便改掉环上的一条边即可
代码：