BZOJ2707:「SDOI2012」走迷宫 – 题解

主要思路

这题细节真他妈多。

首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。

继续阅读BZOJ2707:「SDOI2012」走迷宫 – 题解

P3211:[HNOI2011]XOR和路径题解

主要思路

首先,这道题是概率和期望分开算的,进行 DP 时实质上是对概率进行 DP。考虑拆位,设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率,那么显然:

\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]

其中,\((1 – dp_b[v])\)为\(v\)为\(0\)的概率,最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。

继续阅读P3211:[HNOI2011]XOR和路径题解