自动搬运

查看原文

来自洛谷，原作者为

	Aventurine_stone （已AFO）愿人生的赌局，赢的总是我们。

搬运于2025-08-24 22:59:53，当前版本为作者最后更新于2024-07-29 16:08:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 题目分析

先看数据范围，$n \le 200$。如此小的数据范围，首先考虑是否可以使用模拟退火。
模拟退火可以跑十万次，但我们很快可以发现，此题对于一个随机的序列，我们很难找到一个参数用来判断此序列的优劣，故不能用模拟退火解题。
既然不是模拟退火，那么此题很明显便是一道构造题。

2. 题目做法

我们可以将他们的朋友关系做成一张图。然后创建一个数组记录每个人使用的乐器，这里我用 $0$ 表示萨克斯，用 $1$ 表示钢琴。然后用一个数组记录每个人的朋友个数，再用一个数组记录每个人与他使用不同乐器的朋友个数。
对于乐器记录数组，我们可以先随机生成一个序列，然后算出初始的不同乐器数组，之后我们对于一个人，如果他的拥有不同乐器的朋友数不符合题意，那么我们让他主修另外一种乐器，让他符合题意。就这样一直操作，直到得到一个符合题意的方案，然后输出。
每次操作的时间复杂度为 $O(n)$，那么最坏情况下我们要进行多少次操作呢？

猜测：

最多进行 $m$ 次操作。

证明：

初始时，对于一对朋友关系，如果他们使用的是不同的乐器，我们可以将此关系看作不同色关系，反之则为同色关系。
可以看出，我们每进行一次操作，那么同色关系将至少减少一，最多只有 $m$ 个同色关系，故最多进行 $m$ 次操作。
证毕。
故时间复杂度为 $O(nm)$，可以轻松通过此题。

3. 代码

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=40010;//记得开够空间 
inline int read()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x;
}
int head[N],ne[M],e[M],idx;
inline void add(int x,int y)//建边 
{
	ne[++idx]=head[x];
	head[x]=idx;
	e[idx]=y;
}
int n,m;
bool p[N];
int num[N],cnt[N];
inline void change(int x)//修改乐器 
{
	cnt[x]=num[x]-cnt[x];
	for(int i=head[x];i;i=ne[i])
	{
		int c=e[i];
		if(p[x]^p[c])
			cnt[c]++;
		else
			cnt[c]--;
	}
}
int x,y;
bool pd;
int main()
{
	n=read(),m=read();
	while(m--)
	{
		x=read(),y=read();
		add(x,y),add(y,x);
		num[x]++,num[y]++;
	}
	for(int i=1;i<=n;i++)
		p[i]=rand()&1;
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=ne[j])
		{
			int c=e[j];
			if(p[i]^p[c])
				cnt[i]++;
		}
	}
	pd=1;
	for(int i=1;i<=n;i++)
	{
		if((cnt[i]<<1)<num[i])
		{
			x=i,pd=0;
			break;
		}
	}
	while(!pd)//进行操作 
	{
		p[x]=!p[x];
		change(x);
		pd=1;
		for(int i=1;i<=n;i++)
		{
			if((cnt[i]<<1)<num[i])
			{
				x=i,pd=0;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(p[i])
			printf("P");
		else
			printf("S");
	}
	return 0;
}