http://codeforces.com/contest/1477

C. Nezzar and Nice Beatmap

 

题意:给定二维平面上 nn 个点,要求排列,使得相邻三个点以中间的那个点为中心点构成的夹角为锐角。

构造

首先要发现对于三个点 A,B,C,如果此时不是锐角,则交换任意一对相邻点,变成 A,C,BA,C,B 或者 B,A,CB,A,C,都是锐角,因为三角形里最多只会有一个非锐角。

那么就可以在加入点的同时调整已有点。

例如已有 A,B,C,DA,B,C,D,先直接加入 EE,发现 C,D,EC,D,E 为钝角,则调整为 A,B,C,E,DA,B,C,E,D,此时又发现 B,C,EB,C,E 为钝角,再调整为 A,B,E,C,DA,B,E,C,D,又发现 A,B,EA,B,E 为钝角,再调整为 A,E,B,C,DA,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,mn,mmm 对数 (i,j)(i,j),要求 (p[i]p[j])(q[i]q[j])>0(p[i]-p[j])\cdot (q[i]-q[j])>0,要求构造出排列 p,qp,q,在满足所有对数的情况下最大化 p[i]q[i]p[i]\neq q[i]

构造

(i,j)(i,j) 看作连接 i,ji,j 的无向边。

首先能够发现,如果 uu 的度为 n1n-1,则必定有 p[u]=q[u]p[u]=q[u]

再考虑一个集合,其中有一个点 xx,满足与集合中其它点都没有连边,则可以构造出 p[x]=1,q[x]=np[x]=1,q[x]=n,其它点 p[1]=1,p[2]=2,;q[1]=2,q[2]=3,p[1]=1,p[2]=2,\cdots;q[1]=2,q[2]=3,\cdots

那么现在就需要构造出这样的集合。

对于一个点 xx,且 x,yx,y 没有连边。

yy 还未在任何集合中,则直接开一个新的集合,放 x,yx,y

yy 是它所在集合中那个与其他所有点都不连边的点,或者 yy 所在集合只有两个点,则 xx 也加入这个集合。

否则把 yy 从原有集合中拿出来,新开一个集合,放 x,yx,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;
}