Educational Codeforces Round 141

D 设计的状态不太好，不然能 A。没想到能上这么多分，还是之前状态太差了吧

Source

Educational Codeforces Round 141

A - Make it Beautiful

从大到小排序即可。排序后注意特判一下：

• 若 $a_i = a_n$，也就是 $a_i$ 全部相等，则不可能做到

否则，把最小的 $a_n$ 拉到最前面即可

Code

1783 A

B - Matrix of Differences

我的构造纯属灵光一现，懒得给证明了

$$
\begin{matrix}
1 & n^2-1 & 4 & n^2 - 5 & \cdots\\
n^2 & 3 & n^2 - 4 & \cdots\\
2 & n^2-3 & \cdots\\
n^2-2&\cdots\\
\cdots
\end{matrix}
$$

交错 & 斜上的蛇形有些邪魅

实际上，二维反而不是很好考虑。首先明确答案一定是 $n^2 - 1$。我们先考虑 $1\times n$ 的构造方式：

$$1, n^2, 2, n^2-1, 3, \cdots $$

• 若 $n = 2k$，则结尾是 $2k^2, 2k^2 + 1$
• 若 $n = 2k + 1$，则结尾是 $2k^2 + 2k, 2k^2 + 2k + 2, 2k^2 + 2k + 1$

两种情况下， $n^2-1$ 种差都有了。接下来只要把一维的蛇弯曲成二维的即可。具体做法是从左向右铺第 1 排，再从右向左铺第 2 排，如此直至结束

Code

1783 B

C - Yet Another Tournament

排序的想法显然

先将 $\lbrace a\rbrace$ 从小到大排序，计算出最多的获胜次数 $x$。现在能知道我们一定至少与编号为 $x$ 的人平起平坐，若我们准备了 $a_x$ 的话，则排名会高于 $x$，可能低于 $x + 1$

考虑什么情况下会与 $x + 1$ 排名相同：当且仅当我们战胜了 $x + 1$ 且获胜次数还是最多的

因此考虑调整已有的选择策略：

• 若已经战胜了 $x + 1$，则与 $x + 1$ 排名相同，不可能再高了
• 若未战胜 $x + 1$，则尝试不准备 $a_x$ 时间（排序后的），转而为（原来的）第 $x + 1$ 人准备。若合法，则排名能与 $x + 1$ 相同，否则与 $x$ 相同

这题也可以拿二分来做

Code

1783 C

D - Different Arrays

观察数据范围，启发状态设计

令 $f(i, j)$ 表示 $2, \cdots, i - 1$ 进行操作后，$a_i = j$ 的方案数。初始有 $f(2, a_2) = 1$

对于负数下标，可以重载，也可以让原下标加上 $C = 300\times300$。虽然取 $C = \sum a_i$ 即可

最后答案即为 $\sum_{i = -C}^{C} f(n, i)$

Code

1783 D

Warnings

• 二分是个好东西
• 当然能 $O(1)$ 解决的问题还是别用二分了
• 观察数据范围可以大致猜测 DP 的状态设计
• DP 状态设计很重要。考场上 D 最终 WA on 18th case 的原因还是不太明白，部分因为状态是一拍脑袋决定的，科学性存疑