CF1851D Prefix Permutation Sums 题解

Elairin176 · 2023-07-28 06:51:58 · 题解

传送门
思路好想，但是代码量不少。

题意

我们定义“前缀和排列”为：如果 a 为一个长度为 n 的排列，那么如果数列 b 满足 \forall i\in[1,n] 有 b_i=\sum\limits^i_{j=1}a_j，那么我们说 b 是 a 的“前缀和排列”。
现在有一个长度为 n-1 的数列 a，a 是一个前缀和数列且丢失了其中一项。求每次的 a 能否通过补全成为完整的“前缀和排列”。

解法

我们定义 a 的差分数组为 b。
我们易知，一个普通的“前缀和排列”的差分数组必然就是这个排列。
所以我们建一个桶来记录 b 中所有元素是否出现过。这扫一遍即可（下面设扫到 i），但是有一些特殊情况：

• 如果 b_i 已经出现过，那么这个 b_i 应为两个数的和，把它记录下来。
• 如果 b_i 不属于 [1,n] 的范围，那么它也是两个数的和，也把它记录下来。
• 如果记录了多于一个数，那么就不能通过补全得到“前缀和排列”。

那么我们最后只要判断记录的数字是否等于丢下的两个数字即可。这里有特殊情况：没有记录的数字。这种情况我们需要判断桶里的数是否是正好 n-1 个，如果是，就是正确的，反之为否。
时间复杂度为 O(N),N=\sum\limits^t_{i=1}n_i，可以通过。
CODE