CF1682D Circular Spanning Tree 题解

KiloP · 2022-05-23 22:11:10 · 题解

首先观察一下，当给定的总度数和是奇数时，肯定不行。

又发现，当每个点的度数模 2 均为 0 时，肯定不是一棵树，也不行。

猜想：剩下的都可以，下面来构造。

分情况讨论（于此与原 CF 题解略有不同）

• 若每个点的度数均为奇数，那么此时 n 一定是偶数。

  那么我们就任选一点为根，连出一个菊花图即可。

• 否则，此时度数为奇数的点有偶数个，设为 k，此时，选一个度数为偶数的点为根。

  我们将根移除后的字符串以如下方式断开（将字符串认为是循环的）

  [0,0,\dots,1][0,0,\dots,1]\cdots[0,0,\dots,1]

  共 k 组

  从根连出 k 条链，每条链顺次连接上面一对方括号内的点，这样就能保证题目的条件满足。

下面说明这样构造的树没有其余交点。

首先，菊花图肯定是没有的。

来看后一种情况，此时，边只能分为两类：从根连出去的边和圆上相邻两个点之间的边。显然，两组边内部没有其他交点，而后者不可能与前者交于圆内部（画图理解下）。

这样这题就做完了，不懂的看代码吧（代码丑，不喜勿喷）。

#include<bits/stdc++.h>

template<typename _Ty> void __(_Ty &x) {
    bool neg = false;
    unsigned c = getchar();
    for (; (c ^ 48) > 9; c = getchar()) if (c == '-') neg = true;
    for (x = 0; (c ^ 48) < 10; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    if (neg) x = -x;
}
template<typename _Ty> _Ty& read(_Ty &x) { __(x); return x; }
template<typename _Ty, typename ..._Tr> void read(_Ty &x, _Tr&... r) { __(x); read(r...); }

using namespace std;

int main() {

    int t, n;
    string s;
    for (read(t); t--; ) {
        read(n);
        cin >> s; s = " " + s;
        int _0 = 0, _1 = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i] == '0') _0++;
            else _1++;
        }
        if (_1 % 2 != 0 || _1 == 0) {
            puts("NO");
            continue;
        }
        puts("YES");
        if (_0 == 0) {
            for (int i = 2; i <= n; ++i) cout << "1 " << i << endl;
        } else {
            int idx = 0;
            for (int i = 1; i <= n; ++i) if (s[i] == '0' && s[(i + n - 2) % n + 1] == '1') { idx = i; break; }
            int now = idx % n + 1;
            while (now != idx) {
                cout << idx << ' ' << now << endl;
                while(s[now] != '1') {
                    cout << now << ' ' << now % n + 1 << endl;
                    now = now % n + 1;
                }
                now = now % n + 1;
            }
        }

    }

    return 0;

}