P9384 [THUPC 2023 决赛] 着色 题解

lyhqwq · 2023-11-13 16:37:08 · 题解

Solution

喵喵构造

我们考虑将三元环和五元环的限制增强，变为图中不存在颜色相同的奇环。

那么每种颜色都构成一个二分图。

接下来提供一种和其他题解不同的构造方法。

我们考虑分治，每次将当前所有点分成两部分，所有的点之间的边染上相同的颜色，然后递归两部分内部染下一种颜色。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
int a[N][N];
void solve(int l,int r,int o){
    if(l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid,o+1),solve(mid+1,r,o+1);
    for(int i=l;i<=mid;i++) for(int j=mid+1;j<=r;j++) a[i][j]=o;
}
int main(){
    scanf("%d",&n);
    solve(1,n,0);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++) printf("%d",a[i][j]);
        puts("");
    }
    return 0;
}