CF2013

A

显然每次操作可以放 \(\min(x,y)\) 个水果，那么答案就是 \(\lceil\frac{n}{\min(x,y)}\rceil\)。

B

我们考虑什么情况剩下的最大。不难发现，我们可以将 \(a_1~\sim a_{n-2}\) 都与 \(a_{n-1}\) 进行操作，然后将 \(a_{n-1}\) 与 \(a_{n}\) 操作，这样的答案就是最大的。

C

考虑找到最长的连续 \(0\) 段，然后将这段往左和往右尝试扩展，直到两边都不可以扩展就是最终的答案了。

D

首先我们观察一下样例，我们发现如果一个序列 \(a\) 可以变成另一个序列 \(b\)，那么当且仅当：

• 对于任意 \(1\le i\le n\)，\(\displaystyle{(\sum_{j=1}^{i}a_j-b_j)\ge 0}\)

• \(\displaystyle{(\sum_{j=1}^{n}a_j-b_j)=0}\)

然后我们感性理解一下 \(b\) 的最小值最大时多少，容易发现如果将所有 \(a_i\) 都减去 \(x\)，\(a_i\) 的前缀和都 \(\ge 0\)，那么这个 \(x\) 就是合法的，那么这样就可以很容易地算出 \(b\) 的最小值，同理我们也可以容易地算出 \(b\) 的最大值。

E

我们记 \(\gcd(a_1,a_2,\ldots,a_n)=d\)，再记 \(b_i=\gcd(a_1,a_2,\ldots,a_i)\)，那么显然地 \(b_i\) 不同值的个数是 \(\mathcal O(\log V)\) 的，然后我们发现如果存在 \(b_i=b_{i+1}\) 且 \(b_i\neq d\) 肯定不优，所以 \(b_i\neq d\) 的 \(i\) 也只有 \(\mathcal O(\log V)\) 个。

那么考虑以下的暴力做法。我们枚举 \(a_1\)，然后找 \(\mathcal O(\log V)\) 次 \(a_i\)，每次也就是找到一个 \(a_x\) 使得 \(\gcd(a_1,a_2,\ldots,a_{i-1},a_x)\) 最小，我们又发现 \(a_x\) 选择了 \(a_1\) 到 \(a_{i-1}\) 肯定不优，所以我们就是在整个 \(a\) 里面找 \(a_x\)。

那么怎么优化呢？我们记 \(cnt_i\) 表示 \(i\) 在 \(a\) 中的出现次数，\(\displaystyle{f_i=\sum_{i|j}cnt_j}\)，那么我们做一个差分就可以得到 \(\gcd=x\) 的个数，然后就可以求出最小的 \(\gcd\) 了。