B. Find The Array
题意：
给定一个长度为
n
n
n 的序列
a
a
a，
a
i
<
=
1
0
9
a_i<=10^9
ai<=109，设和为
S
S
S
定义一个美丽序列
b
b
b
- 1 < = b i < = 1 0 9 1<=b_i<=10^9 1<=bi<=109
- 对于每一个相邻的 b i , b i + 1 b_i,b_{i+1} bi,bi+1 满足 b i ∣ b i + 1 b_i|b_{i+1} bi∣bi+1 或者 b i + 1 ∣ b i b_{i+1}|b_i bi+1∣bi
- 2 ∗ ∑ i = 1 n ∣ a i − b i ∣ < = S 2*\sum_{i=1}^n|a_i-b_i|<=S 2∗∑i=1n∣ai−bi∣<=S
输出任意一个美丽序列
b
b
b
思路：
大佬的奇妙题解
构造一个
2
2
2 的幂的序列
b
b
b 即可满足条件
2
2
2
第三个性质可以转化为这样一个充分条件
∣
a
i
−
2
k
∣
<
=
a
i
2
(
1
<
=
i
<
=
n
)
|a_i-2^k|<=\frac{a_i}{2} \ (1<=i<=n)
∣ai−2k∣<=2ai (1<=i<=n)，
那么如果
∣
x
−
2
k
∣
<
=
x
2
|x-2^k|<=\frac{x}{2}
∣x−2k∣<=2x 对于所有的
x
x
x 都能找到对应的
k
k
k 满足不等式即可构造
证明不会
std：
把序列
n
n
n 按照奇偶性分成两堆，然后缺少的位置放
1
1
1
1
,
a
2
,
1
,
a
4
.
.
.
1,a_2,1,a_4...
1,a2,1,a4...
a
1
,
1
,
a
3
,
1...
a_1,1,a_3,1...
a1,1,a3,1...
这样构造的两个奇偶相间的序列必然有一个满足限制