比赛地址:https://codeforc.es/contest/1726

A题:大意是给出一个数组a,然后可以选择一个l和r,可以使得l和r做任意次转换  al = al+1对于l - r之间的所有元素,其中ar = al。求出an - a1的最大值。

上来第一题感觉就不简单,wa了好几次。这个题需要分情况来讨论。

当选择l和r是整个范围,那么最大值就是ai - ai+1,因为我们总能够将ai置为an  ,将ai+1置为a1.

同样的,如果a1存在一个小数,那么我们可以通过l和r来找 一个最大数,这样值就是max - a1.  右侧同理。

code:


#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n,x;
	cin>>n;
	vector<int>ve;
	int maxt = 0,mint=9999;
	for(int i=1;i<=n;i++)
		cin>>x,ve.push_back(x),maxt=max(maxt,x),mint=min(mint,x);
	maxt = maxt - ve[0];
	maxt = max(maxt,ve[n-1] - mint);
	for(int i=0;i<ve.size()-1;i++)
		maxt = max(maxt,ve[i]-ve[i+1]);
	maxt = max(maxt,ve[n-1]-ve[0]);
	
	cout<<maxt<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}


B题:大意是给出一个n和m,有n个数总和为m,这n个数的互相异或的结果为0。求是否能构造,并输出构造。ai>0

如果n>m肯定无法构造

如果n是2的倍数,m不是2的倍数也无法构造。因为这样一定存在一个偶数异或一个奇数。

其他可以构造。

我们可以使得前缀2k个数全部为1,这样的异或一定是0。如果n不是2的倍数我们使得最后的数 为1 和一个m剩余的偶数;如果n是2的倍数,我们需要使得最后构造两个偶数,那么我们输出m剩余的m/2。

code:


#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n,m;
	cin>>n>>m;
	if(n>m||(n%2==0&&m%2!=0))
		cout<<"NO"<<endl;
	else{
		cout<<"YES"<<endl;
		if(n%2==0){
			for(int i=1;i<=n-2;i++) m--,cout<<1<<' ';
			m>>=1,cout<<m<<' '<<m<<endl;
		}else
			for(int i=1;i<=n;i++) m--,printf("%d%c",i==n?m+1:1,i==n?'\n':' ');
	}
}
int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}


C题:

也就是说如果存在一个内嵌的(),那么一定可以形成一个连通分量,再加上本身的连通的分量这样,连通分量的数量就是  ((或))数量+1

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n;
	cin>>n;
	string a;
	cin>>a;
	int ans = 0;
	for(int i=1;i<n*2;i++)
		if(a[i]=='('&&a[i-1]=='(')	ans++;
	cout<<ans+1<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}