Codeforces Round 881 (Div. 3)

A.Array Coloring

题目大意

思路

简单判断数组和的奇偶性即可（小学数学）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int sum = 0, x;
        for (int i = 1; i <= n; i++)
        {
            cin >> x;
            sum += x;
        }
        if (sum % 2 == 0)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

Maximum Rounding

题目大意

遍历一个数字的每一位，判断在哪一位四舍五入值最大。

思路

按照题意模拟即可(比赛时被 HACK 了)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        s = '0' + s;
        int lst = s.size() - 1;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            if (s[i] >= '5')
            {
                for (int j = i; j <= lst; j++)
                    s[j] = '0';
                lst = i - 1;
                if (s[i - 1] != '9')
                    s[i - 1] += 1;
                else
                {
                    while (s[i - 1] != '9')
                        s[i - 1] = '0', i--;
                    s[i - 1]++;
                }
            }
        }
        if (s[0] != '0')
            cout << s << endl;
        else
            cout << s.substr(1) << endl;
    }
    return 0;
}

C.Assembly via Minimums

题目大意

![image-20230808200812873](C:\Users\Jianfan Li\AppData\Roaming\Typora\typora-user-images\image-20230808200812873.png)

思路

假设 \(a\) 有序，对 \(b\) 也进行排序，这是不影响结果的。

设 \(a\) 中最小值为 \(x\)，则 \(x\) 在排序后的 \(b\) 中会连续出现 \(n-1\) 次，设次小值为 \(x_1\) ，在排序后的 \(i\) 会出现 \(n-2\) 次(除了 \(x\) 其他都是本身) ，以此类推，第 \(n-1\) 个数为 \(x\)，第 \(n-1+n-2\) 个数为 \(x_1\) ...

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL a[N], b[N];
int n;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n * (n - 1) / 2; i++)
            cin >> a[i];
        sort(a + 1, a + n * (n - 1) / 2 + 1);

        int cnt = 0, idx = 0;
        for (int i = n - 1; i; i--)
        {
            cnt += i;
            b[++idx] = a[cnt];
        }
        for (int i = 1; i < n; i++)
            cout << b[i] << ' ';
        cout << b[n - 1] << endl;
    }
    return 0;
}

D - Strong Vertices

题目大意

![image-20230808201625409](C:\Users\Jianfan Li\AppData\Roaming\Typora\typora-user-images\image-20230808201625409.png)

思路

将题目中的式移向得

\[a_u-b_u≥b_u-b_v \]

当 \(a_u-b_u\) 最大时才会向其他所有顶点连边，所以只需要找最大 \(a_u-b_u\) 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;

struct node
{
    LL id, num;
} a[N];

bool cmp(node a, node b)
{
    return a.id < b.id;
}

bool cmp2(node a, node b)
{
    return a.num > b.num;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        LL maxx = -0x3f3f3f3f3f3f;
        for (int i = 1; i <= n; i++)
            cin >> a[i].num;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            a[i].num -= x;
            a[i].id = i;
            maxx = max(maxx, a[i].num);
        }
        sort(a + 1, a + n + 1, cmp2);
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += (a[i].num == maxx);
        cout << ans << endl;
        sort(a + 1, ans + a + 1, cmp);
        for (int i = 1; i <= ans; i++)
            cout << a[i].id << ' ';
        cout << endl;
    }
    return 0;
}