Atcoder Beginner Contest 313_approximate equalization 2 c++

A

https://atcoder.jp/contests/abc313/tasks/abc313_ahttps://atcoder.jp/contests/abc313/tasks/abc313_a

 解题：第一个成为最大值需要增加x。需要考虑最大值相同的情况

#include<bits/stdc++.h>
using namespace std;
int n;
bool f=0;
int mx=0;
int st=0,x;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		if(i==0)
		{
			st=x;
		}
		mx=max(mx,x);
		if(x==st&&i!=0)
		f=1;
	}
	if(mx!=st||mx==st&&f==1)
	{
		cout<<mx-st+1<<endl;
	}
	else
	{
		cout<<mx-st<<endl;
	}
}

B：B - Who is Saikyo? (atcoder.jp) 

解题：要找到最强的那个，逆向思考，使用vector存储这个点的父节点，如果某个点没有父节点即它为最强。但需要注意：最强的只有一个，多个则返回-1.

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=100;
vector<int>s[N];
int m;
int x,y;
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		s[y].push_back(x);
	}
	bool f=0;
	int u=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i].size()==0&&f==0)
		{
			f=1;
			u=i;
		}
		else if(s[i].size()==0&&f==1)
		{
			cout<<"-1"<<endl;
			return 0;
		}
	}
	if(f==1)
	cout<<u<<endl;
	else
	cout<<"-1"<<endl;
}

C：C - Approximate Equalization 2 (atcoder.jp)

 解题：最后要数组a中的所有值的最大最小差值<=1。由于进行a[i]+、a[j]-的操作，数组总和保持不变，所以最后数组中的值均在平均值左右。此时答案是我们要的对小于平均值的升操作次数与大于平均值+1的减次数的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll n,s=0;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	ll u=s/n;
	ll u1=u+1;
	ll d1=0,d2=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]<u)
		{
			d1+=(u-a[i]);
		}
		else if(a[i]>u1)
		{
			d2+=(a[i]-u1);
		}
	}
	cout<<max(d1,d2)<<endl;
}

D：D - Odd or Even (atcoder.jp)

解题：交互式题目。0为偶数，1为奇数，数组由0、1组成

给定n,k。首先通过k次询问，确定前k个的和的奇偶，对第i次询问要求输出除第i个的其它k-1个的和的奇偶，并计算这些数的和x，最后前1-k+1的值即是：x-除去第i个值的其它k-1和再mod2.

接下来判断剩下的k+2-n的值，仍然用这个方法统计前k+1个已确定的值的和y，输出询问（k+2-n次），每次询问的是第一个值输出第i个值其后的k-1个值依次从1-k-1的和x，然后a[i]=y-x+2再%2得到这个值的奇偶。

综上n个值已计算完毕。

#include<bits/stdc++.h>
using namespace std;
long long i,j,k,l,r,n,m,a[200005],sum,cost,x,y,t[200005];
int main()
{
	cin>>n>>k;
    m=0;
	for (j=1;j<=k+1;j++)
	{
		cout<<'?';
		for (l=1;l<=k+1;l++)
		if (j!=l) cout<<' '<<l;
		cout<<endl; 
		cin>>t[j];
		x+=t[j];
	}
	for (i=1;i<=k+1;i++)
	{
		a[i]=x-t[i];
		a[i]%=2;
	}
	y=0;
	for (i=1;i<=k-1;i++) y+=a[i];
	for (i=k+2;i<=n;i++)
	{
		cout<<'?'<<' '<<i;
		for (j=1;j<k;j++)
		cout<<' '<<j;
		cout<<endl; 
		cin>>x;
		a[i]=y-x+2;
		a[i]%=2;
	}
	cout<<'!';
	for (i=1;i<=n;i++) cout<<' '<<a[i];
	cout<<endl; 
 }