P3317:[SDOI2014]重建题解

矩阵树定理的运用

正常来讲,在矩阵树中,我们其实要算的东西就是这个:

\[ \sum_T  \prod_{e \in T} p_e, \forall p_e = 1 \]

我们算的其实就是概率都为\(0/1\)的情况。现在我们要算:

\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]

我们可以考虑写成和式内仅与矩阵有关的式子:

\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]

合并积和式:

\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]

然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。

继续阅读P3317:[SDOI2014]重建题解

P3345:[ZJOI2015]幻想乡战略游戏题解

主要解法

动态点分治真不友好。

我们先来考虑\(O(nq)\)的静态做法。我们可以随便定一个根,\(O(n)\)处理两个数组来记录子树的权值和与子树之外的权值和,然后再来一次\(O(n)\)判定答案是否最小。

其实从这个地方,我们可以发现一些关系:如果一个点的子节点比父节点更优,会有这样的关系:

\[ dist(fa[u], u) * (sum[fa[u]] – sum[u]) < dist(fa[u], u) * (sum[u]) \]

其中\(sum\)数组是子树的权值和。总结一下就是:

\[ 2 * sum[u] > sum[fa[u]] \]

继续阅读P3345:[ZJOI2015]幻想乡战略游戏题解

[Fortuna OJ]Jul 11th – Group B 解题报告

A – 照片

这道题是一道很考察思维的题目,我在这里介绍 DP 的做法。

我们考虑 DP。大概的方程可以写成:

\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]

其中,\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量,然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\),也就是每一个点集合的左右端点。这个区间满足一个根本的条件:这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\),最后做个小 DP 更新数据即可。

继续阅读[Fortuna OJ]Jul 11th – Group B 解题报告

BZOJ 3456:城市规划题解

题面

注意:这道题在 BZOJ 上是权限题,我是在 JZOJ 上做的。

刚刚解决完电力网络的问题,阿狸又被领导的任务给难住了。

刚才说过, 阿狸的国家有\(n\)个城市,现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通。

为了省钱,每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案, 如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。

好了,这就是困扰阿狸的问题。换句话说,你需要求出\(n\)个点的简单(无重边无自环)无向连通图数目。

由于这个数字可能非常大,你只需要输出方案数 mod 1004535809(479 * 2 ^21 + 1) 即可。

继续阅读BZOJ 3456:城市规划题解