E. Dasha and Puzzle 数学题

阅读原文时间：2023年07月13日阅读：1

http://codeforces.com/contest/761/problem/E

给出一颗树，要求在坐标系中用平行于坐标轴的线描绘出来。

要求边不能相交，而且点的坐标唯一。

注意到2^1 + 2^2 + ….. + 2^n = 2^（n + 1） - 1

那就是说，如果第一条边的边长是2^（n + 1），那么后面的边选2^n 、 2^(n - 1)等等，相加起来也不会越过第一条，所以也就不会相交。

#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include
#include
#include
#include
#include
#include
#include
#include
const int maxn = + ;
struct node {
int u, v, tonext;
} e[maxn * ];
int num;
int first[maxn];
void add(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
struct coor {
LL x, y;
coor(LL xx, LL yy) : x(xx), y(yy) {}
bool operator < (const struct coor & rhs) const { if (x != rhs.x) return x < rhs.x; else return y < rhs.y; } }; vectorans[maxn];
int tonext[][] = {{, }, {, }, {, -}, { -, }};
bool vis[maxn];
const LL one = ;
int haha[];
void dfs(int cur, LL x, LL y, int son, int pre) {
ans[cur].push_back(coor(x, y));
// aler.insert(coor(x, y));
vis[cur] = true;
int to = ;
for (int i = first[cur]; i; i = e[i].tonext) {
int v = e[i].v;
if (vis[v]) continue;
if (to == pre) to++;
if (to == ) to = ;
dfs(v, x + tonext[to][] * (one << son), y + tonext[to][] * (one << son), son - , haha[to]); to++; } } void work() { haha[] = ; haha[] = ; haha[] = ; haha[] = ; int n; scanf("%d", &n); for (int i = ; i <= n - ; ++i) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } for (int i = ; i <= n; ++i) { int t = -; for (int j = first[i]; j; j = e[j].tonext) { t++; } if (t >= ) {
// cout << t << endl;
cout << "NO" << endl;
return;
}
}
// LL y = 1 << 30;
// y <<= 2;
// cout << y << endl;
dfs(, , , , -);
cout << "YES" << endl;
for (int i = ; i <= n; ++i) {
// if (ans[i].size() == 0) {
// cout << i << "ffff" << endl;
// continue;
// }
cout << ans[i][].x << " " << ans[i][].y << endl;
}
}

int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章