Educational Codeforces Round 100 (Rated for Div. 2) B. Find The Array

题意：
给出一个a数组，现在要构造一个b数组，使得b数组相邻两个元素其中一个能整除另一个，并且a数组与b数组之差的绝对值的和*2<=a数组元素之和。

题解：
思路一：
先给出结论：小于等于x并且离x最近的2的幂次方的范围是[x/2,x]。知道这个结论，很快就能知道，只要把b[i]=离a[i]最近的2的幂次方，就一定能满足条件。
结论的正确性可以用反证法来证明。

思路二：
我们假设b[i]<=a[i],由条件可以推出a[i]-b[i]<=a[i]/2,即2*b[i]>=a[i]。那么什么数可以保证相互整除，并且乘2还能大于a[i]？根据思路一，就是离a[i]最近的2的幂次方，但是考虑到a[i]<=1e9,b[i]<=1e9,我们只需选择小于等于a[i]的数即可。

代码：

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int>pii;
const int MAXN=1e6+5;
const int mod=77797;
int a[MAXN];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int s=log2(a[i]);
            int ans=pow(2,s);
            printf("%d ",ans);
        }
        printf("\n");
    }
}
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