题解 P1232 【[NOI2013]树的计数】

2014吕泽龙 · 2019-06-25 20:49:52 · 题解

分析

强烈吐槽一下这道题不采用取模的方式，害我被卡精度卡了半天。

因为毕竟是是自己yy的一种垃圾做法

手玩几组数据 （或者左转看看题解） 发现按层划分BFS序很科学。

然后就可以发现一个结论：一种合法的BFS序的划分对应一棵树。

证明：考虑递归构造对应关系。对于某个BFS序，如果我们已经构造出了i层以内的树，考虑第i+1层，因为已经划分好了，所以这一层有那些节点我们是知道的。如果我们将i层以内的节点在DFS序中全部删掉，剩下的一定是DFS序中的若干个区间。DFS序可以看成子树根+子树的形式，那么每个区间就对应一个子树，并且子树根就是区间左端点前一个节点。这样的话BFS序中第i+1层的节点就可以去对应区间找他们的父亲。

那么现在问题转化成合法地划分BFS序。考虑Dp

在构造的时候实际上已经初步得出了一个层划分合法性的判定方法。

首先将BfS序中j以前的点删掉。

根据题目的要求，第一个条件就是BfS序中[j+1,i]中的点在DFS序中的位置递增。

而构造的时候发现，删去的区间左端点一定是子树根，所以必须出现在划分中。

如果暴力枚举i,j，然后O(n)判断，这样的求can复杂度是O(n^3)的，而Dp也是O(n^3)的，这样就得到了一个O(n^3)的算法，接下来考虑优化。

首先，往O(n^2)进发，先优化预处理can(j,i)。

先枚举一个j，然后枚举i,对于第2个条件，我们对于DFS序中每个区间左端点在BFS序中的最大位置l，那么合法的i一定在l之后。

然后从l开始扫描一段区间，这段区间满足条件1，也就是位置递增即可。假设扫到了r，那么合法i在[l,r]之间。

对于f，一种比较有技巧性的做法是用生成函数优化。

这样的话方程可以写成F_i=\sum xF_j[can(j,i)]

事实上，我们要求的东西是\frac{F'_n(1)}{F_n(1)}

求个导看看：

将x=1带入：

设f_i=F_i(1),g_i=F'_i(1)转移就行了。

其实这个东西可以直接用期望去推，但是人菜就只好用笨方法推方程咯!

所以成功地把Dp也优化到了O(n^2)

还可以优化吗？

之前发现的一个性质是，对于一个j，它仅仅会转移到一段特定区间[l,r]内的i。而且贡献是线性的。

那么显然Dp部分差分打标记前缀和就O(n)了。

而can(j,i)怎么办？

对于某个j，显然r是可以用指针扫过去的。除非当前的j越过了r，不然r不会动。

而l可以在删除数的时候记录一下删除位置的下一个位置对应BFS序的位置，取个max即可。

这样的话两把指针扫一扫也是线性的了。这道题就这么被胡乱优化一波搞定了！

结果被卡精度了？！！！

开__float128也不行？！！！！

我搞了一波骚操作，把某个数科学计数法表示，然后重载加减法，忽略数量级超过一百的运算，然后就过了。。。。

代码

#include<bits/stdc++.h>
const int N = 2e5 + 10;
int ri() {
    char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
    for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
}
struct Data {
    double x; int e;
}g[N], f[N];
Data operator + (Data a, Data b) {
    if(a.e < b.e)
        std::swap(a, b);
    int d = a.e - b.e; double l = b.x;
    if(d > 100) l = 0;
    else {
        for(;d--;)
            l /= 10;
    }
    a.x += l;
    if(fabs(a.x) > 10) a.x /= 10, ++a.e;
    return a;
}
void operator += (Data &a, Data b) {a = a + b;}
void operator -= (Data &a, Data b) {
    b.x = -b.x;
    a = a + b;
}
int a[N], b[N], psa[N], psb[N], n, must;
int main() {
    n = ri();
    for(int i = 1;i <= n; ++i)
        a[i] = ri(), psa[a[i]] = i;
    for(int i = 1;i <= n; ++i)
        b[i] = ri(), psb[b[i]] = i;
    int l = 0, r = 0;
    f[1].x = g[1].x = 1;
    f[2].x = g[2].x = -1;
    for(int j = 1, i;j <= n; ++j) {
        f[j] += f[j - 1]; g[j] += g[j - 1];
        if(j == n) break;
        l = std::max(l, psb[a[psa[b[j]] + 1]]);
        for(r = std::max(r, j + 2);r <= n; ++r)
            if(psa[b[r]] < psa[b[r - 1]])
                break;
        --r;
        if(l <= r) {
            f[l] += f[j]; f[r + 1] -= f[j];
            g[l] += f[j] + g[j]; g[r + 1] -= f[j] + g[j];
        }
    }
    int d = g[n].e - f[n].e; double x = g[n].x / f[n].x;
    for(;d--;)
        x *= 10;
    printf("%.3lf\n", x);
    return 0;
}