Codeforces Round 960 (Div. 2) A B C

A. Submission Bait

题目

Alice和Bob正在一个大小为 $n$ 的数组 $a$ 中玩一个游戏。

他们轮流做操作，爱丽丝先开始。不会操作的玩家会输。首先，将变量 $mx$ 设置为 $0$ 。

在一个操作中，玩家可以做:

—选择索引 $i$ ( $1\le i\le n$ )为 $a_i\ge mx$ ，将 $mx$ 设置为 $a_i$ 。然后将 $a_i$ 设置为 $0$ 。

判断Alice是否有制胜策略。

输入* * * *

第一行包含一个整数 $t$ ( $1\le t\le 10^3$ )—测试用例的数量。

对于每个测试用例:

—第一行为整数 $n$ ( $2\le n\le 50$ )，表示数组的大小。
—第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ )—数组的元素。

• • • *输出

对于每个测试用例，如果Alice有一个获胜的策略，输出“YES”。否则输出“NO”。

您可以在任何情况下输出答案(上或下)。例如，字符串“yEs”、“yEs”、“yEs”和“yEs”将被识别为积极响应。

AC代码

// 从较大的数开始选择，如果存在较大值为奇数则一定存在制胜策略
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
	memset(v,0,sizeof(v));
	memset(a,0,sizeof(a));
    int n;cin>>n;
    vector<int> num;
    int sum=0,ma=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        v[a[i]]++; // 统计出现数的次数
        if(v[a[i]]==1)
        {
        	num.push_back(a[i]);// 统计出现的数
		}
    }
    sort(num.begin(),num.end());
    int t=v[num[num.size()-1]],tt=0;
    int f=0;
    for(int i=num.size()-1;i>=0;i--)
    {
    	if(v[num[i]]%2==0)f=0;
    	else
    	{
    		f=1;
    		break;
		}
	}
	if(f==1)cout<<"Yes";
	else	cout<<"No";
    cout<<"\n";
}

signed main()
{
   ios::sync_with_stdio(0);cin.tie(0);c out.tie(0);
	int t;cin>>t;
    while(t--)solve();
    return 0;
 } 

B. Array Craft

题目

对于大小为 $m$ 的数组 $b$ ，定义:

• $b$ 的最大前缀位置是满足 $b_1+\dots +b_i={\max }_{j=1}^m(b_1+\dots +b_j)$ 的最小索引 $i$ ;
  — $b$ 的最大后缀位置是满足 $b_i+\dots +b_m={\max }_{j=1}^m(b_j+\dots +b_m)$ 的最大索引 $i$ 。

给定三个整数 $n$ ， $x$ 和 $y$ ( KaTeX parse error: Expected 'EOF', got '&' at position 3: x &̲gt; y )。构造一个大小为 $n$ 的数组 $a$ ，满足:

• $a_i$ 是 $1$ 或 $-1$ 对于所有 $1\le i\le n$ ;
• $a$ 的最大前缀位置为 $x$ ;
• $a$ 的最大后缀位置为 $y$ 。

如果有多个符合条件的数组，输出any。可以证明，在给定条件下，这样的数组总是存在的。

输入* * * *

第一行包含一个整数 $t$ ( $1\le t\le 10^4$ )—测试用例的数量。

对于每个测试用例:

—唯一一行包含三个整数 $n$ 、 $x$ 和 $y$ ( $2\le n\le 10^5,1\le y<x\le n)$ )。

保证所有测试用例的 $n$ 之和不超过 $10^5$ 。

• • • *输出

对于每个测试用例，在新行中输出 $n$ 空格分隔的整数 $a_1,a_2,\dots ,a_n$ 。

AC代码

// 令x~y 之间的数为1 ，再从x-1 和 y+1 的位置开始-1,1 交替出现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
	memset(v,0,sizeof(v));
	memset(a,0,sizeof(a));
    int n,x,y;cin>>n>>x>>y;
    for(int i=y;i<=x;i++)a[i]=1;
    int f=0;
	for(int i=y-1;i>=1;i--)
    {
    	if(f==0)
    	{
    		a[i]=-1;
    		f=1;
		}
		else
		{
			a[i]=1;
			f=0;
		}
	}
	f=0;
	for(int i=x+1;i<=n;i++)
	{
		if(f==0)
    	{
    		a[i]=-1;
    		f=1;
		}
		else
		{
			a[i]=1;
			f=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
    cout<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
    while(t--)solve();
    return 0;
 } 

C. Mad MAD Sum

题目

我们将数组中的 $\mathrm{MAD}$ (Maximum appear Duplicate)定义为在数组中至少出现两次的最大数字。具体来说，如果没有数字至少出现两次，则 $\mathrm{MAD}$ 值为 $0$ 。

例如， $\mathrm{MAD}([1,2,1])=1$ ， $\mathrm{MAD}([2,2,3,3])=3$ ， $\mathrm{MAD}([1,2,3,4])=0$ 。

给定一个大小为 $n$ 的数组 $a$ 。最初，变量 $sum$ 被设置为 $0$ 。

下面的过程将在一个顺序循环中执行，直到 $a$ 中的所有数字都变成 $0$ :

1. $sum:=sum+{\sum }_{i=1}^n{a}_i$ ;
2. 设 $b$ 为大小为 $n$ 的数组。为所有 $1\le i\le n$ 设置 $b_i:=\mathrm{MAD}([a_1,a_2,\dots ,a_i])$ ，然后为所有 $1\le i\le n$ 设置 $a_i:=b_i$ 。

处理结束后，查找 $sum$ 的值。

输入* * * *

第一行包含一个整数 $t$ ( $1\le t\le 2\cdot 10^4$ )—测试用例的数量。

对于每个测试用例:

—第一行包含一个整数 $n$ ( $1\le n\le 2\cdot 10^5$ )—数组的大小 $a$ ;
—第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ )——数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ 。

• • • *输出

对于每个测试用例，在新的一行中输出 $sum$ 的值。

AC代码

// 操作两次后必然出现 数列 前 2 位为 0；此后为 数组的后移
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
	int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int j=1;j<=2;j++)
    {
        map<int,int>mp;
        int ma=0;
        for(int i=1;i<=n;i++)
        {
            ans+=a[i];
            mp[a[i]]++;
            if(mp[a[i]]>1)ma=max(a[i],ma);
            a[i]=ma;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]*(n-i+1);
    }
    cout<<ans;
    cout<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
    while(t--)solve();
    return 0;
 }