Codeforces Round 960 (Div. 2)

情况

太惨烈了···
时间：2024年7月20日22:35
AB。https://imagebed-c8c.pages.dev/file/8e9b4283ee6cd1e5679c3.png

题解

A

题意

Alice和Bob在一个大小为 n的数组 a中玩游戏。
他们轮流做手术，爱丽丝先开始。不能操作的玩家将输。首先，将变量 mx设置为 0 。
在一个操作中，玩家可以做：

• 选择索引 i（ 1≤i≤n ），使 ai≥mx𝑎𝑖≥𝑚𝑥 并将 mx𝑚𝑥 设置为 ai 。然后，将 ai设置为 0 。

判断爱丽丝是否有获胜策略。

思路

就是每个数都是偶数个就会输，只要有奇数个，就稳赢

代码

REN（多开一个数组不就行了）

void solve()
{
    cin >> n;
    vector<int> aa(n + 1);
    vector<int> bb(n + 1);
    for (int i = 1, x; i <= n; i++)
    {
        cin >> aa[i];
        bb[aa[i]]++;
    }
    for (int i = n; i >= 1; i--)
    {
        if (bb[i] & 1)
        {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

我写的愚蠢代码

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    int ans = 0;
    int t = n - 1;
    for (int i = n - 1; i >= 0; --i)
    {
        if (a[i] == a[t])
            ans++;
        else
        {
            if (ans % 2 == 0)
                {
                    ans = 1;
                    t = i;
                    continue;
                }
            else
                {
                    cout << "YES\n";
                    return;
                }
        }
    }
    if( ans%2 == 1)cout << "YES\n";
    else
    cout << "NO\n";
}

问题

多尝试去实现而不是用笨方法。还有看是否是2的倍数用&1

B

题意

最大前缀位置：从第一个加到I，能获得最大值的最小
最大后缀位置：从最后一个加到i，能获得最大值的最大
数组只能1、-1
给出满足条件的数组。

思路

让中间x~y变成1，再让其他位置加的时候和为0

代码

REN

void solve()
{
    cin >> n >> x >> y;
    vector<int> aa(n + 1);
    vector<int> bb(n + 1);
    int cnt = -1;
    for (int i = y - 1; i >= 1; i--)
    {
        aa[i] = cnt;
        cnt = cnt == 1 ? -1 : 1;
    }
    for (int i = y; i <= x; i++)
    {
        aa[i] = 1;
    }
    cnt = -1;
    for (int i = x + 1; i <= n; i++)
    {
        aa[i] = cnt;
        cnt = cnt == 1 ? -1 : 1;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << aa[i] << ' ';
    }
    cout << '\n';
}

我的愚蠢写法

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;
    int ans[n];
    int vav = -1;
    int vav2 = -1;

    for (int i = y - 2; i >= 0; --i)
    {

        ans[i] = vav;
        vav = -vav;
    }
    for (int i = y - 1; i < x; ++i)
    {
        ans[i] = 1;
    }
    for (int i = x; i < n; ++i)
    {
        ans[i] = vav2;
        vav2 = -vav2;
    }
    for (int i = 0; i < n; ++i)
    {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

问题

读题就读了半天，搞清楚每个字母啊！
为什么卡了那么久呢。因为：
对于7，3，2，您的数组将是-1 1 1 -1 -1-1-1 -1。但是这个数组的最大后缀位置是6，而不是2。

C

题意

MAD （最大的至少出现两次的数），只出现一次为0。
一个数组和sum=0
循环：
sum=sum+所有和
将每一个位置的数变为MAD从1到i

思路

一次操作过后，递增。
两次操作过后，必定递增+之后每次都右移。

代码

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

typedef long long LL;
typedef pair<int, int> PII;
#define int LL
const int N = 100000;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int sum = 0;

    for (int j = 0; j < 2; j++)
    {

        vector<int> b(n + 1);

        int maxmad = 0;
        for (int i = 0; i < n; i++)
        {
            sum += a[i];
            if (b[a[i]] == 1)
            {
                maxmad = max(maxmad, a[i]);
            }
            b[a[i]] = 1;
            a[i] = maxmad;
        }
    }
    for (int i = 0; i < n; i++)
    {
        sum += a[i] * (n - i); // 1LL * a[i]* (n-i);
    }
    cout << sum << endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
2 2 3
0 2 2
0 0 2

2 1 1 2
0 0 1 2
0 0 0 0

2 2 2 3 1 3 4 4
0 2 2 2 2 3 3 4
0 0 2 2 2 2 3 4

*/

问题

读错题了还