Codeforces Round 960 (Div. 2)

A

这题在一次操作中，玩家可以执行以下操作：

选择一个索引 iii (1 ≤ i ≤ n)，使得 a[i] ≥ mx，并将 mx 设为 a[i]。然后，将 a[i] 设为 0。

Alice先手，判断 Alice 是否有必胜策略。

刚开始我兴冲冲取最大值，判断是否为奇数，然后就WA了。

其实这题属于博弈论，只要有一个数的数量为奇数，则Alice获胜

Alice选择最大的奇数，取走一个数，该数的数量变为偶数。
此时该数后的数后的数的数量都为偶数，则该问题转变为对手的问题，我们易推断出对手必输。

#include <algorithm>
#include <iostream>
using namespace std;

const int N = 105;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int arr[N];
    for (int i = 0; i < N; i++)
      arr[i] = 0;
    bool flag = false;
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
      int num;
      cin >> num;
      arr[num]++;
    }
    for (int i = 50; i >= 1; i--) {

      if (arr[i] % 2 != 0) {

        cout << "YES" << endl;
        flag = true;
        break;
      }
    }
    if (!flag)
      cout << "NO" << endl;
  }
  return 0;
}

B

构造+贪心，

对于所有 1≤i≤n，a[i] 要么是 1，要么是 -1；
数组 a 的最大前缀位置是 x；
数组 a 的最大后缀位置是 y。
n𝑛, x𝑥, and y𝑦 (2≤n≤105,1≤y<x≤n)2≤𝑛≤105,1≤𝑦<𝑥≤𝑛).

#include <iostream>

using namespace std;
const int N = 1e5+10;
int n,x,y;
int a[N];
int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        cin >> n >> x >> y;
        for(int i = y - 1, j = -1; i >= 0;i --, j = -j)
            a[i] = j;
        for(int i = y ; i <= x;i ++)
            a[i] = 1;
        for(int i = x + 1, j = -1; i <= n;i ++, j = -j)
            a[i] = j;


        for(int i = 1;i <= n;i ++)
            cout << a[i] << ' ';
        cout << endl;
    }
}

c

设置 ( sum := $sum + \sum_{i=1}^{n} a_i$ )
设 ( b ) 为大小为 ( n ) 的数组。对于所有 ( $1 \leq i \leq n$ )，设置 ( b_i := MAD( $[a_1, a_2, \ldots, a_i]$ ) )，然后设置 ( $a_i := b_i$ )

找到该过程结束后 ( sum ) 的值。

这里的mad是会随着数组的移动更新
第一次会将前面（第一次有重复数字的位置前）没有重复的数字设置为0
第二次会将后面（第一次有重复数字的位置后）的数字设置为对应数字
那么我们就需要模拟出前两次循环，然后将后面的数累计即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#define ll long long
const int N = 200005;
int a[N], c[N];

using namespace std;

int main()

{
  int T;
  
  cin >> T;
  while (T--) {
    ll sum = 0;
    memset(c,0,sizeof(c));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)	
      {
        cin >> a[i];
        sum+=a[i];
      }

    int mx = 0;
    for(int i = 1; i <= n; i ++)	
    {
      if (++c[a[i]]>=2) mx=max(mx,a[i]);
			a[i]=mx; 
      sum+=a[i];
    }
    memset(c,0,sizeof(c));
    mx = 0;
    for(int i = 1; i <= n; i ++)
    {
      if (++c[a[i]]>=2) mx=max(mx,a[i]);
			a[i]=mx;
       sum += 1LL * a[i] * (n-i + 1);	//累加
    }
    cout << sum << endl;
  }
}

参考

Codeforces Round 960 (Div. 2) - Luckyblock - 博客园 (cnblogs.com)

Codeforces Round 960 (Div. 2) - 空気力学の詩 - 博客园 (cnblogs.com)