Codeforces Round #810 (Div. 2)

A. Perfect Permutation

题目链接：Problem - A - Codeforces

样例输入：

2
1
4

样例输出：

1
2 1 4 3

题意：给定一个n，让我们构造一个1~n的排列p，使得∑i=1n(p[i]" role="presentation" style="position: relative;">∑ni=1(p[i]$\sum _{i=1}^n(p[i]$的值最小，首先来思考一下，有没有可能构造一个排列使得上述求和式等于0呢？其实这显然是不可能的，因为对于i等于1时，任意一个p[i]均能被i整除，所以如果我们能够构造一个排列使得上述求和式的值等于1，那么这种情况一定是最优的，我们直接令p[i]=(i%n)+1，即可，这样除了p[n]=1之外，其他任何数都有p[i]=i+1，因为i和i+1是两个相邻的数，那么一定是互质的，所以一定不会整除，只有n%1=0成立。

细节见代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=2;i<=n;i++)
			printf("%d ",i);
		puts("1");
	}
	return 0;
} 

B. Party

题目链接：Problem - B - Codeforces

 样例输入：

4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1

样例输出：

0
2
3
2

题意：一开始给定一个n，代表参与聚会的候选人数，然后在这n个人之间有m对关系，每个人有一个不高兴值，当我们不邀请这个人参与聚会时，这个人就会不高兴，问我们在参与聚会的人中存在的关系数目为偶数的前提下不高兴值最小是多少？

分析：首先我们知道，如果m是偶数，那么肯定是邀请所有人参与聚会，这样不高兴值就会变为0，所以我们着重选择n为奇数的情况下进行讨论，先给出一个结论：在结果最优的情况下不参与聚会的人数不会超过2.首先我们用ans记录当前获得的满足题意的最小不高兴值，如果与i有关的关系数目为奇数，那么我们去掉i后剩余的关系数目一定是一个偶数，是满足题意的，这个时候我们就可以记录一下不高兴值，而如果与i有关的关系数目为偶数时，我们用一个vector p[i]记录与第i个人有关系的人，假如我们去掉i，那么我们再去掉p[i]中的一个同样有偶数对关系的人，那么剩余的关系也就变为了偶数，因为两者有关系，所以有一对关系是重复去掉的，我们也统计一下这种情况，所以这样我们就能在O(n+m)的复杂度下统计完所有只删除1个或者2个人满足题意的最小不高兴值，但是假如答案是大于两个的，那么显然是多删除了的，因为里面如果有两个人没有关系，那么完全可以少删除一个人，而如果有两个人有关系，那么只需要删除这两个人即可，所以在结果最优的情况下不参与聚会的人数不会超过2。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+10;
int a[N];
vector<int>p[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			p[i].clear();
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			p[u].push_back(v);
			p[v].push_back(u);
		}
		if((m&1)==0) puts("0");
		else
		{
			int ans=0x3f3f3f3f;
			for(int i=1;i<=n;i++)
				if(p[i].size()&1) ans=min(ans,a[i]);
				else
				{
					for(int j=0;j<p[i].size();j++)
						if((p[p[i][j]].size()&1)==0)
							ans=min(ans,a[i]+a[p[i][j]]);
				}
			printf("%d\n",ans);
		}
	}
	return 0;
}

C. Color the Picture

题目链接：Problem - C - Codeforces

样例输入：

6
4 6 3
12 9 8
3 3 2
8 8
3 3 2
9 5
4 5 2
10 11
5 4 2
9 11
10 10 3
11 45 14

样例输出：

Yes
No
Yes
Yes
No
No

题意：给定一个n*m的方格，然后给定k中颜色，接下来给出每种颜色的限定使用次数a[i]，问我们能否把n*m的方格在颜色使用次数不超过限制的情况下全涂满方格，使得每个方格上下左右四个方格中至少有三个方格与该方格颜色相同。默认：第一行的上面是第n列，第n行的下面是第i行，第一列的左边是第m列，第m列的右边是第1列。

分析：通过模拟容易发现一个结论：颜色要么是直接按行进行涂抹，要么就是按列进行涂抹，就是说，要么一行的颜色是相同的要么一列的颜色是相同的，而且至少是连着的至少两行或者两列（边缘除外，当然边缘我们可以把两个边缘的颜色连起来，这也是符合题意的，就比如样例我们可以先涂两列1再涂两列3最后涂两列2，这两种涂法是等价的），为什么必须是一行或者一列连涂呢？因为如果不这么做，那么至少存在一个方格一行中与其相邻的一个方格颜色与其不同，一列中也有一个相邻的方格与其颜色不同，那么这个方格显然是不满足题意的，所以必须要一行或者一列地进行涂色，那么我们就分别枚举一下按行涂色或者按列涂色即可，其中如果有一种方案是可以成功涂色的那么就输出Yse，否则输出No，判断标准就是说比如我们按行涂色，那么对于每种颜色我们需要统计一下他能够与支持连着涂几行，如果只能连着涂一行，那么我们就不统计贡献，因为这样是无法满足题意的，我们遍历完所有的颜色后如果贡献大于行数，那么基本上就可以了，为什么是基本上呢？这是因为有一种特殊情况我们需要特殊考虑一下就是如果行数是奇数但是我们所有的颜色的贡献都是2那么这种是不符合题意的，因为只靠2是无法组成一个奇数的。当时如果有一个数的贡献大于等于3就可以了，因为它可以灵活选取贡献的多少。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		long long s1=0,s2=0;
		bool flag1=false,flag2=false;
		for(int i=1;i<=k;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]/n>=2)
			{
				s1+=a[i]/n;
				if(a[i]/n>2) flag1=true;
			}
			if(a[i]/m>=2)
			{
				s2+=a[i]/m;
				if(a[i]/m>2) flag2=true;
			}
		}
		bool flag=false;
		if(s1>=m)
		{
			if(m&1)
			{
				if(flag1) flag=true;
			}
			else flag=true;
		}
		if(s2>=n)
		{
			if(n&1)
			{
				if(flag2) flag=true;
			}
			else flag=true;
		}
		if(flag) puts("Yes");
		else puts("No");
	}
	return 0;
}