比赛链接:https://codeforc.es/contest/1711

感觉题比较难,幸亏没参赛,不然掉老多分了。感觉一个也做不出来,补题只打算补A和B了

A题:大意是给出一个n,制作一个p1 - pn长度的序列,内容为1-n,对于每一个pi,如果pi%i==0则为一个权重,最后使得权重最小。

一个很明显的数学构造题,我们从1开始考虑,这个元素权重至少为1,对于剩下的每个pi,都有pi-1%pi !=0,所以可以把n放在最前面,剩下的作为顺序排列。

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		cout<<n<<' ';
		for(int i=1;i<n;i++)
		{
			cout<<i<<' ';
		}
		cout<<endl;
	}
}

 

B题:大意是要开一个party,有n个人,如果不邀请其中的一个人就会获得一个不快乐值,给出n个人的预计不快乐值。
party开始后,朋友之间会分享蛋糕,有m对朋友,每个人吃的蛋糕数量=他被邀请的次数,蛋糕机一次只能做两个,所以要求求出一种邀请方式,使得获得的不快乐值最少,且吃的蛋糕数量为偶数。

思路:这个题很有意思,因为吃的蛋糕必须是偶数,所以有可能存在一种情况,所有的人我都邀请了,然而却消费了奇数个蛋糕,这个时候我就需要不邀请一些朋友。首先我们考虑一下有没有可能存在一种情况,使得我们吃的蛋糕是偶数呢,肯定是存在的,当m为偶数时,度为0的成员一定是个偶数的,所以不用删除朋友。

当m为奇数时,我们可以删除一个奇数度的朋友,使得吃的蛋糕数量为偶数。也可以删除一对相邻的偶数度朋友,这里也可以理解成删除一组朋友一定能形成一个合法状态,上面说到了。特别注意的一种情况,就是当m为奇数时,我们既可以删除一个奇数度朋友,也可以删除两个成一对的偶数度朋友。

经过举一反三的测试,我们总可以通过删除一对朋友获得一个合法状态,也总可以通过删除一个奇数度朋友获得一个合法状态。

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
int unhappy[nn];
int degree[nn];
int x[nn],y[nn];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		memset(unhappy,0,sizeof unhappy);
		memset(degree,0,sizeof degree);
		memset(x,0,sizeof x);
		memset(y,0,sizeof y);
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>unhappy[i];
		for(int i=1;i<=m;i++)
		{
			cin>>x[i]>>y[i];
			degree[x[i]]++;
			degree[y[i]]++;
		}
	/*	for(int i=1;i<=n;i++)
			cout<<degree[i]<<' ';
		cout<<endl;*/
		int ans = 9999999;
		if(m%2==0) ans = 0;
		for(int i=1;i<=n;i++)//删除一个奇数点 
			if(degree[i]%2==1)
				ans = min(ans,unhappy[i]);
		for(int i=1;i<=m;i++)//删除一对偶数点 
		//	if(degree[x[i]]%2==0&&degree[y[i]]%2==0)
				ans = min(ans,unhappy[x[i]]+unhappy[y[i]]);
		cout<<ans<<endl; 
	}
}