小朋友学Codeforces（4）：Round 453 DIV 2, C

一时失言乱红尘 2022-05-31 09:42 125阅读 0赞

# 题目 #

[http://codeforces.com/contest/902/problem/C][http_codeforces.com_contest_902_problem_C]

# 分析 #

只要满足两个条件，即存在同构树：  
①该节点上一层的节点数大于1，  
②该节点所在层节点个数大于1。

以例2中的\{1,2,2\}为例：

![C.png][]

只要将最后一个节点（即节点5），放到上一层的倒数第二个节点（即结点2）下，就形成了两棵同构树。

# 代码 #

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 200001;
    
    int main()
    {
        int height;     // 树的高度 = 层数 - 1 
        int cnt[N];     // 每一层的节点总数 
        int parent = 0; // 根结点为1，其父节点为0 
        bool flag = 1;
    
        cin >> height;
        for(int layer = 0; layer <= height; layer++)
        {
            cin >> cnt[layer];
            if(layer == 0) 
            {
                continue;
            }
    
            if(cnt[layer - 1] != 1 && cnt[layer] != 1)
            {
                flag = 0;
            }
        }
    
        if(flag)
        {
            puts("perfect");
            return 0;
        }
    
        puts("ambiguous");
    
        for(int layer = 0; layer <= height; layer++)
        {
            // 输出该层节点的父节点 
            for(int node = 1; node <= cnt[layer]; node++)
            {
                cout << parent << " ";
            }
    
            // 父节点指向该层的最右的那个节点 
            parent += cnt[layer];
        }
    
        printf("\n");
    
        parent = 0;
        for(int layer = 0; layer <= height; layer++)
        {
            if(layer != 0 && cnt[layer - 1] != 1 && cnt[layer] != 1)
            {
                // 前n-1个节点的父节点还是原样输出 
                for(int node = 1; node <= cnt[layer] - 1; node++)
                {
                    cout << parent << " ";
                }
    
                // 最后节点的父节点往左移一个位置 
                cout << parent - 1 << " ";
                parent += cnt[layer];
                continue; 
            }
    
            for(int node = 1; node <= cnt[layer]; node++)
            {
                cout << parent << " ";
            }
    
    
            parent += cnt[layer];
        }
    
        return 0;
    }

> 更多内容请关注微信公众号  
> ![wechat.jpg][]

[http_codeforces.com_contest_902_problem_C]: http://codeforces.com/contest/902/problem/C
[C.png]: /images/20220531/8fb68b4513d240429314501267b54a7c.png
[wechat.jpg]: /images/20220531/ac5c2766de6940869e5499990e4560de.png