Codeforces Round 839 (Div. 3)

A. A+B?

跳过太水了、、、、、

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int a,b;
        scanf("%d+%d",&a,&b);
        cout << a+b << endl;
    }
}

B. Matrix Rotation

题意：给定两行每行两个数，满足一下条件

• 在每一行中，第一个元素小于第二个元素；
• 在每一列中，第一个元素都小于第二个元素

思路：很明显只需要最大数和最小数处于对角线就行

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int a[3][3];
    int mi = 0x3f3f3f3f, x1 = 0, y1 = 0;
    int ma = 0, x2 = 0, y2 = 0;
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            cin >> a[i][j];
            if (a[i][j] < mi) {
                mi = a[i][j];
                x1 = i;
                y1 = j;
            }
            if (a[i][j] > ma) {
                ma = a[i][j];
                x2 = i;
                y2 = j;
            }
        }
    }
    if (x2 + x1 == 3 && y1 + y2 == 3) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

C. Different Differences

题意：定义一个数组其元素是从1-n中的一个
$$
我们定义其特征为a_i-a_{i-1}
$$
求具有最大特征的原数列

思路：很明显这个数据是单增的，那么最大也就是n，每个特征也是单增的，什么时候最大呢，假设后面的特征都是1，那么第k个数的大小就是：a[i-1]+cnt+k+i，如果他大于n那么a[i]-a[i-1]=1,后面也类似

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, k;
    cin >> k >> n;
    int cnt = 1;
    vector<int> a(k + 1);
    a[1] = 1;
    for (int i = 2; i <= k; i++) {
        a[i] = a[i - 1] + (++cnt);
        if (a[i - 1] + cnt + k - i > n) {
            for (; i <= k; i++) {
                a[i] = a[i - 1] + 1;
            }
            break;
        }
    }
    for (int i = 1; i <= k; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

D. Absolute Sorting

题意：操作：找到一个数x将该数组中的数全部变成abs(a[i]-x)；目标：数组单增

思路：1.什么情况要减去x？ a[i+1]<a[i]

​ 2.x怎么取值？ (a[i]+a[i+1]+1)/2(最开始没想到+1，后面想a[i+1]>a[i]，所以x应该大一点点，减的更多负的绝对值更大)

​ 3.什么时候没有这样的值？ 找到x之后变化数组在此来看(之前想的是如果前面的有比后面需要转换的数还小的数就不行)（感谢样例！！！）

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ma = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i] < a[i - 1]) {
            ma = max(ma, (a[i] + a[i - 1] + 1) / 2);
        }
    }
    for (int i = 1; i <= n; i++)
        a[i] = abs(a[i] - ma);
    for (int i = 2; i <= n; i++)
        if (a[i] < a[i - 1]) {
            cout << "-1" << endl;
            return;
        }
    cout << ma << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

E. Permutation Game

题意：给你一个排列，这个排列可以染色，若他未被染色则位置不能动，可进行的操作：

1.将一个字染色

2.将染色之后的数重新排列

3.跳过这一轮

判断：如果最后数列为升序，那么第一个玩家胜利，否则就是第二个玩家胜利

思路：这道题给的是排列！！！，太爱啦！！！，最开始没注意我还觉得是最长上升子序列模型+博弈论(我还觉得这个3操作会让这题变得很麻烦，准备再找下题干信息然后开始放弃)。那么只需要看1赢需要变那些，2赢需要变那些（都要重新排序我就直接略过那一次了）。1不需要动的是a[i]==i,2不需要动的数为a[i]=n-i+1。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int x = 0, y = 0, z = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) x++;
        else if (a[i] == (n - i + 1)) y++;
        else z++;
    }
    if (y + z <= x) {
        cout << "First\n";
    } else if (x + z < y) {
        cout << "Second\n";
    } else {
        cout << "Tie\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}