A. Submission Bait

题目

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

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

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

—选择索引 i i i ( 1 ≤ i ≤ n 1 \le i \le n 1in )为 a i ≥ m x a_{i} \geq mx aimx ,将 m x mx mx 设置为 a i a_{i} ai 。然后将 a i a_{i} ai 设置为 0 0 0

判断Alice是否有制胜策略。

输入* * * *

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

对于每个测试用例:

—第一行为整数 n n n ( 2 ≤ n ≤ 50 2 \leq n \leq 50 2n50 ),表示数组的大小。
—第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 1 ≤ a i ≤ n 1 \leq a_i \leq n 1ain )—数组的元素。

      • *输出

对于每个测试用例,如果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 m m 的数组 b b b ,定义:

  • b b b最大前缀位置是满足 b 1 + … + b i = max ⁡ j = 1 m ( b 1 + … + b j ) b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j) b1++bi=maxj=1m(b1++bj)最小索引 i i i ;
    b b b最大后缀位置是满足 b i + … + b m = max ⁡ j = 1 m ( b j + … + b m ) b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m) bi++bm=maxj=1m(bj++bm)最大索引 i i i

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

  • a i a_i ai 1 1 1 − 1 -1 1 对于所有 1 ≤ i ≤ n 1 \le i \le n 1in ;
  • a a a最大前缀位置 x x x ;
  • a a a最大后缀位置 y y y

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

输入* * * *

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

对于每个测试用例:

—唯一一行包含三个整数 n n n x x x y y y ( 2 ≤ n ≤ 1 0 5 , 1 ≤ y < x ≤ n ) 2 \leq n \leq 10^5, 1 \le y \lt x \le n) 2n105,1y<xn) )。

保证所有测试用例的 n n n 之和不超过 1 0 5 10^5 105

      • *输出

对于每个测试用例,在新行中输出 n n n 空格分隔的整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an

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

题目

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

例如, MAD ⁡ ( [ 1 , 2 , 1 ] ) = 1 \operatorname{MAD}([1, 2, 1]) = 1 MAD([1,2,1])=1 MAD ⁡ ( [ 2 , 2 , 3 , 3 ] ) = 3 \operatorname{MAD}([2, 2, 3, 3]) = 3 MAD([2,2,3,3])=3 MAD ⁡ ( [ 1 , 2 , 3 , 4 ] ) = 0 \operatorname{MAD}([1, 2, 3, 4]) = 0 MAD([1,2,3,4])=0

给定一个大小为 n n n 的数组 a a a 。最初,变量 s u m sum sum 被设置为 0 0 0

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

  1. s u m : = s u m + ∑ i = 1 n a i sum := sum + \sum_{i=1}^{n} a_i sum:=sum+i=1nai ;
  2. b b b 为大小为 n n n 的数组。为所有 1 ≤ i ≤ n 1 \le i \le n 1in 设置 b i : =   MAD ⁡ ( [ a 1 , a 2 , … , a i ] ) b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i]) bi:= MAD([a1,a2,,ai]) ,然后为所有 1 ≤ i ≤ n 1 \le i \le n 1in 设置 a i : = b i a_i := b_i ai:=bi

处理结束后,查找 s u m sum sum 的值。

输入* * * *

第一行包含一个整数 t t t ( 1 ≤ t ≤ 2 ⋅ 1 0 4 1 \leq t \leq 2 \cdot 10^4 1t2104 )—测试用例的数量。

对于每个测试用例:

—第一行包含一个整数 n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \leq n \leq 2 \cdot 10^5 1n2105 )—数组的大小 a a a ;
—第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 1 ≤ a i ≤ n 1 \leq a_i \leq n 1ain )——数组的元素。

保证所有测试用例的 n n n 之和不超过 2 ⋅ 1 0 5 2 \cdot 10^5 2105

      • *输出

对于每个测试用例,在新的一行中输出 s u m sum 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;
 } 

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部