题目
题目链接:https://www.luogu.com.cn/problem/P1232
我们知道一棵有根树可以进行深度优先遍历(DFS)以及广度优先遍历(BFS)来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同,并且它们的 BFS 序也有可能相同,例如下面两棵树的 DFS 序都是 1 2 4 5 3
,BFS 序都是 1 2 3 4 5
。
现给定一个 DFS 序和 BFS 序,我们想要知道,符合条件的有根树中,树的高度的平均值。即,假如共有 (K) 棵不同的有根树具有这组 DFS 序和 BFS 序,且他们的高度分别是 (h_1, h_2, ldots, h_K),那么请你输出:
[frac{h_1+h_2+ldots+h_K}K
]
(nleq 2 imes 10^5)。
思路
同一深度的点在 BFS 序上肯定是连续的一个区间。所以其实就是求 BFS 序上可以分成的段数的期望 (+1)。
利用期望的线性性,分别考虑 BFS 序相邻的两个点之间是必须分段 / 可以分段 / 不能分段。必须分段贡献是 (1),可以分段贡献是 (0.5),不能分段贡献是 (0)。
- 必须分段:如果 BFS 序相邻的两个点 (i,j) 满足 (i) 的 DFS 序小于 (j) 的 DFS 序,那么 (i,j) 之间可以不分段。转化为逆否命题,如果 BFS 序相邻的两个点之间必须分段,那么一定有 (i) 的 DFS 序大于 (j) 的 DFS 序。
- 不能分段:考虑 DFS 序对 BFS 序是否分段的影响。如果 DFS 序相邻的两个点 (i,j)(那么有 ( ext{dep}_jleq ext{dep}_i+1)),满足 (i) 的 BFS 序小于 (j) 的 BFS 序(那么有 ( ext{dep}_jgeq ext{dep}_i)),那么 ( ext{dep}_ileq ext{dep}_jleq ext{dep}_i+1)。也就是 BFS 序上 (i) 到 (j) 这一段区间中,最多有一个位置必须分段。所以在求出所有必须分段的位置后,如果这一段区间之间存在一个必须分段的位置,那么这一段区间剩余的所有位置都不能分段。
可以利用差分来标记每一个位置是否不能分段。
时间复杂度 (O(n))。
其实我没太搞懂为什么这样是充分的。只能感性理解一下。题解区似乎也没有比较完整的证明。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,id1[N],rk1[N],id2[N],rk2[N],a[N],b[N];
double ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&id1[i]),rk1[id1[i]]=i;
for (int i=1;i<=n;i++)
scanf("%d",&id2[i]),rk2[id2[i]]=i;
for (int i=1;i<n;i++)
b[i]=b[i-1]+(rk1[id2[i]]>rk1[id2[i+1]] || i==1);
for (int i=1;i<n;i++)
if (rk2[id1[i]]<rk2[id1[i+1]] && b[rk2[id1[i+1]]-1]-b[rk2[id1[i]]-1])
a[rk2[id1[i]]]++,a[rk2[id1[i+1]]]--;
for (int i=1;i<n;i++)
{
a[i]+=a[i-1];
if (b[i]-b[i-1]) ans+=1;
if (!a[i]) ans+=0.5;
}
printf("%.3lf",ans+1);
return 0;
}