PAT 甲级 1116-1119

1116 Come on! Let’s C (20分)

简单特判

1117 Eddington Number (25分)

题意有误，应该是大于等于$E$天，排序二分即可。

1118 Birds in Forest (25分)

并查集大水题，注意查询时用$find()$不要用$s[]$数组。

1119 Pre- and Post-order Traversals (30分)

已知前序，后序求中序，不唯一的情况就是一个结点只有一个子树。

因此可以每次在前序中查找后序的倒数第二个结点，该结点就是子树的根，如果根只有该一个子树的话，可以默认为是右子树进行递归。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,pre[N],post[N],in[N],id;
bool f=true;
void inorder(int l1,int r1,int l2,int r2){
    if(l1==r1){
        in[++id]=pre[l1];return;
    }
    if(pre[l1]==post[r2]){
        int i=l1+1;
        while(i<=r1&&pre[i]!=post[r2-1]) i++;
        if(i-l1>1) inorder(l1+1,i-1,l2,l2+i-l1-2);
        else f=false;
        in[++id]=post[r2];
        inorder(i,r1,l2+i-l1-1,r2-1); 
    }
}
int main(){
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&pre[i]);
    for(int i=1;i<=n;i++) scanf("%d",&post[i]);
    inorder(1,n,1,n);puts(f?"Yes":"No");printf("%d",in[1]);
    for(int i=2;i<=n;i++) printf(" %d",in[i]);printf("\n");
    return 0;
}