Codeforce Global Round 9 ABC题_codeforce round 九进制

Codeforce Global Round 9 (ABC)

A. Sign Flipping

题意简述

输入

5
3
-2 4 3
5
1 1 1 1 1
5
-2 4 7 -6 4
9
9 7 -4 -2 1 -3 9 -4 -5
9
-4 1 9 4 8 9 5 1 -9
1
2
3
4
5
6
7
8
9
10
11

输出

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

思路

这道题主要就靠一下两个关系：

1. 正数 $-$ 负数 $=$ 正数
2. 负数 $-$ 正数 $=$ 负数

根据这两个式子，我们就可知这道题的构造方向：把原数组中的数变成一正一负交替出现即可

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int a[N];

void solve()					//这里我们就把奇数位数的变成正数,偶数位数的变成负数
{
    for(int i = 1; i <= n; i++)
    {
        if(i & 1)
            a[i] = abs(a[i]);
        else
            a[i] = -abs(a[i]);
    }
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        
        solve();
        for(int i = 1; i <= n; i++)
            cout << a[i] << ' ';
    }

    return 0;
}
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

---

B. Neighbor Grid

题意简述

1. 题意

2. 输入输出格式

3. 数据范围

输入

5
3 4
0 0 0 0
0 1 0 0
0 0 0 0
2 2
3 0
0 0
2 2
0 0
0 0
2 3
0 0 0
0 4 0
4 4
0 0 0 0
0 2 0 1
0 0 0 0
0 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输出

YES
0 0 0 0
0 1 1 0
0 0 0 0
NO
YES
0 0
0 0
NO
YES
0 1 0 0
1 4 2 1
0 2 0 0
1 3 1 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路

这道题暴力的话必爆TLE，仔细观察的话发现这个本质上还是一道构造题。

首先，我们知道角上有两个相邻位置，边上有三个相邻位置，中间有四个相邻位置。

那么我们就知道每个矩阵必有一个一定完美的矩阵如下

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

那么我们就可以在输入前先初始化好这个完美的矩阵，再在输入中比较每个点值的大小。如果输入的比我们的初始化的值要大，就说明这个点存在矛盾，这个不能做到完美；如果输入的比我们初始化的要小，我们就可以不断给它加一直到它和我们初始化的数组一样。

最后输出的就是我们初始化的数组

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int m1[N][N];
int t;
int n, m;

int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                if(i == 1 && j == 1 || i == n && j == 1 
                   || i == 1 && j == m || i == n && j == m)
                    m1[i][j] = 2;
                else if(i == 1 || i == n || j == 1 || j == m)
                    m1[i][j] = 3;
                else
                    m1[i][j] = 4;
            }
        
        bool ok = true;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                int tmp;
                cin >> tmp;
                if(tmp > m1[i][j])
                    ok = false;
            }
        
        if(ok)
        {
            puts("YES");
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= m; j++)
                    cout << m1[i][j] << ' ';
                
                puts("");
            }                
        }
        else
            puts("NO");
    }

    return 0;
}
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

---

C. Element Extermination

题意简述

输入

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

输出

YES
YES
NO
YES
1
2
3
4

思路

这道题是一道思维题，虽然我一开始的思路错了QAQ

我们可以逆着去推断这道题。

如果成功的话，最后只会剩下一个数，这之前必有$a_i<a_{i+1}$。以此为界，我们就可以把数组分成左右两边。

左边那部分由于$a_i<a_{i+1}$的存在，可知最后得到的$a_i$必不小于第一个数。

同理可得右边那部分最后得到的$a_{i+1}$必不大于最后一个数。

由此可得如果$a_1>a_n$，则必不可能消除到只剩下最后一个数。

接着反向猜想，如果$a_1<a_n$，我们能否消除到只剩下最后一个数呢？

答案是可以的。

证明：我们先找到数组中值最大的那个点，把它一直向左“推”，删除掉所有在它和$a_1$之间的点。当它与$a_1$比较大小后，我们舍弃掉这个最大的数，再寻找剩下的数组中最大的那个数，重复和一开始一样的动作。我们重复此类操作直到$a_n$成为数组中最大的那个数。从$a_n$开始往左推就可以最后只剩下$a_1$。得证！

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;

int a[N];
int t;
int n;

int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        
        if(a[1] < a[n])
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}
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

文本翻译均来自洛谷