首页 > 代码库 > UOJ#122【NOI2013】树的计数

UOJ#122【NOI2013】树的计数

2024-09-29 19:39:02   219人阅读

【NOI2013】树的计数

链接：http://uoj.ac/problem/122

按BFS序来，如果$B_i$与$B_{i-1}$必须在同一层，那么贡献为0，必须在不同层那么贡献为1，都可以贡献为0.5。

因为$B_i$与$B_{i-1}$相邻，所以对方案数的改变最多+1.

  1. 必须在不同层，即$D(B_{i-1})>D(B_i)$
  2. 都可以，$B_i$能往下移一层，不改变BFS序以及DFS序：　　
    1. 作为兄弟，父亲必须一样(即$D(B_{i-1})==D(B_i)-1$)，不然会改变DFS序.
    2. 作为儿子，该层当前不能有其他点。等价于$\{D(B_{1..i-1})\}=B\{[1...L]∪[R..N]\}$,意味着一部分在x属于前面，后面是深度都小于x的。中间的其实就是x的子树

剩下代码就很简单了。

#include<cstdio>typedef long long ll;template<class T>inline void read(T&x){    x=0;bool f=0;char c=getchar();    while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar();    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    x=f?-x:x;}const int MAXN(200010);int B[MAXN],D[MAXN],n,D_num[MAXN],l,r,B_num[MAXN];bool bf[MAXN];double Ans;int main(){    freopen("C.in","r",stdin);    freopen("C.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&D[i]);    for(int i=1;i<=n;i++)scanf("%d",&B[i]),B_num[B[i]]=i;    for(int i=1;i<=n;i++)D[i]=B_num[D[i]],D_num[D[i]]=i;    Ans=2;bf[D_num[1]]=bf[D_num[2]]==1;l=2;r=n+1;    for(int i=3;i<=n;i++)    {        if(D_num[i-1]>D_num[i])Ans+=1;        else         if(D_num[i-1]==D_num[i]-1&&n-r+1+l==i-1)        {            Ans+=0.5;        }        bf[D_num[i]]=1;        while(bf[l+1])l++;        while(bf[r-1])r--;    }    printf("%.3lf",Ans);    return 0;}

 

UOJ#122【NOI2013】树的计数


联系
我们