标签: 期望

[WC2010]重建计划 题解

[WC2010]重建计划 题解

题目地址:洛谷:【P4292】[WC2010]重建计划 – 洛谷、BZOJ:Problem 1758. — [Wc2010]重建计划

题目描述

1758 - [WC2010]重建计划 题解

题意简述

给你一棵树,求长度在[L, U]范围内的树链的边权平均值的最大值。

输入输出格式

输入格式:
第一行包含一个正整数N,表示X国的城市个数。
第二行包含两个正整数L、U,表示政府要求的第一期重建方案中修建道路数的上下限。
接下来的N-1行描述重建小组的原有方案,每行三个正整数ai, bi, vi,分别表示道路(ai, bi),其价值为vi。其中城市由1…N标号。

输出格式:
仅包含一行,为一个实数AvgValue,即最大平均价值。
小数点后保留三位。

输入输出样例

输入样例#1:

4 
2 3 
1 2 1 
1 3 2 
1 4 3

输出样例#1:

2.500

说明

新方案中选择路径(3, 1), (1, 4)可以得到的平均价值为2.5,为最大平均价值。
对于20%的数据,N ≤ 5 000;
另有30%的数据,N ≤ 100 000, 原有方案恰好为一条路径(链);
对于100%的数据,N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, vi ≤ 10^6。

题解

整个树找树链可以考虑使用点分治。
对于每个重心,我们考虑二分答案,验证的时候找两条子树到重心的路径拼起来长度在范围内的,或者一条路径长度就在范围内的,在处理边权和的时候在每个边权上减掉答案,则只需要判断边权和是否不小于0即可。
由于对于以前找到过的每一个深度的链,只需要存下边权和最大值,就可以直接拿来判断了。而枚举每个深度去遍历合法区间,会造成复杂度退化为$O(n^2)$。我们考虑单调队列优化这一过程,从浅到深枚举当前遍历子树的每个节点,对应的在以前找到过的深度区间可以确定为[L-d, R-d],由于遍历的顺序单调,单调队列可以倒着从深到浅维护最大值来判定,遍历节点时使用BFS,这样节点的遍历顺序就是从浅到深单调的了,这样判定的复杂度是$O(n)$的了。
单调队列的复杂度其实应该是$O(之前找到过的最大深度)$的,因此,我们可以对每一棵子树的深度进行排序,从浅的子树开始遍历,可以优化时间,不过我采用了快排,排序复杂度会多一个$\log n$。
另外,本题有一定的卡常数成分,有以下几个卡常的地方可以作为参考:

  1. 每次遍历需要初始化最大值数组,可以到用的时候再初始化(参见121~123行);
  2. 对于大小小于L的子树,是找不到符合条件的链的,因此可以不用递归下去处理(参见145行);
  3. 可以使用计数排序代替快排(没写);
  4. 读入优化,fread(我的文件头);
  5. 存树用邻接表而不是vector;
  6. 自己实现的max函数代替STL的;
  7. 手写BFS的队列;
  8. 二分答案的时候,可以将左端点设为已经找到的解,右端点设为最大边权,这样每次二分只会去找比当前解更优的解更新。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline double max(double a, double b) {
    return a > b ? a : b;
}

const int MAXN = 100005;
const double EPS = 1e-4;

int n, L, U;
double ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int w) {
    gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, w, head[v]}; head[v] = tot++;
}

bool vis[MAXN];
int siz[MAXN], rt, rtsiz;

inline void findrt(int u, int fa, int tot) {
    siz[u] = 1; int msiz = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        findrt(v, u, tot);
        siz[u] += siz[v];
        msiz = max(msiz, siz[v]);
    }
    msiz = max(msiz, tot - siz[u]);
    if(msiz < rtsiz) {
        rt = u; rtsiz = msiz;
    }
}

int fa[MAXN], dep[MAXN], que[MAXN], deq[MAXN];
double dis[MAXN];

int tdep[MAXN], subt[MAXN], subw[MAXN], stot;

inline bool cmp(int a, int b) {
    return tdep[a] < tdep[b];
}

inline int dfs(int u, int fa, int dep) {
    int mxdep = dep;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        mxdep = max(mxdep, dfs(v, u, dep + 1));
    }
    return mxdep;
}

double mx[MAXN];

inline bool check(int u, double mid) {
    int mxdep = 0;
    stot = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        subt[++stot] = v;
        subw[v] = gra[i].w;
        tdep[v] = dfs(v, u, 1);
    }
    std::sort(subt + 1, subt + stot + 1, cmp);
    for(register int i = 1; i <= stot; i++) {
        int v = subt[i];
        if(vis[v]) continue;
        int hd = 0, tl = 1; fa[v] = u; dep[v] = 1; dis[v] = subw[v] - mid; que[0] = v;
        while(hd < tl) {
            int uu = que[hd++];
            for(register int j = head[uu]; ~j; j = gra[j].nxt) {
                int vv = gra[j].to;
                if(vis[vv] || vv == fa[uu]) continue;
                fa[vv] = uu;
                dep[vv] = dep[uu] + 1;
                dis[vv] = dis[uu] + gra[j].w - mid;
                que[tl++] = vv;
            }
        }
        int l = 1, r = 0, now = mxdep;
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            while(dep[p] + now >= L && now >= 0) {
                while(l <= r && mx[deq[r]] < mx[now]) r--;
                deq[++r] = now; now--;
            }
            while(l <= r && dep[p] + deq[l] > U) l++;
            if(l <= r && dis[p] + mx[deq[l]] + EPS >= 0) return true;
        }
        for(register int j = mxdep + 1; j <= dep[que[tl - 1]]; j++) {
            mx[j] = -1e9;
        }
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            mx[dep[p]] = max(mx[dep[p]], dis[p]);
        }
        mxdep = max(mxdep, dep[que[tl - 1]]);
    }
    return false;
}

int lim;

inline void divide(int u) {
    register double l = ans, r = lim, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(check(u, mid)) l = mid; else r = mid;
    }
    ans = l;
    vis[u] = true;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || siz[v] < L) continue;
        rt = 0; rtsiz = n; findrt(v, u, siz[v]);
        divide(rt);
    }
}

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); L = readint(); U = readint();
    for(register int i = 1, a, b, c; i < n; i++) {
        a = readint(); b = readint(); c = readint();
        lim = max(lim, c);
        addedge(a, b, c);
    }
    rt = 0; rtsiz = n; findrt(1, 0, n);
    divide(rt);
    printf("%.3lf", ans);
    return 0;
}
[HAOI2012]高速公路 题解

[HAOI2012]高速公路 题解

题目地址:洛谷:【P2221】[HAOI2012]高速公路 – 洛谷、BZOJ:Problem 2752. — [HAOI2012]高速公路(road)

题目描述

Y901高速公路是一条重要的交通纽带,政府部门建设初期的投入以及使用期间的养护费用都不低,因此政府在这条高速公路上设立了许多收费站。
Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链,我们按照由西向东的顺序将收费站依次编号为1~N,从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况,会不定期地对连续路段的收费标准进行调整,根据政策涨价或降价。
无聊的小A同学总喜欢研究一些稀奇古怪的问题,他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b,那么从a行驶到b将期望花费多少费用呢?

输入输出格式

输入格式:
第一行2个正整数N,M,表示有N个收费站,M次调整或询问
接下来M行,每行将出现以下两种形式中的一种
C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v
Q l r 表示对于给定的l,r,要求回答小A的问题
所有C与Q操作中保证1<=l<r<=N

输出格式:
对于每次询问操作回答一行,输出一个既约分数
若答案为整数a,输出a/1

输入输出样例

输入样例#1:

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

输出样例#1:

1/1
8/3
17/6

说明

所有C操作中的v的绝对值不超过10000
在任何时刻任意道路的费用均为不超过10000的非负整数
所有测试点的详细情况如下表所示
Test N M
1 =10 =10
2 =100 =100
3 =1000 =1000
4 =10000 =10000
5 =50000 =50000
6 =60000 =60000
7 =70000 =70000
8 =80000 =80000
9 =90000 =90000
10 =100000 =100000

题解

既然所有情况是等概率的,那么期望可以定义成所有情况的和除以情况数量。我们考虑询问中单独一段路对所有情况的和的贡献,假如为第i段路(即连接第i个与第i+1个收费站的路),则为 (i-l+1)(r-i)v_i ,也就是说,答案是
\begin{aligned} \mathrm{E}(l, r) &= \frac{\sum_{i=l}^{r-1} (i-l+1)(r-i)v_i}{\mathrm{C}_{r-l+1}^2} \\ &= \frac{(r-lr)\sum_{i=l}^{r-1} v_i + (l+r-1) \sum_{i=l}^{r-1} iv_i - \sum_{i=l}^{r-1} i^2v_i}{(r-l)(r-l+1)/2} \end{aligned}
我们考虑用线段树维护v_i, iv_i, i^2v_i的值,每次询问把它们拿出来算一下即可。
当我们使用lazy标记的时候,肯定要求\sum_{i=l}^r i^2的值,平方和公式是\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6},可以做减法求出要求的值。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'C' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 100005;

inline LL callr(LL l, LL r) {
    return (l + r) * (r - l + 1) / 2;
}

inline LL call2r2(LL l, LL r) {
    return r * (r + 1) * (2 * r + 1) / 6 - l * (l - 1) * (2 * l - 1) / 6;
}

inline LL gcd(LL a, LL b) {
    if(a < b) std::swap(a, b);
    LL t;
    while(b) {
        t = a; a = b; b = t % b;
    }
    return a;
}

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

struct Node {
    LL v, iv, iiv, add;
} sgt[MAXN << 2];

inline void merge(Node &rt, Node ls, Node rs) {
    rt.v = ls.v + rs.v;
    rt.iv = ls.iv + rs.iv;
    rt.iiv = ls.iiv + rs.iiv;
}

inline void pushdown(int o, int l, int r) {
    if(sgt[o].add) {
        sgt[lch].add += sgt[o].add;
        sgt[rch].add += sgt[o].add;
        sgt[lch].v += sgt[o].add * (mid - l + 1);
        sgt[rch].v += sgt[o].add * (r - mid);
        sgt[lch].iv += sgt[o].add * callr(l, mid);
        sgt[rch].iv += sgt[o].add * callr(mid + 1, r);
        sgt[lch].iiv += sgt[o].add * call2r2(l, mid);
        sgt[rch].iiv += sgt[o].add * call2r2(mid + 1, r);
        sgt[o].add = 0;
    }
}

inline void add(int o, int l, int r, int ll, int rr, LL v) {
    if(l >= ll && r <= rr) {
        sgt[o].add += v;
        sgt[o].v += v * (r - l + 1);
        sgt[o].iv += v * callr(l, r);
        sgt[o].iiv += v * call2r2(l, r);
        return;
    }
    pushdown(o, l, r);
    if(ll <= mid) add(lch, l, mid, ll, rr, v);
    if(rr > mid) add(rch, mid + 1, r, ll, rr, v);
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline Node query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) {
        return sgt[o];
    }
    pushdown(o, l, r);
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        Node res, ls = query(lch, l, mid, ll, mid), 
            rs = query(rch, mid + 1, r, mid + 1, rr);
        merge(res, ls, rs);
        return res;
    }
}

LL n, m, l, r, v;
char op;

int main() {
    n = readint(); m = readint();
    while(m--) {
        op = readop(); l = readint(); r = readint();
        if(op == 'C') {
            v = readint();
            add(1, 1, n - 1, l, r - 1, v);
        } else {
            Node res = query(1, 1, n - 1, l, r - 1);
            LL a = (r - l * r) * res.v + (l + r - 1) * res.iv - res.iiv,
                b = (r - l) * (r - l + 1) / 2, g = gcd(a, b);
            printf("%lld/%lld\n", a / g, b / g);
        }
    }
    return 0;
}
[ZJOI2015]地震后的幻想乡 题解

[ZJOI2015]地震后的幻想乡 题解

题目地址:洛谷:【P3343】[ZJOI2015]地震后的幻想乡 – 洛谷、BZOJ:Problem 3925. — [Zjoi2015]地震后的幻想乡

题目描述

傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。
幻想乡一共有n个地方,那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的,一共有m条边。现在这m条边由于地震的关系,全部都毁坏掉了。每条边都有一个修复它需要花费的时间,第i条边所需要的时间为ei。地震发生以后,由于幽香是一位人生经验丰富,见得多了的长者,她根据以前的经验,知道每次地震以后,每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。
现在幽香要出发去帮忙修复道路了,她可以使用一个神奇的大魔法,能够选择需要的那n-1条边,同时开始修复,那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值,然后再选择完成时间最小的方案。 幽香在走之前,她想知道修复完成的时间的期望是多少呢?

输入输出格式

输入格式:
第一行两个数n,m,表示地方的数量和边的数量。其中点从1到n标号。 接下来m行,每行两个数a,b,表示点a和点b之间原来有一条边。 这个图不会有重边和自环。

输出格式:
一行输出答案,四舍五入保留6位小数。

输入输出样例

输入样例#1:

5 4
1 2
1 5
4 3
5 3

输出样例#1:

0.800000

说明

提示:
(以下内容与题意无关,对于解题也不是必要的。)
对于n个[0,1]之间的随机变量x1,x2,…,xn,第k小的那个的期望值是k/(n+1)。
样例解释:
对于第一个样例,由于只有4条边,幽香显然只能选择这4条,那么答案就是4条边的ei中最大的数的期望,由提示中的内容,可知答案为0.8。
数据范围:
对于所有数据:n<=10, m<=n(n-1)/2, n,m>=1。
对于15%的数据:n<=3。
另有15%的数据:n<=10, m=n。
另有10%的数据:n<=10, m=n(n-1)/2。
另有20%的数据:n<=5。
另有20%的数据:n<=8。

题解

题目要求最小生成树上的最大边权Y的期望,因此我们只需要关心这个最大边权在所有边权中的排名,我们发现有下面的式子
\mathrm{E}(Y) = \sum_{i=1}^n \mathrm{E}(i)\mathrm{P}(i) = \sum_{i=1}^n \frac{i}{m+1} \cdot \mathrm{P}(i) = \frac{\sum_{i=1}^n i\mathrm{P}(i)}{m+1} = \frac{\mathrm{E}(Z)}{m+1}
最后我们发现要求的就是最小生成树上最大边权排名的期望值Z。考虑怎么求这个Z,设L为同定义的随机变量,有
\mathrm{E}(Z) = \sum_{i=1}^m i\mathrm{P}(L=i) = \sum_{i=1}^m \mathrm{P}(L \geq i)
如果说最大边排名大于等于i不好求,我们就正难则反,求排名小于i的边集无法构成生成树的概率,由于所有的边权都是随机分布的变量,这个概率可以转化为从边集中随机选择i条边无法构成生成树的概率,我们考虑计算出选择i条边无法构成生成树的方案数,进而计算概率。
通过观察题目数据范围,我们发现n的范围很适合状压。考虑状压DP,用f[S][i]表示在S点集构成的子图中,选i条边使得该点集不连通的方案数,这个状态似乎没法转移,但是我们考虑与其意义互补的量:g[S][i]表示在S点集构成的子图中,选i条边使得该点集连通的方案数,显然有
f[S][i] + g[S][i] = \mathrm{C}_{ecnt[S]}^i
ecnt表示该点集构成子图内的边数。如果知道了其中一个,我们就可以知道另外一个。那么怎么转移成了问题,我们考虑固定S中的某个点,对于S这个点集的一个包含定点的真子集T,只要使T连通但\complement_S T与T之间没有连边就能保证S不连通了,而枚举每一个T可以实现对S不连通情况的遍历。最后我们的转移式就是
f[S][i] = \sum_{T \subsetneqq S, U \in T} \sum_{j=0}^{ecnt[T]} g[T][j] \cdot \mathrm{C}_{ecnt[\complement_S T]}^{i-j}
最后,我们获得了 \mathrm{E}(Z) = \sum_{i=0}^{n-1} f[\mathbb{U}][i] ,直接计算答案即可。
注意爆int。

附加内容:证明提示结论

需要证明的内容:对于n个[0,1]之间的随机变量x1,x2,…,xn,第k小的那个的期望值是k/(n+1)。
我们首先令x_1为第k小值,我们现在来求它的期望。
对于这种情况,我们显然有其中k-1个值比它小,n-k个值比它大,我们分别计算概率,乘起来,就得到了概率密度,对其积分就是x_1为第k小值时x_1的期望值,即\mathrm{E}(x_1, x_1是第k小数)
\begin{aligned} & \int_0^1 x_1 \cdot x_1^{k-1} (1-x_1)^{n-k} \mathrm{d}x_1 \\ = & \int_0^1 x_1^k (1-x_1)^{n-k} \mathrm{d}x_1 \\ = & \mathrm{B}(k+1, n-k+1) \\ = & \frac{k!(n-k)!}{(n+1)!} \end{aligned}
我们知道了这个,但是要求的是E(第k小数),即\mathrm{E}(x_1|x_1是第k小数)。我们记x_1是第k小数这一事件为A,根据下面的关系
\mathrm{E}(x_1|A) = \frac{\mathrm{E}(x_1, A)}{\mathrm{P}(A)}
我们又容易知道
\mathrm{P}(A) = \frac{1}{n \cdot \mathrm{C}_{n-1}^{k-1}}
直接就可以算出来了,结果就是
\mathrm{E}(x_1|A) = \frac{k}{n+1}

代码

// Code by KSkun, 2018/3
#include <cstdio>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 13, MAXM = 50;

int n, m, ut, vt;
LL gra[MAXN], cnt[1 << MAXN], ecnt[1 << MAXN], f[1 << MAXN][MAXM], g[1 << MAXN][MAXM];

LL C[MAXM][MAXM];

inline void calc() {
    for(int i = 0; i <= m; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
}

int main() {
    n = readint(); m = readint();
    calc();
    for(int i = 0; i < m; i++) {
        ut = readint(); vt = readint();
        gra[ut] |= (1 << (vt - 1));
        gra[vt] |= (1 << (ut - 1));
    }
    for(int i = 0; i < 1 << n; i++) {
        cnt[i] = cnt[i >> 1] + (i & 1);
    }
    for(int i = 0; i < 1 << n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i & (1 << (j - 1))) {
                ecnt[i] += cnt[gra[j] & i];
            }
        }
        ecnt[i] >>= 1;
    }
    for(int i = 0; i < 1 << n; i++) {
        if(cnt[i] == 1) {
            g[i][0] = 1;
            continue;
        }
        int t = i & (-i);
        for(int j = (i - 1) & i; j; j = (j - 1) & i) {
            if(j & t) {
                for(int k1 = 0; k1 <= ecnt[j]; k1++) {
                    for(int k2 = 0; k2 <= ecnt[i ^ j]; k2++) {
                        f[i][k1 + k2] += g[j][k1] * C[ecnt[i ^ j]][k2];
                    }
                }
            }
        }
        for(int j = 0; j <= ecnt[i]; j++) {
            g[i][j] = C[ecnt[i]][j] - f[i][j];
        }
    }
    double ans = 0;
    for(int i = 0; i <= m; i++) {
        ans += double(f[(1 << n) - 1][i]) / C[m][i];
    }
    printf("%.6lf", ans / (m + 1));
    return 0;
}