「Codeforces 1214E」Petya and Construction Set
题目传送门
题意
构造一个 \(2n-1\) 个节点的树，满足 \(\forall i\in [1,n] : dis(2i-1,2i)=d_i\)，\(dis(x,y)\) 表示树上 \(x\) 到 \(y\) 的距离，\(d_i\) 是给定的。
\(n\le 10^5\)
题解
将 \(d_i\) 从大到小排序，然后依次把所有奇数连成一条链（按对应的 \(d_i\) 从大到小的顺序）。
然后依次考虑链上每个点对应的偶数点的位置。假设这个点是链上第 \(k\) 个点，对应的 \(d_i\) 记为 \(D\)，那么显然只要把这个偶数点挂在链上第 \(k+D-1\) 个点下面即可。要注意的是，如果第 \(k+D-1\) 个点是链上最后一个点，那么再挂一个点要把链进行“扩充”。可以证明，在处理第 \(k\) 个点时，链上一定存在 \(k+D-1\) 个点（根据 \(d_i\) 从大到小进行证明）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <cstdio>
#include <cctype>
#include <algorithm>
int read(){
register int x = 0;
register char ch = getchar(), f = 1;
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
int n, cnt, id[100005];
std :: pair<int, int> d[100005];
int main(){
n = read();
for (register int i = 1; i <= n; ++i) d[i].first = -read(), d[i].second = i;
std :: sort(d + 1, d + 1 + n);
for (register int i = 1; i <= n; ++i){
if (i < n) printf("%d %d\n", 2 * d[i].second - 1, 2 * d[i + 1].second - 1);
int x = i - d[i].first - 1;
if (x <= n) printf("%d %d\n", 2 * d[x].second - 1, 2 * d[i].second);
else printf("%d %d\n", id[x - n], 2 * d[i].second);
if (x - n == cnt) id[++cnt] = 2 * d[i].second;
}
}
|
