【题解】AGC 005 C Tree Restoring

Problem

给定一个长度为 $n$ 序列 $a$,求是否有一棵树,使得节点 $i$ 和最远节点距离为 $a_i$

Thought

直径长度 $L=\max\{a_i\}+1$
然后距离为 $[L-1,(L+1)/2]$ 的点至少每个位置两个
当 $L$ 为奇数时, $L/2$ 有且仅有一个
当 $L$ 为偶数时, $L/2$ 有且仅有两个

剩下的就随意啦

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 110;
int n, L;
int num[N];
int main() {
    n = read();
    for(int i = 1; i <= n; ++ i) {
        int x = read();
        L = max(L, x + 1);
        ++ num[x];
    }
    bool flag = 1;
    for(int i = L - 1; i >= (L + 1) / 2 && flag; -- i)
        if(num[i] < 2)
            flag = 0;
    if(((L & 1) && num[L / 2] != 1) || (!(L & 1) && num[L / 2] != 2))
        flag = 0;
    puts(flag ? "Possible" : "Impossible");
    return 0;
}
Comments

添加新评论