[UOJ#122][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

输入

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

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

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

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

输出

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

输入示例





输出示例




3.500




数据规模及约定


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


题解


首先自己 YY 了一个 90 分的做法。


我们给树重标号，使得它的 DFS 序变成 1~n（BFS 序也随之改变）。


那么在这里发现：如果 BFS 序中两个数 i 和 i+1，i+1 的位置在 i 后面，并且 i 和 i+1 不相邻，那么意味着 i+1 一定是 i 的儿子（性质1），并且在 BFS 序中，处在 i 和 i+1 位置中间的节点要么是 i 的兄弟并且在 i 的右边，要么是 i+1 的兄弟并且不是 i 的儿子并且在 i+1 的左边（这里的左右指的是树上同一层节点的左右关系）。


然后，对于 BFS 序中相邻两个数 B[i] 和 B[i+1]，如果 B[i] > B[i+1] 那么，节点 B[i] 和 B[i+1] 一定在不同层，更确切地，B[i+1] 在 B[i] 的下一层（因为会先 DFS 到 B[i] 这个节点）。（性质2）


注意到如果我们给每个节点确定了深度，树的形态一定确定了。


给个例子：


DFS 序：1 2 3 4 5 6 7 8 9


BFS 序：1 2 6 7 3 4 5 8 9


那么发现 (2, 3) 和 (7, 8) 这两对数满足性质1，(B[4]=7, B[5]=3) 这对数满足性质2。


那么我们怎么给它们安排深度呢？注意到深度按照 BFS 序排列从左往右是不下降的。


节点 1 深度一定是 1，节点 2 深度一定为 2；由 (2, 3) 和 (B[4]=7, B[5]=3) 这两个条件知道节点 6 和 7 深度都是 2，节点 3 的深度为 3；由 (7, 8) 得知节点 8 深度为 3，那么节点 4 和 5 的深度也就自然都是 3 了；节点 9 的深度无所谓，可以是 3 或者 4。


深度序列：1 2 2 2 3 3 3 3 (3 or 4)


差分一下这个序列，即 dep[i] = dep[i+1] - dep[i]（舍去最后一个位置的数），得到：1 0 0 1 0 0 0 (0 or 1)


于是问题变成了，在这个差分后的新序列中，给每个位置上确定 0 或 1，有些位置上必须是 1，然后有一些区间，每个区间内的 1 的个数不能多于 1，求期望有多少个 1。


在这个例子中，必须填 1 的位置是 1 和 4，区间为 [2, 4] 和 [4, 7]。


那么就可以 dp 了。f[i] 表示考虑前 i 个位置，并且第 i 位填 1 的方案数；g[i] 表示考虑前 i 个位置，第 i 为填 1 的所有方案中 1 的个数之和；那么 f[i] 和 g[i] 都可以从【上一个必填 1 的位置】到【包含位置 i 的所有区间中最小的左端点 - 1】这一段区间中转移过来，线段树维护即可。如果 f 和 g 都用 long double，可以蹭到 90 分。




#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 200010

#define double long double

#define pdd pair <double, double>

int n, dfn[maxn], bfn[maxn], id[maxn], pos[maxn];

bool tag[maxn];

vector <int> add[maxn], del[maxn];

priority_queue <int> Q, delQ;

int lft[maxn];

void Addi(int l, int r) {

	add[l].push_back(l); del[r+1].push_back(l);

	return ;

}

double sf[maxn<<2], sumv[maxn<<2];

void update(int o, int l, int r, int x, double f, double v) {

	if(l == r) sf[o] = f, sumv[o] = v;

	else {

		int mid = l + r >> 1, lc = o << 1, rc = lc | 1;

		if(x <= mid) update(lc, l, mid, x, f, v);

		else update(rc, mid + 1, r, x, f, v);

		sf[o] = sf[lc] + sf[rc];

		sumv[o] = sumv[lc] + sumv[rc];

	}

	return ;

}

pdd query(int o, int l, int r, int ql, int qr) {

	if(ql > qr) return make_pair(0.0, 0.0);

	if(ql <= l && r <= qr) return make_pair(sf[o], sumv[o]);

	int mid = l + r >> 1, lc = o << 1, rc = lc | 1;

	pdd ans = make_pair(0.0, 0.0), tmp;

	if(ql <= mid) tmp = query(lc, l, mid, ql, qr), ans.first += tmp.first, ans.second += tmp.second;

	if(qr > mid) tmp = query(rc, mid + 1, r, ql, qr), ans.first += tmp.first, ans.second += tmp.second;

	return ans;

}

int main() {

	n = read();

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

	for(int i = 1; i <= n; i++) bfn[i] = id[read()], pos[bfn[i]] = i;

//	for(int i = 1; i <= n; i++) printf("%d%c", bfn[i], i < n ? ' ' : '\n');

	tag[1] = 1;

	for(int i = 2; i < n; i++) if(bfn[i] > bfn[i+1]) tag[i] = 1;

	for(int i = 1; i <= n; i++) if(pos[bfn[i]+1] > i + 1) Addi(i, pos[bfn[i]+1] - 1);

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

		for(int j = 0; j < del[i].size(); j++) {

			delQ.push(-del[i][j]);

			while(!Q.empty() && Q.top() == delQ.top()) Q.pop(), delQ.pop();

		}

		for(int j = 0; j < add[i].size(); j++) Q.push(-add[i][j]);

		if(Q.empty()) lft[i] = i; else lft[i] = -Q.top();

	}

//	for(int i = 1; i <= n; i++) printf("%d%c", lft[i], i < n ? ' ' : '\n');

	int lst = 1;

	update(1, 1, n, 1, 1, 1);

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

		pdd info = query(1, 1, n, lst, lft[i] - 1);

		update(1, 1, n, i, info.first, info.first + info.second);

//		printf("%d: %.3lf %.3lf\n", i, info.first, info.first + info.second);

		if(tag[i]) lst = i;

	}

	double Sumv = 0, Sf = 0;

	for(int i = n - 1; i; i--) {

		pdd info = query(1, 1, n, i, i);

		Sf += info.first; Sumv += info.second;

//		printf("record: %d %.3lf\n", i, info.second);

		if(tag[i]) break;

	}

	printf("%.3Lf\n", (Sumv + Sf) / Sf);

	return 0;

}





更简单的做法就是让 BFS 序变成 1~n 的排列，DFS 序随之变化，然后分情况讨论节点 i 和 i-1 必定不在同一层，可以在同一层也可以不在同一层，必定在同一层，贡献分别是 1、0.5 和 0。


以下省略条件：对于节点 i 和节点 i-1。令 pos[i] 表示节点 i 在 DFS 序中的位置。


必定不在同一层：节点 i 必定在 i-1 的下一层，需要满足 pos[i] < pos[i-1]，即先 DFS 到节点 i；


可以在同一层，也可以不在：pos[i] = pos[i-1] + 1，并且如果节点 i 放在了节点 i-1 那一层，则节点 i 是当前层的最靠右的节点，即 pos[1], pos[2], ... , pos[i-1] 标记上了 DFS 序中的开头和结尾；


必定在同一层：其余情况。


并查集判判就好了。




#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 200010

int n, dfn[maxn], bfn[maxn], id[maxn], pos[maxn], fa[maxn], siz[maxn];

int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }

int main() {

	n = read();

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

	for(int i = 1; i <= n; i++) id[bfn[i] = read()] = i;

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

	double sum = 0;

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

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

		if(i == 1 || i == 2) sum++;

		else if(pos[i] < pos[i-1]) sum++;

		else if(pos[i] == pos[i-1] + 1 && siz[findset(1)] + siz[findset(n)] == i - 1) sum += 0.5;

		siz[pos[i]] = 1;

		int u = findset(pos[i]), v;

		if(pos[i] > 1) {

			v = findset(pos[i] - 1);

			if(siz[v]) fa[v] = u, siz[u] += siz[v];

		}

		if(pos[i] < n) {

			v = findset(pos[i] + 1);

			if(siz[v]) fa[v] = u, siz[u] += siz[v];

		}

	}

	printf("%.3lf\n", sum);

	return 0;

}



												


																

最新文章
	

    
						
  1. MySQL免安装的配置
		
    2. 
						
  2. 正确获得android设备的IP地址
		
    3. 
						
  3. windows上安装使用mySql
		
    4. 
						
  4. 【Android】自定义控件让TextView的drawableLeft与文本一起居中显示
		
    5. 
						
  5. 233. Number of Digit One  *HARD* -- 从1到n的整数中数字1出现的次数
		
    6. 
						
  6. 如何为libs目录下的jar包关联源代码
		
    7. 
						
  7. Android和WCF通信 - 大数据压缩后传输
		
    8. 
						
  8. i++与++i的误解
		
    9. 
						
  9. 文本阴影text-shadow
		
    10. 
						
  10. 物联网操作系统HelloX V1.77（beta）版本发布
		
    11. 
						
  11. java中synchronized使用方法
		
    12. 
						
  12. Server Tomcat v7.0 Server at localhost was unable to start within 45 seconds解
		
    13. 
						
  13. 我的TDD实践---SVN架设篇
		
    14. 
						
  14. redis配置密码认证
		
    15. 
						
  15. UTF编码检测
		
    16. 
						
  16. 数据调试~~TCP转串口、串口转TCP调试
		
    17. 
						
  17. Codeforces Round #207 (Div. 1)    A. Knight Tournament  （线段树离线）
		
    18. 
						
  18. MongoDB使用优化
		
    19. 
						
  19. angular ng-repeat中DOM的重新渲染机制（项目中遇到问题）
		
    20. 
						
  20. PLSQL Developer是什么？
		
    21. 
		

	


热门文章
	

    
									
  1. Android adb命令，linux中各种命令
			
    2. 
						
  2. IOSButton自定义
			
    3. 
						
  3. Selenium私房菜系列9 -- Selenium RC服务器命令行参数列表【ZZ】
			
    4. 
						
  4. 浅谈table和DIV网页布局
			
    5. 
						
  5. NumPy库的基本使用
			
    6. 
						
  6. POJ 2955  Brackets  （区间DP，常规）
			
    7. 
						
  7. eclipse报错MA
			
    8. 
						
  8. python 基础网络编程2
			
    9. 
						
  9. （转）MyBatis框架的学习(三)——Dao层开发方法
			
    10. 
						
  10. 77 最长公共子序列 (lintcode)
			
    11.