首页 > 代码库 > 【uoj122】 NOI2013—树的计数
【uoj122】 NOI2013—树的计数
http://uoj.ac/problem/122 (题目链接)
题意
给出一棵树的dfs序和bfs序，保证一定可以构成一棵树。问构成的树的期望深度。
Solution
这是一个悲伤的故事，我YY的东西挂了，最后打满了补丁，化简一下，就是跟llg一样的写法。←_←别理他。
本来很简单的一个东西，也许是我脑洞太大了→_→
代码
// uoj122#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=200010;int vis[maxn],dfn[maxn],bfn[maxn],t[maxn],pos[maxn],n;double ans;int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&dfn[i]); for (int i=1;i<=n;i++) scanf("%d",&bfn[i]),t[bfn[i]]=i; for (int i=1;i<=n;i++) dfn[i]=t[dfn[i]]; for (int i=1;i<=n;i++) pos[dfn[i]]=i; ans=2; int l=2,r=n+1; vis[1]=1,vis[2]=1; for (int i=3;i<=n;i++) { if (pos[i-1]>pos[i]) ans++; if (pos[i-1]+1==pos[i] && r-l-1==n-i+1) ans+=0.5; vis[pos[i]]=1; while (vis[l+1]) l++; while (vis[r-1]) r--; } printf("%.3lf",ans); return 0;}
【uoj122】 NOI2013—树的计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。