【Codeforces Round #453 (Div. 2) C】 Hashing Trees

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

显然只有当a[i]和a[i-1]都大于1的时候才会有不同的情况。
a[i] >= a[i-1] 且a[i-1]>=2
则第i-1层的a[i-1]个节点,每个节点下面接一个第i层的节点.
然后剩下的a[i]-a[i-1]个都放在第i-1层最左边那个节点下面。
另外一颗树,所有节点都放在第i-1层最左边那颗下面。
如果a[i]2且a[i]>=2
同样的,在第i-1层的前a[i]个节点下面各接一个节点。
然后另外一棵树,第i-1层只在最左边那个节点接

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int a[N+50],h;

vector <int> tree[2];

void GetTrees(int idx){

    tree[0].push_back(0);

    tree[1].push_back(0);

    int pre1 = 1,pre2 = -1,now = 1;

    for (int i = 2;i <= idx-1;i++){

        for (int j = 1;j <= a[i];j++){

            tree[0].push_back(pre1);

            tree[1].push_back(pre1);

        }

        int cnt = 0;

        for (int j = 1;j <= a[i];j++){

            now++;cnt++;

            if (cnt==1) pre1 = now;

            if (cnt==2) pre2 = now;

        }

    }

    for (int i = 1;i <= a[idx];i++){

        if (i&1) {

            tree[0].push_back(pre1);

        }else tree[0].push_back(pre2);

        tree[1].push_back(pre1);

    }

    for (int i = 1;i <= a[idx];i++){

        now++;

        pre1 = now;

    }

    for (int i = idx+1;i <= h;i++){

        for (int j = 1;j <= a[i];j++){

            tree[0].push_back(pre1);

            tree[1].push_back(pre1);

        }

        for (int j = 1;j <= a[i];j++){

            now++;

            pre1 = now;

        }

    }

    for (int x:tree[0]){

        cout << x <<' ';

    }

    cout << endl;

    for (int x:tree[1]){

        cout << x <<' ';

    }

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> h;h++;

    for (int i = 1;i <= h;i++) cin >> a[i];

    for (int i = 2;i <= h;i++)

        if (a[i]>=2 && a[i-1]>=2){

            cout << "ambiguous" << endl;

            GetTrees(i);

            return 0;

        }

    cout <<"perfect"<<endl;

	return 0;

}