CF960

A

记录每个数出现的次数\(a\)，如果存在\(a\)为奇数，那么输出YES。否则最后输出NO。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
	int t=1;	
	cin>>t;
	while(t--)	
	{
		solve();
	}
}
int mp[MAXN];
void solve()
{	
	int n;	cin>>n;
	memset(mp,0,sizeof(mp));
	vector<int> a(n+1,0);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(mp[a[i]]%2)
		{
			cout<<"YES\n";
			return;
		}
	}
	cout<<"NO\n";
}

B

不难想到在\(x\)的右边所有数的总和小于0，而在\(y\)的左边所有数的总和小于0，所以先初始化为1，然后在\(x+1，x+3······\)这样交替进行构造。\(y-1,y-3\)也是如此。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
	int t=1;	
	cin>>t;
	while(t--)	
	{
		solve();
	}
}
int a[MAXN];
void solve()
{	
	int n,x,y;	cin>>n>>x>>y;
	for(int i=1;i<=n;i++)
	{
		a[i]=1;
	}
	for(int i=x+1;i<=n;i+=2)
	{
		a[i]=-1;
	}
	for(int j=y-1;j>=1;j-=2)
	{
		a[j]=-1;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<"\n";
}

C

对原序列求一次MAD操作得到数组\(b\)，不难发现：\(b\)数组是一个单调递增的数组，每次操作后是对\(b\)进行向右平移操作，前面用0补充。需要注意的是：

如果同一个数字在\(b\)中出现多次，那么做一次MAD运算后是右移。

如果是出现一次的话，就用前面的进行填充即可，再计算上贡献。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
	int t=1;	
	cin>>t;
	while(t--)	
	{
		solve();
	}
}
ll a[MAXN];
ll b[MAXN];
ll mp[MAXN];
map<ll,int> m;
void solve()
{	
	int n;	cin>>n;
	ll maxn=0;
	m.clear();
	for(int i=1;i<=n;i++)
	{
		mp[i]=b[i]=0;
	}
	ll sum=0;
	ll tmp=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		if(mp[a[i]])
		{
			b[i]=max(a[i],maxn);
			maxn=max(b[i],maxn);
		}
		else
		{
			mp[a[i]]++;
			b[i]=b[i-1];
		}
	}
	for(int i=1;i<=n;i++)
	{
		m[b[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(m[b[i]]>=2)
		{
			sum+=b[i]*(n-i+1);
		}
		else	
		{
			sum+=b[i]+b[i-1]*(n-i);
			b[i]=b[i-1];
		}
	}
	cout<<sum<<"\n";
}

另外的方法：实际上模拟两次即可（模拟完两次后，出现一次的元素就消失了，直接计算出现多次的情况即可）。

//jiangly
#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    i64 ans = 0;
    
    for (int t = 0; t < 2; t++) {
        std::vector<int> vis(n + 1);
        int mx = 0;
        for (auto &x : a) {
            ans += x;
            if (vis[x]) {
                mx = std::max(mx, x);
            }
            vis[x] = 1;
            x = mx;
        }
    }
    for (int i = 0; i < n; i++) {
        ans += 1LL * (n - i) * a[i];
    }
    std::cout << ans << "\n";
}

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

D

后来补的题目：应该是按照题目进行模拟吧。

关键是样例二，可以用方块进行跨行填补。代码细节比较多，不太好调。

最后需要留意的是用\(a[n]\)特判一下。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
	int t=1;	
	cin>>t;
	while(t--)	
	{
		solve();
	}
}
int a[MAXN];
void solve()
{	
	int n;	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		if(a[i]==0)	continue;
		else if(a[i]>2)
		{
			ans++;
		}
		else
		{
			if(a[i+1]<=2)
			{
				ans++;
				a[i+1]=0;
			}
            //对应样例二
			else if(a[i+1]<=4 && a[i+2]>2 && i+2<=n)
			{
				ans+=2;
				a[i+1]=0;
				a[i+2]-=2;
			}
			else
			{
				ans++;
			}
		}
	}
	if(a[n])	ans++;
	cout<<ans<<"\n";
}