构造+bfs，CF 761E - Dasha and Puzzle

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

761E - Dasha and Puzzle

---

二、解题报告

1、思路分析

如果一个点的度 > 4，那么无解

注意到 平面很大——1e18，而点数 & 边数很小

我们像玩贪吃蛇那样蛇形顺时针内卷的走，如何保证走n - 1次得到的边都不交叉？

我们可以让第一根很长，后面依次减半

基于上面的策略，我们可以这样构造：

从0开始bfs 往外向邻接点伸边，每条边长度为 2^28

第二层的点分别向临界点伸边，每条边长度为 2^27，只要方向不往回走，就不会交叉

……

这样就完成了构造

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;constexpr int N = 2E5;void solve() {int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1, u, v; i < n; ++ i) {std::cin >> u >> v;-- u, -- v;adj[u].push_back(v);adj[v].push_back(u);if (adj[u].size() == 5 || adj[v].size() == 5) {std::cout << "NO\n";return;}}std::vector<bool> vis(n);std::vector<std::pair<int, int>> ans(n);ans[0] = {0, 0};vis[0] = true;constexpr int dir[]{ -1, 0, 1, 0, -1 };std::queue<std::tuple<int, int, int>> q;q.emplace(0, -1, 1 << 29);while (q.size()) {auto [u, d, len] = q.front();q.pop();len /= 2;int curd = 0;for (int v : adj[u]) {if (vis[v]) continue;if (curd == d)++ curd;int x = ans[u].first + dir[curd] * len, y = ans[u].second + dir[curd + 1] * len;ans[v] = {x, y};vis[v] = true;q.emplace(v, curd ^ 2, len);++ curd;}}std::cout << "YES\n";for (auto &[x, y] : ans)std::cout << x << ' ' << y << '\n';}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}