Codeforces Round ＃810 (Div. 2)A~C题解

Codeforces Round #810 (Div. 2)https://codeforces.com/contest/1711

A~C题解

A.Perfect Permutation

题意：给定一个数n，生成一个n的排列使得在这个排列中满足第i个数能被i整除的元素的个数最小。

分析：从1开始，每两个相邻的自然数互质，（可证明其最大公约数为1从而证明）可根据这个特点生成排列。【此题解法不唯一】

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        vector<int> ans(n);
        for (int i=0;i<n;i++)
            ans[i]=i+1;
        for (int i=0;i<n-2;i+=2)
            swap(ans[i],ans[i+1]);
        if (n>1)
        swap(ans[n-1],ans[n-2]);
        for (int i=0;i<n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

B.Party

题意：有n个人可供邀请，给出每个人若未被邀请产生的不满意值和一个朋友列表（m队朋友），若一队朋友两个人均被邀请，要做一个蛋糕，现问满足做偶数个蛋糕的情况下产生的最小不满意值。注意：朋友之间的关系可能是多边的。

分析：虽然朋友之间是有“朋友圈”的，但由于关系不重复，最多只有n*(n-1)/2朋友关系，如果m是偶数，均可被邀请，最小不满意值为零。根据这个思路处理奇数情况，先要得到一个偶数，把偶数对的朋友都邀请了，剩下的那个人就是不邀请的，取最小值更新即可。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m,a[N];
ll sum,ans;
int du[N],p1[N],p2[N];
void solve()
{
	cin>>n>>m;
	ans=2e9;
	memset(du,0,sizeof(du));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>p1[i]>>p2[i];
		du[p1[i]]++;
		du[p2[i]]++;
	}
	if(m%2==0)
	{
		cout<<0<<'\n';
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if((m-du[i])%2==0)
            ans=min(ans,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		if((du[p1[i]]+du[p2[i]])%2==0)
            ans=min(ans,a[p1[i]]+a[p2[i]]);
	}
	cout<<ans<<'\n';


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

C.Color the Picture

题意：对图案的每一个方格，都有至少三个相邻的方格和它的颜色一样，这个图案就是美丽图案。给出k种颜料的数量和图案的大小n*m，问能否上色使得这个图案成为美丽图案。

分析：只有横着上色和竖着上色满足题意。

Code:

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int k,a[N];
bool check(int n,int m)
{
	ll s=0;
	bool n2=false;
	for(int i=0;i<k;i++)
	{
		int now=a[i]/n;
		if(now>=2)
		{
			s+=now;
			if(now>=3)n2=true;
		}
	}
	if(s<m)return false;
	else if(n2)return true;
	else if(s%2!=m%2)return false;
	else return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while (t--)
	{
		int n,m;
		cin>>n>>m>>k;
		for(int i=0;i<k;i++)
            cin>>a[i];
		if (check(n,m)||check(m,n))
            puts("YES");
        else
            puts("NO");
	}
}