CF1923 VP 记录
AB 跳了。
C. Find B
赛时切了。
题意
如果存在一个整数数组 \(b\) 满足以下条件，则认为一个整数数组 \(a\) 是好的：
- \(|b|=|a|\)。
- \(a_i\neq b_i\)。
- \(\sum b=\sum a\)。
- \(b_i>0\)。
给定一个数组 \(c\)，\(q\) 次询问，要求判断 \(c[l,r]\) 是不是好的数组。
可以做到 \(\Theta(n+q)\) 的复杂度。
做法
考虑一种构造方案，给所有数都减一，然后给最后一个数加上减去的总和。
这样显然是可行的。
但是可能有 \(1\)，就不能减了。
所以 \(1\) 就得变成 \(2\)。
这样数字的总和可能就不够用了。
所以我们判断这种情况就好了。
所以我们的构造方案就是：把所有大于 \(1\) 的数减一，然后把所有 \(1\) 都至少加一。判断这样构造数字的总和够不够用即可，也就是区间中 \(1\) 的个数是否小于等于区间的和减去区间长度。
D. Slimes
赛时不会，跳了。
题意
有 \(n\) 个史莱姆一字排开。这些史莱姆按照从左至右的顺序编号为 \(1\) 到 \(n\)，其中第 \(i\) 个史莱姆的大小为 \(a_i\)。
每隔一秒会发生以下情况：恰好有一个 史莱姆会吃掉它的一个邻居，并且将它的大小增加被吃掉的邻居的大小。一个史莱姆只有在其大小严格大于邻居时才能吃掉这个邻居。如果没有史莱姆的大小严格大于其任意一个邻居，则该过程结束。
例如，假设 \(n = 5\)，\(a = [2, 2, 3, 1, 4]\)。过程可能如下进行：
首先，第 \(3\) 个史莱姆吃掉第 \(2\) 个史莱姆。第 \(3\) 个史莱姆的大小变为 \(5\)，第 \(2\) 个史莱姆被吃掉。
接着，第 \(3\) 个史莱姆吃掉第 \(1\) 个史莱姆（由于第 \(2\) 个史莱姆已被吃掉，它们相邻）。第 \(3\) 个史莱姆的大小变为 \(7\)，第 \(1\) 个史莱姆被吃掉。
然后，第 \(5\) 个史莱姆吃掉第 \(4\) 个史莱姆。第 \(5\) 个史莱姆的大小变为 \(5\)，第 \(4\) 个史莱姆被吃掉。
最后，第 \(3\) 个史莱姆吃掉第 \(5\) 个史莱姆（因为第 \(4\) 个史莱姆已经被吃掉，它们相邻）。第 \(3\) 个史莱姆的大小变为 \(12\)，第 \(5\) 个史莱姆被吃掉。
对于每个史莱姆，计算在所有可能的过程演变中，该史莱姆被另一个史莱姆吃掉所需的最少秒数，如果不可能被吃掉，则报告“不可能”。