【uoj122】 NOI2013—树的计数

时间：2023-03-08 18:19:07

http://uoj.ac/problem/122 (题目链接)

题意

　　给出一棵树的dfs序和bfs序，保证一定可以构成一棵树。问构成的树的期望深度。

Solution

　　这是一个悲伤的故事，我YY的东西挂了，最后打满了补丁，化简一下，就是跟llg一样的写法。←_←别理他。

　　本来很简单的一个东西，也许是我脑洞太大了→_→

代码

// uoj122

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=200010;

int vis[maxn],dfn[maxn],bfn[maxn],t[maxn],pos[maxn],n;

double ans;

int main() {

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",&dfn[i]);

	for (int i=1;i<=n;i++) scanf("%d",&bfn[i]),t[bfn[i]]=i;

	for (int i=1;i<=n;i++) dfn[i]=t[dfn[i]];

	for (int i=1;i<=n;i++) pos[dfn[i]]=i;

	ans=2;

	int l=2,r=n+1;

	vis[1]=1,vis[2]=1;

	for (int i=3;i<=n;i++) {

		if (pos[i-1]>pos[i]) ans++;

		if (pos[i-1]+1==pos[i] && r-l-1==n-i+1) ans+=0.5;

		vis[pos[i]]=1;

		while (vis[l+1]) l++;

		while (vis[r-1]) r--;

	}

	printf("%.3lf",ans);

	return 0;

}

相关文章