题解：CF1981C（Turtle and an Incomplete Sequence）

题解：CF1981C（Turtle and an Incomplete Sequence）

Part 1：题意理解

• 地址链接：CF、洛谷。
• 题面翻译：给定一个长度为 $n$ 的序列 $a$，其中有一些元素未知，用 $-1$ 表示，现在要将数组 $a$ 补充完整，即将 $a$ 中所有的 $-1$ 替换成一个小于等于 $10^9$ 的正整数，使得对于任意一个 $1\le i<n$，都有 $a_i=\lfloor \frac{a_{i+1}}{2}\rfloor$ 或者 $a_{i+1}=\lfloor \frac{a_i}{2}\rfloor$。如果存在合法的方案，输出填充后的数组，否则输出 $-1$。
• 数据范围：$n\le 2\cdot 10^5$，只能接受线性算法。

Part 2：算法分析

• 典型构造题。
• 首先特判，如果 $a$ 中所有元素都未知，那么就 $1$ 和 $2$ 交替输出。
• 由于前缀和后缀的 $-1$ 都很好处理，并且对中间没有影响，先将他们特别处理。具体的，以前缀为例，假设 $a_1$ 到 $a_i$ 均为 $-1$，且 $a_{i+1}$ 不是 $-1$，是已知的，那么将 $1$ 到 $i$ 中所有与 $i+1$ 奇偶性相同的赋值为 $a_{i+1}$，其余赋值为 $a_{i+1}\times 2$。
• 对于中间，每个连续的 $-1$ 组成的段是独立的，可分别处理。假设现在处理的是 $a_u$ 到 $a_v$ 这个段，我们的目标就是通过 $v-u+2$ 次乘 $2$、除以 $2$ 的操作让 $a_{u-1}$ 变成 $a_{v+1}$。也就是说 $a_{u-1}\ne -1$，$a_u$ 到 $a_v$ 都是 $-1$，$a_{v+1}\ne -1$。根据题面分析，其实说 $a_i$ 和 $a_{i+1}$ 满足条件，实际上就是说它们在由 $1$ 到 $n$ 编号的节点组成的完全二叉树上是相邻的。因此，$a_{u-1}$ 通过一些操作变成 $a_{v+1}$，就相当于在这棵完全二叉树上找到一个从 $a_{u-1}$ 走到 $a_{v+1}$ 的长度等于 $v-u+2$ 的路径。
• 如何找这条路径呢？显然，只要找出两个节点的 LCA，按照 $a_{u-1}$ 到 LCA 再到 $a_{v+1}$ 的顺序走就能得出最短的一条路径。至于怎么使它加长，就可以直接在某个点上，比如 LCA，不断地乘 $2$、除以 $2$ 就可以了。当然，如果奇偶性不对，或者最短的长度也不够，自然不行。
• 但是如何实现呢？有两个指针分别指向这段未知的元素内最左侧、最右侧仍旧没有填充的位置。每一次，如果某一侧最后一个已经填充完成的数较大，就让对应侧的指针对应的元素赋值为它除以 $2$。如果两侧相等，就让其中一个能除以二就除以二；不能除以二，也就是说对应的已经处理完的是 $1$，就乘二。最后判断两个方向最后一个赋值的是否满足条件即可。

Part 3：代码实现

#include <bits/stdc++.h>
#define N 220000
using namespace std;
int t, n, a[N];
int s, lst, u, v;
bool flag;
int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);s = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);if (a[i] == -1) {s++;}}flag = false;for (int i = 2; i <= n; i++) {if (a[i - 1] != -1 && a[i] != -1 && a[i - 1] != a[i] / 2 && a[i] != a[i - 1] / 2) {flag = true;break;}}if (flag == true) {printf("-1\n");continue;}if (s == n) {for (int i = 1; i <= n; i++) {if (i % 2 == 0) {printf("1 ");} else {printf("2 ");}}printf("\n");} else {lst = -1;for (int i = 1; i <= n; i++) {if (a[i] != -1) {lst = i;break;}}for (int i = lst - 1; i >= 1; i--) {if (i % 2 == lst % 2) {a[i] = a[lst];} else {a[i] = a[lst] * 2;}}lst = -1;for (int i = n; i >= 1; i--) {if (a[i] != -1) {lst = i;break;}}for (int i = lst + 1; i <= n; i++) {if (i % 2 == lst % 2) {a[i] = a[lst];} else {a[i] = a[lst] * 2;}}lst = -1;flag = true;for (int i = 1; i <= n; i++) {if (a[i] == -1) {if (lst == -1) {lst = i;}if (a[i + 1] != -1) {u = lst;v = i;while (u <= v) {if (a[u - 1] > a[v + 1]) {a[u] = a[u - 1] / 2;u++;} else if (a[u - 1] < a[v + 1] ){a[v] = a[v + 1] / 2;v--;} else {if (a[u - 1] == 1) {a[u] = a[u - 1] * 2;} else {a[u] = a[u - 1] / 2;}u++;}}if (a[u] != a[v] / 2 && a[v] != a[u] / 2) {flag = false;break;}lst = -1;}}}if (flag == false) {printf("-1\n");} else {for (int i = 1; i <= n; i++) {printf("%d ", a[i]);}printf("\n");}}}return 0;
}