社区讨论

刚学OI,不是女生,求dalao帮忙看

P3365改造二叉树参与者 13已保存回复 19

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
19 条
当前快照
1 份
快照标识符
@mi7cl52i
此快照首次捕获于
2025/11/20 19:28
4 个月前
此快照最后确认于
2025/11/20 21:57
4 个月前
查看原帖
CPP
#include<iostream> 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define il inline
#define MAXN 100005
il int fr(){
    rg int f=1,res=0;rg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return f*res;
}
using namespace std;
struct node{
    LL date;
    node *ls,*rs;
}tree[MAXN];
LL n;
LL fa,ch;
LL a[MAXN],f[MAXN],d[MAXN];
LL cnt=0,len;
il void  in(){
    n=fr();
    for(rg LL i=1;i<=n;++i)tree[i].date=fr();
    for(rg LL i=1;i<=n-1;++i){
        fa=fr();ch=fr();
        if(ch==0)tree[fa].ls=&tree[i+1];
        else tree[fa].rs=&tree[i+1];
    }
    return;
}
il void zxdfs(node *x){
    if(x!=NULL){
    zxdfs(x->ls);
    ++cnt;
    a[cnt]=x->date-cnt;
    zxdfs(x->rs);
    }
    return;
}
il LL erf(rg LL x){
    rg LL l=1,r=len,ans=0;
    while(l<=r){
        LL mid=(l+r)>>1;
        if(a[mid]<=x)ans=mid,l=mid+1;else r=mid-1;
    }
    return ans;
}
il void bxj(){
    for(rg int i=1;i<=n;++i){
        f[i]=erf(a[i])+1;
        d[f[i]]=a[i];
        len=len>f[i]?len:f[i];
    }
}
int main(){
    in(); 
    zxdfs(&tree[1]);
//	for(rg LL i=1;i<=n;++i)printf("%lld ",a[i]);
    bxj();
//	printf("%lld\n",len);
    printf("%lld",n-len);
    return 0;
}

回复

19 条回复,欢迎继续交流。

正在加载回复...