BZOJ-3244 [Noi2013]树的计数

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

首先先把 $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
home cleaning servic 说:
2021年8月01日 21:27

This is how Fantastic Detergents work: You reveal all about your expections and i will handle the other parts - while guaranteed close of tenancy maintaining, expert carpet cleaning service, professional oven valeting, upholstery good care, commercial home office cleaning and a lot more! We might send special professionals straight away to your destination in Dubai. Cleaning execs will whole each and even all things with persistance while taking your current requirements inside full awareness.


登录 *


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