青木君特别喜欢数列和树，他觉得它们是世界上最美妙的事物。
有一天，神仙给了青木君一个长度为 n 的整数数列a。这让青木君特别想构造一棵美妙树。
美妙树的每条边长度都为1。而且美妙树有一个最重要的性质：对于每一个点i(1≤i≤n)，在树中离它距离最远的点与它的距离应恰好等于ai。
青木君想了想就秒掉了这题，他决定考考你：对于一个给定的序列，是否存在一棵美妙树？
2≤n≤100,1≤ai≤n−1
题解
首先根据这个序列我们可以很方便地求出直径。
然后我们把树的直径上的点删掉，即l,l−1,l−2,⋯,mid,mid+1,⋯,l−1,l，如果不存在那么一定是impossible。
然后还有就是不可能出现 a 比直径中点小的点，把它判掉就过了此题。
代码
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
| #include <cstdio>
#include <cctype>
#include <set>
#include <iostream>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int tong[maxn];
int main()
{
int n, zj = 0;
read(n);
for (int i = 1, a; i <= n; ++i)
{
read(a);
tong[a]++;
zj = max(a, zj);
}
for (int i = 0; i <= zj; ++i)
{
int noww = max(i, zj - i);
if (!tong[noww])
{
puts("Impossible");
return 0;
}
tong[noww]--;
}
for (int i = 1; i <= ((zj + 1) >> 1); ++i)
{
if (tong[i])
{
puts("Impossible");
return 0;
}
}
puts("Possible");
return 0;
}
|
