首页 > 代码库 > 【BZOJ3244】【UOJ#122】【NOI2013]树的计数
【BZOJ3244】【UOJ#122】【NOI2013]树的计数
NOI都是酱的题怎么玩啊,哇.jpg
原题:
我们知道一棵有根树可以进行深度优先遍历(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
2≤n≤200000
恩开始想了一下一点思路都没有。。。。。。。。。好吧我应该想一想暴力的
直接看题解了,这里只解释题解
首先先把bfs调成1,2,3……n的形式,dfs跟着调方便讨论
然后对于b=a+1
因为bfs是按层推,所以b要么跟a一层,要么比a多一层,即height[b]=height[a]+1或height[b]=height[a],如果在同一层则b一定在a的后面
如果dfs[a]>dfs[b],表示dfs的时候是先到a再到b,那么a和b就不能在同一层,则height[b]=height[a]+1
如果dfs[a]<dfs[b],有两种情况,dfs[b]!=dfs[a]+1,这个时候显然只能是ab在同一层且a在b前面,注意因为bfs[b]=bfs[a]+1(注意bfs[a]=a)
如果dfs[b]=dfs[a]+1,还是有两种情况,菊花或链,如果菊花就height[b]=height[a],如果链就height[b]=height[a]+1
尽管这种情况有机会是的height[b]大于height[a],但是这个未必会对答案造成影响
啥时候会造成影响呢,首先height[b]=height[a]+1,然后b是这一层最后一个点,这个时候对答案就贡献了
怎么判断这种情况?当剩下的点都是b的子树的时候就是这种情况,如果用flag[i]表示i有没有被遍历到,计一个r表示从最右边起最多连续多少个flag[i]==1,l表示从左起最多连续多少个flag[i]==1,那么当i-1=n-r+1-l,即左边一截全是1,右边一截全是1,中间全是0的时候就表示剩下的点全是b的子树
因为还有height[b]=height[a]的情况而且这种情况对于后面没有影响,因此此时给答案贡献的期望值为0.5
为啥height[b]=height[a]+1会对答案有贡献呢,因为b=a+1,前面是沿着bfs序一层一层推的,结合上面的性质就容易立即如果对答案贡献
这种题完全没思路啊,NOI怎么玩啊QAQ
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int rd(){int z=0,mk=1; char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mk=-1; ch=getchar();} 9 while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘; ch=getchar();} 10 return z*mk; 11 } 12 int n,a[210000],b[210000]; 13 int rvs[210000]; 14 bool flg[210000]; 15 int main(){freopen("ddd.in","r",stdin); 16 cin>>n; 17 for(int i=1;i<=n;++i) a[i]=rd(),rvs[a[i]]=i; 18 for(int i=1;i<=n;++i) b[i]=rvs[rd()]; 19 int l=2,r=n+1; double ans=2; 20 flg[1]=flg[2]=true; 21 for(int i=3;i<=n;++i){ 22 if(b[i-1]>b[i]) ++ans; 23 else if(b[i]==b[i-1]+1) ans+=(n-r+1+l==i-1)*0.5; 24 flg[b[i]]=true; 25 while((l<r) & flg[r-1]) --r; 26 while((l<r) & flg[l+1]) ++l; 27 } 28 printf("%.3lf\n%.3lf\n%.3lf\n",ans-0.001,ans,ans+0.001); 29 return 0; 30 }
【BZOJ3244】【UOJ#122】【NOI2013]树的计数