526互联

Codeforces Round 793 (Div. 2)D. Circular Spanning Tree（图论，思维，构造）

发布时间 2023-08-30 10:29:35作者: XiCen

题目链接：https://codeforces.com/contest/1682/problem/D

 

题意：

 

给n个点，围成一个圈，你可以添加 n - 1条边使他成为一棵树，限制条件如下：

 

1：给长度为n的字符串，字符集为 0 和 1，对于 第i个字符，如果是1，表示第i个点的度数为奇数，反之为偶数；

 

2：边不能相交；

 

现在让你给出构造方案，如果不能构造，输出“NO”

 

分析：

 

我们分析，什么时候这棵树一定可以构造出来；

 

1：树都是有叶子的，故没有奇数的就 一定不行；

 

2：考虑一棵树是由一条条线段组成，一开始，一条线段有俩个奇数；

 

如果俩条线段是端点相连，那么结果还是俩个奇数；

 

如果一条线段连在另一线段中间，那么会变成4个奇数；

 

综上：如果没有奇数  或  奇数的个数是奇数个，那么无解；

 

现在我们来构造：

 

如果全部都是1，那么我们把n - 1个点连到第一个点上即可；

 

否则一定会有一个0，我们选取1相邻的一个0：

 

对于每个1，我们以他为头，依次把后面的0串起来，到最后一个0 的时候，我们把那个0的下一端连到上面我们选取那个0 那里，因为会有偶数个1，所以会有偶数个线段和0相连，是符合条件的；

 

时间复杂度：O（n）

 

代码：

 

#include<bits/stdc++.h>

int main()
{
    std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    int T; std::cin >> T;
    while (T--)
    {
        int n; std::cin >> n;
        std::string s; std::cin >> s;s += s[0];
        int cnt = 0;
        for (int i = 0; i < n; ++i)cnt += (s[i] - '0');
        if (!cnt || cnt % 2) { std::cout << "NO\n"; continue; }
        std::vector<std::pair<int, int>>ans;
        int st = 0;
        for (int i = 0; i < n; ++i)if (s[i] == '0' && s[i + 1] == '1') { st = i; break; }
        for (int i = (st + 1) % n; i != st; i = (i+1)%n)
        {
            int mid = (i + 1) % n;
            while (s[mid] == '0')ans.push_back(std::make_pair((mid - 1 + n) % n + 1, mid + 1)), mid = (mid + 1) % n;
            mid = (mid - 1 + n) % n;
            if (mid == st)break; else ans.push_back(std::make_pair(mid + 1, st + 1)); i = mid;
        }
        std::cout << "YES\n";
        for (auto& [x, y] : ans)std::cout << x << " " << y << "\n";
    }

    return 0;
}

哈哈哈，妙妙构造：）