http://codeforces.com/contest/1477
C. Nezzar and Nice Beatmap
题意:给定二维平面上 n 个点,要求排列,使得相邻三个点以中间的那个点为中心点构成的夹角为锐角。
构造
首先要发现对于三个点 A,B,C,如果此时不是锐角,则交换任意一对相邻点,变成 A,C,B 或者 B,A,C,都是锐角,因为三角形里最多只会有一个非锐角。
那么就可以在加入点的同时调整已有点。
例如已有 A,B,C,D,先直接加入 E,发现 C,D,E 为钝角,则调整为 A,B,C,E,D,此时又发现 B,C,E 为钝角,再调整为 A,B,E,C,D,又发现 A,B,E 为钝角,再调整为 A,E,B,C,D,这样一定就不会再有钝角了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e6 + 5; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; int n; struct X { ll x, y; int id; }; ll dot(X a, X b, X c) { return (b.x - a.x)*(b.x - c.x) + (b.y - a.y)*(b.y - c.y); } X a[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lld%lld", &a[i].x, &a[i].y); a[i].id = i; } for (int i = 3; i <= n; i++) { for (int j = i; j >= 3; j--) { if (dot(a[j - 2], a[j - 1], a[j]) <= 0)swap(a[j], a[j - 1]); } } for (int i = 1; i <= n; i++)printf("%d%c", a[i].id, " \n"[i == n]); return 0; }
|
D. Nezzar and Hidden Permutations
题意:给定 n,m,m 对数 (i,j),要求 (p[i]−p[j])⋅(q[i]−q[j])>0,要求构造出排列 p,q,在满足所有对数的情况下最大化 p[i]=q[i]。
构造
把 (i,j) 看作连接 i,j 的无向边。
首先能够发现,如果 u 的度为 n−1,则必定有 p[u]=q[u]。
再考虑一个集合,其中有一个点 x,满足与集合中其它点都没有连边,则可以构造出 p[x]=1,q[x]=n,其它点 p[1]=1,p[2]=2,⋯;q[1]=2,q[2]=3,⋯。
那么现在就需要构造出这样的集合。
对于一个点 x,且 x,y 没有连边。
若 y 还未在任何集合中,则直接开一个新的集合,放 x,y。
若 y 是它所在集合中那个与其他所有点都不连边的点,或者 y 所在集合只有两个点,则 x 也加入这个集合。
否则把 y 从原有集合中拿出来,新开一个集合,放 x,y。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e6 + 5; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; int T; int n, m; vector<int>G[N]; set<int>st[N]; int tot, key[N], id[N], p[N], q[N]; int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)G[i].clear(); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) { G[i].push_back(0); G[i].push_back(n + 1); G[i].push_back(i); sort(G[i].begin(), G[i].end()); } int base = 0; for (int i = 1; i <= n; i++) { if ((int)G[i].size() == n + 2) { p[i] = q[i] = ++base; continue; } if (id[i])continue; int y; for (int j = 1; j < (int)G[i].size(); j++) { if (G[i][j] != G[i][j - 1] + 1) { y = G[i][j - 1] + 1; break; } } if (!id[y]) { st[++tot].insert(i); st[tot].insert(y); id[i] = id[y] = tot; key[tot] = i; } else { if (key[id[y]] == y || st[id[y]].size() == 2) { key[id[y]] = y; st[id[y]].insert(i); id[i] = id[y]; } else { st[id[y]].erase(y); st[++tot].insert(y); st[tot].insert(i); id[i] = id[y] = tot; key[tot] = i; } } } for (int i = 1; i <= tot; i++) { int j = base + 1; for (int x : st[i]) { if (x == key[i]) { p[x] = base + (int)st[i].size(); q[x] = base + 1; } else { p[x] = j; q[x] = j + 1; j++; } } base += (int)st[i].size(); } for (int i = 1; i <= n; i++)printf("%d%c", p[i], " \n"[i == n]); for (int i = 1; i <= n; i++)printf("%d%c", q[i], " \n"[i == n]); for (int i = 1; i <= tot; i++)st[i].clear(); fill(key, key + tot + 1, 0); fill(id, id + n + 1, 0); tot = 0; } return 0; }
|