题目链接: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; }
哈哈哈,妙妙构造:)
- Codeforces Circular Spanning 思维 Roundcodeforces circular spanning思维 树形codeforces思维round educational codeforces思维round educational codeforces multiset思维 educational codeforces思维 数学 codeforces规律 思维nonzero 数论codeforces思维 数学 educational codeforces round rated codeforces思维eriktse 2023 codeforces round 911 div