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
输出
-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
思路
这道题主要就靠一下两个关系：
- 正数 $-$ 负数 $=$ 正数
- 负数 $-$ 正数 $=$ 负数
根据这两个式子，我们就可知这道题的构造方向：把原数组中的数变成一正一负交替出现即可
代码
#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;
}
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
输出
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
思路
这道题暴力的话必爆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
那么我们就可以在输入前先初始化好这个完美的矩阵，再在输入中比较每个点值的大小。如果输入的比我们的初始化的值要大，就说明这个点存在矛盾，这个不能做到完美；如果输入的比我们初始化的要小，我们就可以不断给它加一直到它和我们初始化的数组一样。
最后输出的就是我们初始化的数组
代码
#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;
}
C. Element Extermination
题意简述
输入
4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5
输出
YES
YES
NO
YES
思路
这道题是一道思维题，虽然我一开始的思路错了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;
}
