前言
这种带模拟的构造题最讨厌了 qwq
https://codeforces.com/problemset/problem/1981/C
题意：
对于给定的序列a，要求更改其中值为-1的元素，得到的序列b满足$either \ bi=⌊\frac{b{i + 1}}{2}⌋\ or\ b{i + 1}=⌊\frac{b_i}{2}⌋ \ holds$
输出任意满足要求的b即可。
思路
其实直接考虑并不好做，因为构造中不只涉及乘2除2，向下取整会导致序列中出现各种数字
联想到完全二叉树的性质，用数组表示一颗完全二叉树时，结点x的左儿子为x >> 1,右儿子为x >> 1 | 1,父亲结点为x << 1,所以可以认为序列b中相邻的元素在一颗完全二叉树上也相邻。
将a中值不为-1的元素抽出来存进vector中，先处理开头和结尾的-1，对于vec中相邻的每两个数：
- 假设这两个数分别为x，y，分别在位置l和位置r，求出LCA(x, y)（x,y值域比较大，但是操作次数比较少，可以暴力求，而且也不能预处理对数，需要使用
__lg）
- 从x到y的序列可以看作这颗完全二叉树上x到y的一条路径（不一定为简单路径），我们可以求出x到y的简单路径，再重复走过某一小段，凑出x到y长度为
r-l+1的路径（可能不存在）
- 我个人认为在修改数组时判断路径是否存在比较麻烦，所以在修改完整个数组后O(n)的判断序列b合法性
细节
在求路径时我使用了双指针，但实际提交时由于没有判断边界/边界判断错误，导致了RE/WA
由于1 >> 1 == 0，所以在凑长度时应选用某个点x，在序列中反复添加x << 1,x……
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, a[N];
void solve() {
cin >> n;
vector<int> pos;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
if(a[i] != -1) pos.push_back(i);
}
if(pos.size() == 0) {
for(int i = 1; i <= n; ++i) {
cout << 1 + (i & 1) << " \n"[i == n];
}
return;
}
for(int i = 1; i < pos[0]; ++i) {
if(pos[0] - i & 1) a[i] = a[pos[0]] << 1;
else a[i] = a[pos[0]];
}
for(int i = pos.back() + 1; i <= n; ++i) {
if(i - pos.back() & 1) a[i] = a[pos.back()] << 1;
else a[i] = a[pos.back()];
}
for(int i = 0; i < pos.size() - 1; ++i) {
int l = pos[i], r = pos[i + 1];
int x = a[l], y = a[r];
while(__lg(x) > __lg(y)) {
x >>= 1;
a[++l] = x;
if(l > r) {
cout << -1 << endl;
return;
}
}
while(__lg(y) > __lg(x)) {
y >>= 1;
a[--r] = y;
if(r < l) {
cout << -1 << endl;
return;
}
}
while(x != y) {
if(l > r) {
cout << -1 << endl;
return;
}
a[++l] = x >> 1;
a[--r] = y >> 1;
x >>= 1;
y >>= 1;
}
if(l > r) {
cout << -1 << endl;
return;
}
for(int j = l + 1; j < r; ++j) {
if(j - l & 1) a[j] = a[l] << 1;
else a[j] = a[l];
}
}
for(int i = 1; i < n; ++i) {
if(a[i] != a[i + 1] / 2 && a[i] / 2 != a[i + 1]) {
cout << -1 << endl;
return;
}
}
for(int i = 1; i <= n; ++i) {
cout << a[i] << " \n"[i == n];
}
}
int main() {
int t; cin >> t;
while(t--) {
solve();
}
}
|
后记
如果我有错，请惩罚我，而不是告诉我在第1701个test case出现错误
