洛谷 P10643 嬉皮爵士

思路

注意到标签里面有随机调整，所以随机乱搞

好吧其实也给了一定的思路（
先随机出每个点的值。然后每次 \(O(n)\) 地去检查是否合法。
假如找到某个点 \(i\) 不合法。那么将 \(i\) 这个点反转一下。因为这种权值不合法，说明另一种权值必然是合法的（只对于这个点而言）。继续上述步骤直到合法。

我并不会去证明时间复杂度，题解说至多调整 \(O(m)\) 次（似乎是因为每调整一次，至少都会减少 \(1\) 对颜色相同的边，总共又是 \(m\) 条边）。\(m\) 至多又只有 \(19900\) ，所以是可以通过的。

代码

// Problem: P10643 [NordicOI 2022] 嬉皮爵士 Hipster Jazz
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10643
// Memory Limit: 1 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,k,head[MAXN],d[MAXN],half[MAXN];
bool val[MAXN];
struct node{
    int to,next;
}edge[MAXN<<1];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

int chk(){
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=head[i];j;j=edge[j].next){
            int v=edge[j].to;
            if(val[i]==val[v]) cnt++;
        }
        if(d[i]-cnt<half[i]) return i;
    }
    return 0;
}

signed main(){
    srand(time(0));
    read(n,m);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        build(u,v);
        build(v,u);
        d[u]++;d[v]++;
    }
    for(int i=1;i<=n;i++) half[i]=d[i]/2+(d[i]%2);
    for(int i=1;i<=n;i++) val[i]=rand()%2;
    int z=chk();
    while(z!=0){
        val[z]^=1;
        z=chk();
    }
    for(int i=1;i<=n;i++) cout<<(val[i]?'P':'S');
    return 0;
}