Airlines — 2

Gym - 100113B


题意要时n个点之间的所有连边染色，使得不存在相同颜色的边组成一个奇环。
分治，对于一个n个点的，我们可以把它分为 (1, mid) (mid+1, n) 两部分，和二分图一样，并且两边相互连相同颜色的边，这样这种颜色的边肯定不存在奇环，然后对于两边再分别这样递归下去，最后答案是logn的。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 510;
int a[maxn][maxn], n, m, t;

void dfs(int l, int r, int c) {
    if (l == r) return;
    t = max(t, c);
    int mid = (l+r)/2;
    for (int i = l; i <= mid; i++)
        for (int j = mid+1; j <= r; j++) {
            a[i][j] = a[j][i] = c;
        }
    dfs(l, mid, c+1);
    dfs(mid+1, r, c+1);
}

int main() {
    freopen("avia2.in","r",stdin);
    freopen("avia2.out","w",stdout);

    scanf("%d", &n);
    t = 0;
    dfs(1, n, 1);
    printf("%d\n", t);
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j < n; j++) printf("%d ", a[i][j]);
        printf("%d\n", a[i][n]);
    }
}