[UOJ#122][NOI2013]树的计数

发布时间:2017-7-9 7:05:19编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[UOJ#122][NOI2013]树的计数 ",主要涉及到[UOJ#122][NOI2013]树的计数 方面的内容,对于[UOJ#122][NOI2013]树的计数 感兴趣的同学可以参考一下。

[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 个正整数,是一个 1n 的排列,表示树的 DFS 序。

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

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

输出

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

输入示例

51 2 4 5 31 2 3 4 5

输出示例

3.500

数据规模及约定

100% 的测试数据,满足:2n200000

题解

首先自己 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 200010int 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;}


上一篇:抽象工厂
下一篇:类818tu.com小说微信二级分销系统开发,源码下次分析

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款