题目

http://codeforces.com/contest/902/problem/C

分析

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

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

只要将最后一个节点（即节点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; }

更多内容请关注微信公众号