目录
Contest Info
| 6/7 | O | O | Ø | Ø | Ø | - | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Pens and Pencils
签到。
B. Rooms and Staircases
签到。
C. The Football Season
题意：
给出\(n, p, w, d\)，求解：
\[\begin{eqnarray*}x \cdot w + y \cdot d = p \\x + y \leq n\end{eqnarray*}\]
题目保证\(d < w\)
思路：
题目保证了\(d < w\)，那么有\(y < d\)，因为如果\(y = d\)，那么相当于\(w * d\)，然后取了\(d\)个\(w\)，那么不如取\(w\)个\(d\)更优。
所以直接暴力即可。
也可以直接上\(exgcd\)，但是要讨论的东西挺多的。
代码：
exgcd代码：
D. Paint the Tree
题意：
给出\(n\)个点的树，有三种颜色，要给每个点染色，给出你每个点染某种颜色的代价。
染色方案要满足不存在任意一个三元组\((x, y, z)\)使得\(x, y\)有边相连，\(y, z\)有边相连，并且\(x, y, z\)有任意两个颜色相同。
求合法方案的最小代价。
思路：
考虑只有一条链的时候才存在方案，并且考虑在链上的话，前两个点的颜色确定了，那么整条链的颜色都确定了。
直接暴力枚举然后判断即可。
代码：
思路二：
考虑\(f[i][j][k]\)表示当前点为\(i\)，前一个点的颜色为\(j\)，当前点颜色为\(k\)的最小花费，然后转移即可。
但是输出方案要维护一个前驱或者直接确定了最后两个暴力推上去。
但是不能通过判断\(dp\)值来找前驱，这样可能导致染色方案不合法，但是\(dp\)值可能是相同的
E. Minimizing Difference
题意：
给出\(n\)个数\(a_i\)，每次可以对一个数增加\(1\)或者减少\(1\)。问操作次数不小于\(k\)的情况下，\(n\)个数中的最大值减最小值的差值最小是多少
思路：
二分答案，然后考虑合法方案一定能让最大值或者最小值固定在某个\(a_i\)，然后枚举\(a_i\)，算右界范围内的花费是否小于等于\(k\)即可。
代码：
G. Running in Pairs
题意：
要求构造两个排列\(p, q\)，使得\(sum = \sum\limits_{i = 1}^n max(p_i, q_i) \leq k\)，并且结果最大。
思路：
考虑将第一个排列顺序排放。
然后考虑第二个排列刚开始也是顺序排放的。
然后考虑交换位置视为元素左移和元素右移。
显然，元素右移不会对答案产生影响。
但是元素左移，左移几个位置它就产生多少贡献。
那么显然可以发现这个变化是连续的，直接贪心即可。
代码：