[AGC032B] Balanced Neighbors 题解

考虑先写个暴力 \(O(n2^m)\) 的输出一下结果，看一下 n = 4, 5, 6 的（尤其是 n = 6 的）结果，尤其是每个点像其余哪几个点连边，然后就想到了构造方案。

代码

const int N = 109;
int n;
int e[N][N];

void skymaths() {
    read(n);
    if (n % 2 == 0) {
        rep (i, 1, n) {
            e[i][n + 1 - i] = 1;
        }
    } else {
        rep (i, 1, n - 1) {
            e[i][n - i] = 1;
        }
    }

    vector <pii> E;
    rep (i, 1, n) {
        rep (j, i + 1, n) {
            if (!e[i][j]) {
                E.eb(i, j);
            }
        }
    }

    int deg[101]; clr(deg);
    for (pii e : E) {
        deg[e.fi] += e.se;
        deg[e.se] += e.fi;
    }
    rep (i, 2, n) if (deg[i] != deg[i - 1]) assert(0);

    printf("%llu\n", E.size());
    for (pii e : E) {
        printf("%d %d\n", e.fi, e.se);
    }
}