P10643 题解

· · 题解

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;
}