欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

[NOI2013]树的计数

发布时间:2024/7/5 编程问答 4 豆豆
如意编程网 收集整理的这篇文章主要介绍了 [NOI2013]树的计数 小编觉得挺不错的,现在分享给大家,帮大家做个参考.
// luogu-judger-enable-o2 /* 考虑将bfs序按层分段, 每分一段就会使深度+1,所以分的段数+1就是深度 由于每种分段方式至多只能对应一种dfs序, 所以我们的目标就是求出可行的bfs序 然后我们发现, 如果在bfs序中第i个比第i + 1个后出现在dfs序中, 那么这里一定分段然后我们考虑dfs序对于bfs序的限制, 假设a[i] < a[i + 1]的话,意味着a[i + 1]和a[i]同层或者在下一层那么\sum_{i = a[i]} ^ {a[i + 1] - 1} 分层<= 1这样的话得到了一些限制以及确定位置, 没有限制的位置因为任意分都可以, 那么统计0.5答案即可*/ #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> #define mmp make_pair #define ll long long #define M 200010 using namespace std; int read() {int nm = 0, f = 1;char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';return nm * f; } double note[M], s[M]; int t[M], a[M], pos[M], f[M], sta[M], n, tp; int main() {double ans = 1;n = read();for(int i = 1; i <= n; i++) t[read()] = i;for(int i = 1; i <= n; i++) {int x = read();a[t[x]] = i, pos[i] = t[x];}note[1] = 1;for(int i = 1; i < n; i++) {if(pos[i] > pos[i + 1]) note[i] = 1;if(note[i] == 1) {f[i]++;f[i + 1]--;}s[i] = s[i - 1] + note[i];}for(int i = 1; i < n; i++) {if(a[i] < a[i + 1]) {if(s[a[i + 1] - 1] - s[a[i] - 1] > 0) {f[a[i]]++;f[a[i + 1]]--;} else sta[++tp] = a[i];}}for(int i = 1; i <= n; i++) f[i] += f[i - 1];for(int i = 1; i <= tp; i++) {if(f[sta[i]] == 0) note[sta[i]] = 0.5;}for(int i = 1; i <= n; i++) ans += note[i];printf("%.3lf\n", ans);return 0; }

转载于:https://www.cnblogs.com/luoyibujue/p/10903784.html

总结

以上是如意编程网为你收集整理的[NOI2013]树的计数的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。