Sengxian's Blog

题目地址

描述

UOJ 有精美排版，http://uoj.ac/problem/131

分析

很神的题，完全不会。
跟大多数题解一样，首先还是对 BFS 序和 DFS 序重编号，使得 BFS 为 ，再记标好的 DFS 序为 $a[1..n]$。令 $pos[x]$ 为 $x$ 在 $a[]$ 中出现的位置，即 $pos[a[i]]=i$，下面全部以重标号后的下标描述。

首先介绍分段方案：任意一棵满足要求的树对应 BFS 序列的分段方案：，表示树高为 $h + 1$，第 $i$ 层的节点为 $[x_{i - 1} + 1, x_i]$。
要清楚这样一个事实，两棵不同的满足要求的树，必定对应着不同的分段方案。假设有相同的分段方案，则不同的树，必定有同一个节点 $u$ 的在某树中的父亲为 $x$，在另一棵树父亲为 $y$。那么不妨设 $x < y$，则显然在第一棵树中 $pos[x] < pos[u] < pos[y]$，第二棵树中 $pos[y] < pos[u]$，显然与“两棵树有相同的 DFS 序列矛盾”。

问题转化为统计合法分段方案段数的平均值，我们看看什么分段方案是合法的：

1. 结点 1 单独分为一段；
2. 对于 BFS 序列任何一段 $[l, r]$，有 ；
3. 记 $\mathrm{depth}[i]$ 为结点 $i$ 的深度，则 $\mathrm{depth}[a[i+1]] \le \mathrm{depth}[a[i]]+1$。

充分必要性我可以证明，这里不证。
第一条是显然的。对于第二条，也是显然的，同层的节点必定满足 DFS 由先后到到达。而对于第 3 条，意思是 DFS 序中相邻的两个节点 $a[i], a[i + 1]$，如果 $a[i] < a[i + 1]$ 必定满足 $a[i + 1]$ 的深度不大于 $a[i]$ 的深度 +1。首先 $a[i] > a[i + 1]$ 是绝对满足的，原因是 $a[i]$ 的层数不小于 $a[i + 1]$ 的层数，必定成立。而 $a[i] < a[i + 1]$ 时，要么它们之间有边，要么它们是兄弟，所以这个性质必须满足。

我们尝试将上面 3 条约束转化为易于计算的形式。构造辅助数列 ，$x_i$ 当且仅当结点 $i$ 和结点 $i+1$ 分在不同的两段，否则 $x_i = 0$。这样进行转化之后，以上三条约束变成了如下的形式：

1. $x_1 = 1$；
2. 若 $pos[i]>pos[i+1]$，则 $x_i = 1$；
3. 若 $a[i]<a[i+1]$，则 $\sum\limits_{a[i]\le j < a[i + 1]}x_j \le 1$。

一三想一想都能理解，第二条则是前面的第二条反过来了，如果 $pos[i]>pos[i+1]$，他们不可能在同一层，则 $x_i = 1$。则树高为 $\sum x_i + 1$。

问题变为给这个 01 序列赋值，并且有一定的约束，问你合法序列中平均有多少个 1。
第一二个约束可以秒杀。第三个约束我们先考虑 $\sum\limits_{a[i]\le j < a[i + 1]}x_j = 1$ 的部分，不难发现如果 $x_j(a[i]\le j < a[i + 1])$ 有一个被约束 2 确定了为 1，其余只能为 0 了，否则可以任意取值。
再考虑 $\sum\limits_{a[i]\le j < a[i + 1]}x_j = 0$ 的部分，$x_j = 0$ 说明均在同一层，所以 ，这不就是 $i < i + 1$ 吗？恒等式，可以忽略。
所以最后有一些变量被强制要求取 0 或 1，有些变量没有要求，因此平均贡献是 $0.5$，用前缀和的思想可以在 $O(n)$ 处理被强制取 0 的区间，也就是可以 $O(n)$ 得到答案。

代码

//  Created by Sengxian on 5/19/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3244 NOI 2013 D1T2
#include <bits/stdc++.h>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 200000 + 3;
int n, dfs[maxn], f[maxn], pos[maxn], fix[maxn], s[maxn];
bool x[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    for (int i = 0; i < n; ++i) dfs[i] = ReadInt();
    for (int i = 0; i < n; ++i) f[ReadInt()] = i;
    for (int i = 0; i < n; ++i) dfs[i] = f[dfs[i]], pos[dfs[i]] = i;
    x[0] = 1, fix[0]++, fix[1]--; //差分化标记，前缀和表示这个位置是否被固定
    for (int i = 0; i < n - 1; ++i)
        if (pos[i] > pos[i + 1]) x[i] = true;
    s[0] = 1;
    for (int i = 1; i < n - 1; ++i) s[i] = s[i - 1] + x[i];
    for (int i = 0; i < n - 1; ++i)
        if (dfs[i] < dfs[i + 1]) {
            //dfs 序中相邻的两个，且 dfs[i] < dfs[i + 1] 说明他们之间至多跨越 1 层
            int sum = s[dfs[i + 1] - 1] - (dfs[i] == 0 ? 0 : s[dfs[i] - 1]);
            if (sum) fix[dfs[i]]++, fix[dfs[i + 1]]--; //有一为 0 了必定都为 0
        }
    int f = 0; double ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        f += fix[i];
        if (f) ans += x[i];
        else ans += 0.5; //随便 0，1，平均下来就是 0.5
    }
    ans++; //树高还要 +1
    printf("%.3lf\n", floor(ans * 100 + 0.5) / 100);
    /* //bzoj 必须这样输出
    printf("%.3lf\n", ans - 0.001);
    printf("%.3lf\n", ans);
    printf("%.3lf\n", ans + 0.001);
    */
    return 0;
}