自动搬运

查看原文

来自洛谷，原作者为

	lyhqwq D

搬运于2025-08-24 22:47:52，当前版本为作者最后更新于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;
}