公开题解_延安 20230805 模拟赛题解

T1

相信你们都查到了的原题：CF468A

签到题，考的是出题人如何写SPJ。

$1,2,3$：显然无解

$4,5$：显然有解，手工构造就行了。

1 * 2 = 2
2 * 3 = 6
6 * 4 = 24

1 + 5 = 6
2 * 6 = 12
3 * 4 = 12
12 + 12 = 24

$>5$：每次输出

n - (n-1) = 1
1 * 1 = 1

就可以使得 $n,(n-1)$ 两数字凭空消失，此时只剩 $1$ 到 $(n-2)$，可以看做 $n$ 减少了 $2$。

不断减下去，直到 $n$ 为 $4$ 或 $5$，输出构造的答案就可以了。

T2

相信你们都查到了的原题：P2224

DP，设 $f_i$ 表示左手劳累度为 $i$ 时右手劳累度最小值。

最后计算 $\max\{f_i,i\}$ 即可。

其实上面的思想有了，转移十分简单，实在推导不出来就看 luogu 题解吧。

T3

相信你们都查到了的近似题：P5656

傍一写了个十分正确的东西，但 TA 取模为啥要那么写我不知道。

exgcd 板子题，还是弱化版，建议直接上 oiwiki 搜索 exgcd。

你会发现真的非常简单，会算 $\gcd$ 的人肯定都会。

T4

相信你们都查到了的原题：P4552

t4 没想到会有那么多人写出正解（不过我觉得都是贺的，因为4个人中有3个第一次提交RE，第4个干脆直接告诉我 TA 发现了原题）。

20230805 16:26更新：

还真是原题，但我在团队题单中都没找到啊😢。

将原序列变成差分序列。

你会发现，操作无非两种：把两个数一个 $+1$，一个 $-1$ 或单独把一个数$+1$ 或 $-1$ 。目的是把下标为 $2$ 到 $n$ 的数变为 $0$。

最少次数就是差分数组中 $2$ 到 $n$ 的所有负数和与正数和（以下负数和与正数和）的最大值（证明：显然不可能更少（一次操作只能最多使得正数和 $-1$，也只能最多使得负数和 $-1$），也不用更多（只要每次挑选一个 $2$ 到 $n$ 的负数+1，挑选一个 $2$ 到 $n$ 的正数-1，然后当其中一个为 $0$ 时专心消除另一个即可））。

最后会多出 $\operatorname{abs}(负数和-正数和)$ 个运算，我们可以把其中的一些运算改成同时作用于第一个数（比如把 $-1$ 改成 $-1$ 且第一个数 $+1$），这样第一个数就多了 $\operatorname{abs}(负数和-正数和)$ 种取值，共有 $\operatorname{abs}(负数和-正数和)+1$ 种取值。