CF1463B-Find The Array

2020-12-23 约 572 字预计阅读 2 分钟次阅读

CF1463B-Find The Array

题目:

题目描述:

You are given an array $ [a_1, a_2, \dots, a_n] $ such that $ 1 \le a_i \le 10^9 $ . Let $ S $ be the sum of all elements of the array $ a $ .

Let’s call an array $ b $ of $ n $ integers beautiful if:

$ 1 \le b_i \le 10^9 $ for each $ i $ from $ 1 $ to $ n $ ;
for every pair of adjacent integers from the array $ (b_i, b_{i + 1}) $ , either $ b_i $ divides $ b_{i + 1} $ , or $ b_{i + 1} $ divides $ b_i $ (or both);
$ 2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S $ .

Your task is to find any beautiful array. It can be shown that at least one beautiful array always exists.

输入格式:

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $ n $ ( $ 2 \le n \le 50 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

输出格式:

For each test case, print the beautiful array $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 10^9 $ ) on a separate line. It can be shown that at least one beautiful array exists under these circumstances. If there are multiple answers, print any of them.

样例:

样例输入1:

1
2
3
4
5
6
7
8
9
4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3

样例输出1:

1
2
3
4
3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3

思路:

实现:

 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
// Problem: CF1463B Find The Array
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1463B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int a[100001], n;
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        yin >> n;
        long long sum1 = 0, sum2 = 0;
        for (int i = 1; i <= n; i++)
        {
            yin >> a[i];
            if (i & 1)
                sum1 += a[i] - 1;
            else
                sum2 += a[i] - 1;
        }
        if (sum1 < sum2)
        {
            for (int i = 1; i <= n; i++)
            {
                if (i & 1)
                    yout << 1 << " ";
                else
                    yout << a[i] << " ";
            }
            yout << endl;
        }
        else
        {
            for (int i = 1; i <= n; i++)
            {
                if (i & 1)
                    yout << a[i] << " ";
                else
                    yout << 1 << " ";
            }
            yout << endl;
        }
    }
    return 0;
}

目录

CF1463B-Find The Array

CF1463B-Find The Array

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

思路:

实现: