首页 > 代码库 > UOJ #122 【NOI2013】 树的计数
UOJ #122 【NOI2013】 树的计数
题目链接:树的计数
这道题好神啊……正好有人讲了这道题,那么我就写掉吧……
首先,为了方便考虑,我们可以把节点重标号,使得\(bfs\)序变成\(1,2,3,……,n\),那么显然树的深度就是\(dep_n\)。
然后,我们来考虑一下\(dfs\)序和\(bfs\)序的性质。设\(dfs\)序中的第\(i\)个点为\(d_i\),那么显然有\(dep_{d_{i+1}} \le dep_{d_i}+1\)。由于我们已经进行了重标号,那么通过\(bfs\)序,我们可以得到\(dep_i \le dep_{i+1} \le dep_i+1\)。令\(pos_i\)表示节点\(i\)在\(dfs\)序中出现的位置,那么当\(dep_i=dep_{i+1}\)时,我们可以得到\(pos_i<pos_{i+1}\)。因为我们是按照\(bfs\)序编号的,所以对于同一深度的点,越早被\(dfs\)到编号就越小。
所以,我们建立一个数组\(s_i\),\(s_i=1\)表示\(dep_{i+1}=dep_i+1\),\(s_i=0\)表示\(dep_{i+1}=dep_i\),那么显然\(s_1=1\)。并且当\(pos_i>pos_{i+1}\)时,我们可以推出\(s_i=1\)。因为上一段中提到了,如果\(dep_i=dep_{i+1}\),则有\(pos_i<pos_{i+1}\)。
然后,我们接着考虑\(dfs\)序的限制。如果\(d_i<d_{i+1}\),由于\(dep_{d_{i+1}}-dep_{d_i} \le 1\),我们可以得到一个式子:
\[dep_{d_{i+1}}-dep_{d_i}=\sum_{j=d_i}^{d_{i+1}-1}s_j\]
于是我们可以得到一堆的约束条件。如果等号右边是\(0\),那么这段区间的\(s_j\)就都是\(0\)了。剩下的可能不为\(0\)的\(s_j\)都有可能为\(1\),而这些变量的取值和其他变量的取值无关,取到\(1\)的概率是\(0.5\),对\(dep_n\)贡献为\(0.5\)。
最后,让我们来回顾一下算法流程:
1.确定所有的\(s_i\)必定等于\(1\)的位置
2.找出所有的限制条件
3.未被限制且不一定为\(1\)的点对答案贡献为\(0.5\)。
于是这道题就愉快地解决辣!(虽然我可能还是没有讲清楚)
参考博客:戳这里
下面贴代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 200010 using namespace std; typedef long long llg; int d[maxn],n,a[maxn],s[maxn],w[maxn]; double ans; int getint(){ int w=0;bool q=0; char c=getchar(); while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar(); if(c==‘-‘) c=getchar(),q=1; while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } int main(){ File("a"); n=getint(); w[1]=1; for(int i=1;i<=n;i++) a[d[i]=getint()]=i; for(int i=1;i<=n;i++) d[a[getint()]]=i; for(int i=1;i<=n;i++) a[d[i]]=i; for(int i=2;i<=n;i++) if(a[i]<a[i-1]) s[i-1]++,s[i]--,w[i-1]++; for(int i=2;i<=n;i++) w[i]+=w[i-1]; ans=w[n]; for(int i=2;i<=n;i++) if(d[i-1]<d[i] && w[d[i]-1]-w[d[i-1]-1]) s[d[i-1]]++,s[d[i]]--; for(int i=1,j=0;i<n;i++) j+=s[i],ans+=(bool)(!j)*0.5; printf("%.3lf",ans+1); return 0; }
UOJ #122 【NOI2013】 树的计数