BS-2293 Violet Cubes 题解
这是一道站外题题解。
Problem
给一张
数据范围:
Solution
不难发现答案
否则答案
一个显然的暴力就是先随便染色,每次找一个不满足条件的点并反转颜色直到所有点都满足条件。
可以证明,这个暴力是正确的。我们需要证明它在一定步数内结束,不会无限循环。
常见的套路是,找到一个量,使得它有上界且在算法过程中单调递增。
观察到,在上述算法中反转一个点,一定使异色边的数量严格增加。这启发我们设
Code
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define per(i,a,b) for(int i(a);i>b;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define eb emplace_back
using namespace std;
constexpr int N=5005;
int n,m,d[N],c[N];
vector<int> g[N];
// c[i]:i的颜色,0/1
// d[i]:和i相邻且颜色为1的点数
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
if(!m){
cout<<"1\n";
rept(i,1,n) cout<<"1 ";
return 0;
}
rep(_,0,m){
int u,v;
cin>>u>>v;
g[u].eb(v),g[v].eb(u);
}
rep(_,0,m){
bool f=false;
rept(i,1,n){
if(c[i]&&d[i]*2>g[i].size()||!c[i]&&(g[i].size()-d[i])*2>g[i].size()){
for(int j:g[i]){
d[j]-=c[i];
d[j]+=!c[i];
}
c[i]^=1;
f=true;
}
}
if(!f) break;
}
cout<<"2\n";
rept(i,1,n){
cout<<c[i]+1<<' ';
}
return 0;
}