UPD: 那位神牛的题解更新了，在这里。
----------------------------------------------------------------------------------------------------
被这题虐了好久……本来是看这个题解，然后晕乎乎的，没怎么看懂……然后YGW巨神质疑那个程序，于是就举出了一个反例……(rzO Orz)。于是本蒟蒻就顺着那个题解的思路和YGW的反例弄出了一种奇葩的方法……
我们在BFS序上分割，分出每一层。这样一种分割方案对应一种树的形态。
其实，分割方案会有不同，原因在于存在某些点，他们既可以做与他相邻的点的儿子，也可以做兄弟。那么他们对ans的贡献是0.5。而那些只能做儿子的点就只能被分配到下一层，所以对ans的贡献是1.0；其它的点对分层方案没有影响，对ans就没有贡献。于是关键在于如何找到这些点。
我们把BFS序编为1..n，以此重标号DFS序。
我们从1到n遍历BFS序，根据dfs序一个一个判断。
这些点必须满足既可以做兄弟也可以做儿子（废话- -）。
可以发现，那些点刚好在BFS和DFS序都是连续的。但是这还不够。我们还必须满足这个点可以分配到下一层（因为如果可以被分配到下一层就可以做兄弟）。于是考虑两个情况：
1.下一层有一个点的BFS序>当前点。
2.当前层有一个点的BFS序>当前点，且这个点必须在当前层。（注：有一种情况存在一个点的BFS序>当前点，但是不一定要在当前层，这种情况不影响当前点的分配方案。）
这两个情况下当前点都只能被分配到当前层。
第一种等价于dfs序<当前点的点中存在一个bfs序>当前点的点。（可以用前缀最值判断）
第二种等价于在dfs序中这个点的到前一个点之间有一个bfs序<当前点，这相当于限制了当前点与前一个点不是同一个点的儿子。（可以用线段树判断，否则要n^2，完全可以构造数据卡掉，如bfs:1 2 3 4 5 6 7 8 ... dfs:1 3 5 7 ... 2 4 6 8 ...）
当排除了上面两种情况后，当前点就可以放到下面去。且把当前点放到下面去对后面所有的点的分配是没有影响的，这样保证了正确性。
这种情况只出现在当前点的dfs序<上一个点的dfs序。
最后贴一下卡掉那个代码的数据和我的代码
9
1 2 4 5 6 7 9 8 3
1 2 3 4 5 6 7 8 9
/************************************************************** Problem: 3244 User: lazycal Language: C++ Result: Accepted Time:292 ms Memory:7056 kb ****************************************************************/ #include <cstdio> #include <algorithm> const int N = 200000 + 9; int Max[N],Min[N*4],rk[N],dfs[N],bfs[N],n; void build(const int idx,const int l,const int r) { if (l == r) return (void)(Min[idx] = dfs[l]); build(idx * 2,l,(l+r)/2); build(idx*2+1,(l+r)/2+1,r); Min[idx] = std::min(Min[idx*2],Min[idx*2+1]); } int MIN(const int idx,const int l,const int r,const int L,const int R) { if (L <= l && r <= R) return Min[idx]; int mid = (l + r)/2,res = 0x7fffffff; if (L <= mid) res = std::min(res,MIN(idx * 2,l,mid,L,R)); if (mid < R) res = std::min(res,MIN(idx*2+1,mid+1,r,L,R)); return res; } int main() { #ifndef ONLINE_JUDGE freopen("3244.in","r",stdin); freopen("3244.out","w",stdout); #endif scanf("%d",&n); for (int i = 1; i <= n; ++i) { scanf("%d",dfs + i); rk[dfs[i]] = i; } for (int i = 1; i <= n; ++i) { scanf("%d",bfs + i); dfs[rk[bfs[i]]] = i; } for (int i = 1; i <= n; ++i) { Max[i] = std::max(Max[i - 1],dfs[i]); rk[dfs[i]] = i; } build(1,1,n); int ans = 2,tmp = 0; for (int i = 1; i < n; ++i) { if (i == 1 || rk[i + 1] < rk[i]) ans += tmp + 2,tmp = 0; else if (rk[i] + 1 == rk[i + 1] && Max[rk[i]] < i + 1) ++tmp; else if (MIN(1,1,n,rk[i] + 1,rk[i + 1] - 1) < i) tmp = 0; } ans += tmp; printf("%.3f\n%.3f\n%.3f\n",ans/2.0-0.001,ans/2.0,ans/2.0+0.001); }
转载于:https://www.cnblogs.com/lazycal/p/bzoj-3244.html
相关资源：JAVA上百实例源码以及开源项目