luogu 1232 [NOI2013]树的计数

题目描述

能评测了哦。

我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的DFS序以及BFS序。两棵不同的树的DFS序有可能相同，并且它们的BFS序也有可能相同，例如下面两棵树的DFS序都是1 2 4 5 3，BFS序都是1 2 3 4 5

现给定一个DFS序和BFS序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有K棵不同的有根树具有这组DFS序和BFS序，且他们的高度分别是h1,h2,...,hk，那么请你输出

(h1+h2..+hk)/k

输入格式

输入文件count.in共有3行。

第一行包含1个正整数n，表示树的节点个数。

第二行包含n个正整数，是一个1~n的排列，表示树的DFS序。

第三行包含n个正整数，是一个1~n的排列，表示树的BFS序。

输入保证至少存在一棵树符合给定的两个序列。

输出格式

输出文件count.out仅包含1个实数，四舍五入保留恰好三位小数，表示树高的平均值。

输入输出样例

输入 #1

5 
1 2 4 5 3 
1 2 3 4 5

输出 #1

3.500

说明/提示

【评分方式】

如果输出文件的答案与标准输出的差不超过0.001，则将获得该测试点上的分数，否则不得分。

【数据规模和约定】

20%的测试数据，满足：n≤10；

40%的测试数据，满足：n≤100；

85%的测试数据，满足：n≤2000；

100%的测试数据，满足：2≤n≤200000。

【说明】

树的高度：一棵有根树如果只包含一个根节点，那么它的高度为1。否则，它的高度为根节点的所有子树的高度的最大值加1。

对于树中任意的三个节点a , b , c ，如果a, b都是c的儿子，则a, b在BFS序中和DFS序中的相对前后位置是一致的，即要么a都在b的前方，要么a都在b的后方。

【时间限制】

1s 【空间限制】

256000KB

分析

很妙的一道思维题

题解1

题解2

去luogu题解搜就好

从dfs序与bfs序充分考虑是否会对答案贡献

 1 /**************************
 2 User：Mandy.H.Y
 3 Language:c++
 4 Problem： 
 5 **************************/
 6 
 7 #include<bits/stdc++.h>
 8 
 9 using namespace std;
10 
11 const int maxn = 2e5 + 5;
12 
13 int n;
14 double ans;
15 int dfn[maxn],bfn[maxn],pos[maxn];
16 int sum[maxn];
17 
18 template<class T>inline void read(T &x){
19     x = 0;bool flag = 0;char ch = getchar();
20     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
21     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
22     if(flag) x = -x;
23 }
24 
25 template<class T>void putch(const T x){
26     if(x > 9) putch(x / 10);
27     putchar(x % 10 | 48);
28 }
29 
30 template<class T>void put(const T x){
31     if(x < 0) putchar('-'),putch(-x);
32     else putch(x);
33 }
34 
35 void file(){
36     freopen("1232.in","r",stdin);
37     freopen("1232.out","w",stdout);
38 }
39 
40 void readdata(){
41     read(n);
42     for(int i = 1;i <= n; ++ i) read(dfn[i]);
43     for(int i = 1;i <= n; ++ i) read(bfn[i]),pos[bfn[i]] = i;
44     for(int i = 1;i <= n; ++ i) dfn[i] = pos[dfn[i]];
45     for(int i = 1;i <= n; ++ i) pos[dfn[i]] = i;
46     //pos[i]为i的dfs序
47     //dfn[i]是dfs序为i的节点 
48 }
49 
50 void work(){
51     sum[1]++,sum[2]--;ans = 1.0;
52     for(int i = 1;i < n; ++ i){
53         if(pos[i] > pos[i+1]) ans++,sum[i]++,sum[i+1]--; 
54         if(dfn[i] < dfn[i+1] - 1) sum[dfn[i]]++,sum[dfn[i+1]]--;
55     }
56     int cur = 0;
57     for(int i = 1;i < n; ++ i) cur += sum[i],ans += (cur ? 0 : 0.5);
58     printf("%.3lf",ans+1);//深度 = 分的段数 + 1 
59 }
60 
61 int main(){
62 //    file();
63     readdata();
64     work();
65     return 0;
66 }

View Code