BZOJ2115 [Wc2011] Xor 线性基+DFS 图论 数学

BZOJ2115 [Wc2011] Xor 线性基+DFS

题目   给出一个无向图,求一条1-n的路径,使路径边权xor和最大。 首先,可以把一条简单路径和任意多个环拼在一起,形成一条题目所求的路径。接着,对于任意一条简单路径,都可以和一些环的权值异或在一起,达到其他简单路径的效果。所以,我们只需找出任意一条简单路径,找到所有的环,再把环上的xo···
BZOJ2337 [HNOI2011]XOR和路径 高斯消元 图论 期望概率

BZOJ2337 [HNOI2011]XOR和路径 高斯消元

题目链接 一遍填以前的坑,一遍翻达哥的题表,结果就做了一堆高斯消元= = 考虑到二进制上每一位都是独立的,我们可以按位分别计算概率。 还是倒着做,设f[i]:从i点到达n点,该二进制位异或和为1的概率。 当遇到一条二进制为1的边时,意味着通过这条边,按照定义,概率应该取对立面,所以f[i]=p[i]···
BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元 图论 期望概率

BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

  题目链接 和BZOJ3270比较相似,都是在图上高斯消元来转移状态。 观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。 一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。 设f[i]:从i点出发走到终点的期望步数,则f···