BZOJ-3244 [Noi2013]树的计数

n+e posted @ 2015年7月03日 21:51 in BZOJ with tags DP , 1004 阅读

首先先把 $bfs$ 序弄成 $1,2,\cdots ,n$,$dfs$ 序一起映射;

然后按照 $1,2,\cdots ,n$ 的顺序依次插入最终的树中

每个点的贡献独立,只可能是 $0,0.5,1$ 三种中的一种。

贡献 $1$:点 $i$ 与点 $i-1$ 不能在同一层内

贡献 $0.5$:点 $i$ 与点 $i-1$ 既能在同一层内,又能不在同一层内

贡献 $0$:其他情况

考虑当前插入的点 $i$:

如果 $i\le 2$,由于 $1,2$ 两个点的位置事先确定,直接强制令它们贡献均为 $1$

如果点 $i$  在 $dfs$ 序中的位置比 $i-1$ 的靠前,说明 $i$ 和 $i-1$ 一定不在同一层里,贡献为 $1$

如果点 $i$ 之前的所有点 $mark$ 到 $dfs$ 序上时,是从 $1$ 开始的连续一段到 $l$ 结束 + 从 $r$ 开始到 $n$ 结束的连续另一段,比如 $111100\cdots 001111$ (1),并且点 $i$ 要插入到 $l+1$ 这个位置 (2),并且点 $i$ 前面是点 $i-1$ (3),说明说点 $i$ 既可以当点 $i-1$ 的兄弟,又可以当儿子。

否则不贡献答案。

(1):如果不连续的话就不能交换了= =这样交换的话至少不会破坏前面已经插入的序列

(2)(3):两个点能交换当且仅当它们在 $bfs$ 序和 $dfs$ 序上都相邻

/**************************************************************
    Problem: 3244
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:3180 kb
****************************************************************/
 
#include<cstdio>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int F(){
    while(ch=getc(),ch<'0'||ch>'9');int aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 200010
int n,dfs[N],pos[N],ans,l=1,r,a[N];main(){
    n=r=F();
    for(int i=1;i<=n;i++)dfs[i]=F();
    for(int i=1;i<=n;i++)pos[F()]=i;
    for(int i=1;i<=n;i++)dfs[i]=pos[dfs[i]];
    for(int i=1;i<=n;i++)pos[dfs[i]]=i;
    for(int i=1;i<=n;i++){
        a[pos[i]]=1;
        if(i<=2||pos[i]<pos[i-1])ans+=2;
        else if(pos[i]==l&&i==n-r+l&&pos[i]==pos[i-1]+1)ans++;
        while(a[l])l++;while(a[r])r--;
    }
    printf("%.3lf\n%.3lf\n%.3lf\n",ans*.5-0.001,ans*.5,ans*.5+0.001);
}
---By n+e

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter