[ABC151-B]实现目标

题意

成绩是不超过$k$的整数，给定前$n-1$门课程的成绩，计算最后一门课最少考多少分才能让整体达到平均分$m$。

解法

直接算总分即可。平均分达到$m$，就意味着总分达到$n \times m$，那么就算一下前$n-1$门课的总成绩与这个数字还差多少。

---

[ABC151-C]欢迎来到AtCoder

题意

求出获得过 AC 的题目数量和罚分数量。罚分数量指对于获得过 AC 的题目，在第一次 AC 之前的 WA 数量总和。

• 多次AC不累加
• 如果没有过这道题就不算罚分
• 只有第一次AC之前的WA才算罚分，之后的不算

解法

• 创建两个数组，分别记录每个题WA的数量以及是否AC
• 如果当前是WA，并且这道题没有AC，则这道题WA的数量加一
• 如果当前是AC，并且这道题没有AC，总通过数加一，罚分加上当前题的WA数量，标记当前题目已经AC

---

[ABC151-D]迷宫大师

题意

给定一个矩阵，有些点可以走有些不可以走。找到任意两点最短距离的最大值。

解法

BFS模板题。直接枚举每个能走的点，到其他点的最短距离，再取一个最大值即可。

---

[ABC099-D]好网格

题意

给你一个$n \times n$的矩阵，$C(i,j)$为矩阵第$i$行第$j$列的初始颜色，给你一个$c \times c$的矩阵$D(i,j)$表示第$i$种颜色变为第$j$种颜色所花费的代价，当且仅当$i = j$时代价为0。

在$C$矩阵中，如果满足横坐标$i$加纵坐标$j$的和，除以三余数相同的方块颜色相同，余数不同的方块颜色不同，就是一个好矩阵。问我们如何花费最小代价使这个矩阵变为一个好矩阵。

解法

直接暴力枚举。

记录余数为$p(p=0,1,2)$的点中，颜色为$x$的有多少个。然后三重循环，枚举每种余数，将所有颜色换为一种统一颜色得代价。

---

[ABC107-D]中位数

题意

一个长度为 $M$ 的序列的中位数为这个序列从小到大排序后第 $\lfloor \frac{M}{2} \rfloor + 1$ 个数。将这个序列的所有子段的中位数放入一个序列中，求这个序列的中位数。

解法

如果$x$是一个序列的中位数，换句话讲就是这个数列中大于$x$的数字有$\frac{2}{n}$个。

对于每个$x$，大于$x$的数的个数显然是对于$x$的值大小单调递减的。

因此本题使用二分答案，二分中位数在数组排序后的下标位置。

对于单个数列，如果我们要找他的中位数，也就是要找大于$x$的数有$\frac{n}{2}$的位置。

对于区间来说也是同样道理，对于数组 $a$，求所有区间中位数大于等于 $x$ 的数量，因为区间的中位数就是新的序列中的元素。

---

[ABC107-D]中位数

为了方便的判断一个区间中位数是否大于等于$x$的，考虑辅助数组 $b$，$b_i = \begin{cases} 1 & (a_i \ge x) \\ -1 & (a_i < x) \end{cases}$，如果 $\sum_{i=l}^r b_i \ge 0$，则区间 $(l,r)$ 的中位数大于等于 $x$。

于是题目又转换为：对于数组 $b$，求出区间和非负的区间数。

使用前缀和可简化为求满足 $sum_r - sum_{l-1} \ge 0$ 的 $(l,r)$ 数量。

如果我们要枚举$l$和$r$显然会超时，因此需要想一个办法。对于每一个$sum_r$，我们只需要小于等于 $sum_r$ 的数有多少个即可。换句话说，对于每个$sum_r$，我们需要知道$b$序列中位于某个区间的数字有多少个，可以使用树状数组或者值域线段树来解决。

注意由于 $b$ 数组可能为负数，所以在树状数组统计时所有元素都要加上 $n+1$。