[ZJOI2015] 地震后的幻想乡

给定一个无向图 $G$ ，$n$ 个点 $m$ 条边每条边权为 $[0,1]$ 的随机实数，求这张图的最小生成树的最大边权期望。

$1\le n\le 10,1\le m\le \frac{n(n-1)}{2}$ 。

Solution

引理 $1$ ：

$n$ 个 $[0,1]$ 随机变量 $x_1,\cdots,x_n $ ，第 $k$ 小的期望值是 $\frac{k}{n+1}$

证明：枚举第 $k$ 小值为 $x$ ：$\binom{n}{k}\int_0^1x \cdot x^{k-1}\cdot (1-x)^{n-k} dx=\frac{k}{n+1}$ 。

暴力枚举 $m$ 条边的相对大小关系，套引理即可做到 $\mathcal O(m!poly(n))$ 。

考虑状压 dp ，定义 $f_{S,i},g_{S,i}$ 表示点集 $S$ ，用了 $i$ 条边，且点集不连通/连通的方案数，$d_{S}$ 表示点集 $S$ 导出子图的边数。

考虑 $f$ 的转移，我们枚举一个连通块（不妨是 $lowbit(S)$ 所属的那个块），其他的点之间任意连边，则： $f_{S,i}=\sum\limits_{lowbit(S) \in T\subset S}\sum\limits_{j=0}^{|d_T|}g_{T,j}\binom{|d_{S-T}|}{i-j}$

注意到 加了 i 条边恰好连通概率 = 加之前不连通概率 - 加之后不连通概率 ，因此答案为：

\[\sum_{k=1}^{m}\frac{k}{m+1}\cdot \left(\frac{f_{U,k-1}}{\binom{|d_U|}{k-1}}-\frac{f_{U,k}}{\binom{|d_{U}|}{k}}\right)\\\begin{aligned}=\frac{1}{m+1}\sum_{k=0}^{m}\frac{f_{U,k}}{\binom{|d_{U}|}{k}}\end{aligned}
\]

时间复杂度 $\mathcal O(3^nm)$ 。

Day1

T1

给定一个由字符 $\text{'a', 'b'}$ 构成的字符串 $str$ 。

一个串为好串的定义是：串长为偶数，且左右两半相等。比如说 $abcdeabcde$ 就是好串。

有 $q$ 次询问，询问区间 $[l,r]$ 内有多少个本质不同的好串（也就是一模一样的好串只算 $1$ 次）。

$1\le n,q\le 2\times 10^5$

T2

给定一颗广义线段树，读入按中序遍历的方式告诉你每根线段 $[l,r]$ 的 $mid$ 值。

你需要执行 $k$ 次 选区间 操作，每次等概率选择一个区间 $[ql, qr]$ 满足 $1\le ql\le qr\le n$ ，并且相应在线段树上打懒标记。

对于每个区间 $[ql, qr]$，执行 $\text{modify(1, 1, n, ql, qr)}$ ：

void pushdown(int u) {

  if (tag[u]) {

    tag[lson[u]] = 1;

    tag[rson[u]] = 1;

    tag[u] = 0;

  }

}

void modify(int u, int l, int r, int ql, int qr) {

  if ([l, r] ∩ [ql, qr] = 空集) return ;

  if (ql <= l && r <= qr) {

    tag[u] = 1;

    return ;

  }

  int mid = 读入的 mid 值;

  pushdown(u);

  if (ql <= mid) modify(lson[u], l, mid, ql, qr);

  if (qr > mid) modify(rson[u], mid + 1, r, ql, qr);

}

请求出期望下线段树中 $tag$ 值为 $1$ 的线段的个数。

$n$ 在 $10^5$ 级别， $1\le k\le 10^9$ 。

T3

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，你可以执行以下三种操作：

选择一个区间 $[l,r]$ ，让区间内的数全减 $1$
选择一个区间 $[l,r]$ ，让区间内下标是奇数的数全减 $1$
选择一个区间 $[l,r]$ ，让区间内下标是偶数的数全减 $1$

你需要最小化你的操作次数，使得所有数变成 $0$ 。

Day2

T1

$Alice$ 和 $Bob$ 在 树/基环树 上的游戏。。。

题面有点长，咕咕

T2

给定 $n$ 个数 $a_1,a_2,...,a_n$ ，每次等概率选择一个数（选过的数下次可能还会被选）。

问期望下取多少次数，才能出现 $k$ 个连续的数（也就是满足 $a_{i_1},a_{i_2},a_{i_3},...$ 依次 $+1$）？

$1\le n\le 2\times 10^5, 1\le a_i\le 10^9$（好像）

T3

给定 $n$ 个方程组，参数 $a_i,c_i$。

\[\begin{cases}a_1 \times x + p_1 \equiv c_1 (mod\ p) \\ a_2 \times x + p_2 \equiv c_2 (mod\ p) \\ ... \\ a_n\times x + p_n \equiv c_n (mod\ p) \end{cases}
\]

给出一个扰动 $err$ ，每个 $p_i$ 均为 $[\lceil - \frac{err}{2} \rceil, \lceil \frac{err}{2} \rceil]$ 内随机的一个数。

你需要找到一个 $x$ ，使得它满足上述所有条件。

数据保证有且仅有一个 $x$ 满足条件。

$n=2000, 1\le a_i,c_i,p\le 10^{18}$

如果要用 $\text{__int128}$ ，请手写。

巴特西

ZJOI2020

[ZJOI2015] 地震后的幻想乡

Day1

T1

T2

T3

Day2

T1

T2

T3

最新文章

热门文章