Base基站选址(线段树优化dp)

首先写dp转移式，      $dp(i，j)$表示在第i位修建第j个基站。

定义$l(i)$为能覆盖i的最靠左的基站，$r(i)$为能覆盖i的最靠右的基站，

l和r数组均可以用二分求出，

$dp(i，j)=min( dp(u，j-1)+cost(u，i)+c(i) )$     $(0<=u<i)$。

$cost(u，i)$表示在u，i间不能被覆盖的村庄w值和，

即$cost(u，i)=\sum \limits_{o=u}^{i} w(o)$   $l(o)>u \bigcap r(o)<i$

设$weight(u)=cost(u，i)+dp(u，j-1)$，

如果可以维护weight的最小值，那么就可以直接用线段树logn转移，

显然$dp(u，j-1)$可以直接更新，难点是cost的更新。

注意一个问题，d具有单调性，如果一个点不能被点l覆盖，

那么它必然也不能被l-1覆盖，可以使用区间修改，

对于每个村庄x，它如果不能被覆盖，需要被补偿，即$i＞r(x) \bigcap u<l(x)$

则可在处理完$r(x)$后对$l(x)$以前的weight值更新，使用vector记录每个点的$r(x)$值即可。

因为建第j个的dp值只与j-1有关，可以使用滚动线段树维护。

 

 

 

奇怪的道路(状压dp)

观察数据范围，看到k非常小，可以利用这一点进行状压dp

$dp(i,j,o)$表示目前在第i位，已经有j条边，当前从 i一直到i+k 的奇偶性的状态种数。

枚举状态，有$dp(i,j+1,o$  $xor$  $1$  $xor$  $p)+=dp(i,j,o)$。

由i转移到i+1位$dp(i+1,j,o)+=dp(i,j,o)$   $((i$  $and$  $1)==0)$

最终目的$dp(n+1,m,0)$

需要注意的是循环的顺序，这样才可以保证种数不重复。

如果先枚举边数，一定会导致同一状态的重复。

先枚举终点，可以保证以前枚举过的边不会再枚举到，就不会导致重复。

 

 

 

概率充电器(概率 树形dp)

每个点如果被充电，只可能有三种情况，

自己充上电，父亲有电且自己和父亲的边联通，儿子有电且自己和儿子的边联通

如果定义状态为充上电的概率，式子列的很麻烦，

不妨定义$p(x)$为点x不能充上电的概率，

$q(x)$为点x自己发电的概率，$data(x,y)$为边x，y联通的概率

$p(x)=(1-q(x))*\prod (1-data(x,i)+data(x,i)*p(i))$

或$p(x)=(1-q(x))*\prod (p(i)+(1-p(i))*(1-data(x,i)))$

上式中i为与x相连的点

两种计算方式是等价的，

第一种的解释为，该点不自己发电 * 边不联通 或 边联通且联通点无电

第二种的解释为，该点不自己发电 * 联通点无电 或 联通点有电且边不联通

有后效性，但n的范围过大不支持高斯消元

考虑树形dp，第一次dfs更新子树和自己对该节点的贡献

第二次dfs更新除子树和自己以外的点对该节点的贡献

因为只有乘的操作，更新的时候把以它为根的子树贡献除回去即可

答案显然为$\sum \limits_{i=1}^{n}(1-p(i))$

 

走迷宫(高斯消元 tarjan缩点)

INF的条件为，存在一个点，起点能到达但它无法到达终点。

定义$E(x)$为x到终点的期望长度，显然$E(t)=0$

$E(x)=\sum \limits_{i=1} E(i)/out(x) +1$          i为x的出边所连点

数据范围，如果对全图高斯消元，将TLE

题中提示强连通分量大小不超过100

可以在强连通分量形成的DAG图的反图上进行拓扑排序

对于每个强连通分量进行高斯消元，强连通分量中每个点的出边已经处理好，则可以解出该强连通分量中每个点的答案

目标即$E(s)$

 

 

XOR和路径(期望 高斯消元)

算法一：

因为是位运算，加上300的数据范围，显然要按位来进行高斯消元

给每个点开一个0域和一个1域，分别表示经过这一点且目前的xor和值为0和1的期望次数，显然该状态可以由它的每一个入边所连的点的状态转移而来。至于由0域还是1域，由边权该位为0还是1决定。

初始在起点，所以给起点的0域期望值加一，作为初始值以解出其他期望。

因为终点的期望经过次数必定为1

答案即每次消元终点1域的期望值乘该位对应的值大小 之和

 

算法二：(%yxm)

注意到终点没有出边，这是算法一中忽略的点

刚开始打的时候想到了可以直接对概率进行消元，但起点概率未知，于是只好打出了算法一

同理按位高斯消元

定义状态为该点到终点xor值为1的概率

显然终点的概率为0

一个点的概率可以由它的出边为1概率转移而来

答案即每次消元起点的概率乘该位对应的值大小 之和

 

 

卡牌游戏(dp  期望)

可以发现一个特点，当人数固定的时候，每个人的胜率都是固定的

于是可以以游戏进行的逆过程进行dp，即倒着dp

当只剩下一个人的时候 显然他的胜率是1

我们需要知道当前轮是谁在坐庄，但是如果多加一维dp，就会很臃肿，不妨让每轮坐庄的人都换到1号位

于是可以进行dp，该状态由人数减一，这个人下一次的编号转移过来

因为庄家始终是1，这个人下一次的编号就是这一次的编号减去卡牌上的数字，当然应该对一个数取模

 

 

OSU(期望)

$(n+1)^3-n^3=3n^2+3n+1$

每一次新增一个操作，目前的期望得分应该是 前一个期望得分 加上 期望的得分增量

期望得分增量与当前的期望连续1长度有关

每次的长度增量必定是1，于是可以处理出当前期望的长度和长度平方的期望，注意后者不等于前者的平方

 

 

 

 

硬币游戏

数据范围n<=300  加上如此诡异的数据，应该是高斯消元了

设P(i)表示完成第i个串的概率

诡异点：引入一个P(0)表示 一个串也不能匹配上的概率

于是P(i)可以用P(0)来表示

在P(0)后面接m个字符，可以凑成P(i)

但是还有已经可能凑成其它的字符串j，那么这个j一定满足j的后缀等同于字符串i的前缀，并且字符串0的后缀等同于字符串j的未匹配的前缀

$\sum \limits_{j=1} \sum \limits_{k=1}  P(j)*1/2^{m-k}+P(i)=P(0)*1/2^m$

k为匹配的长度

还差最后一个方程才能解出n+1个变量，这个方程就是$\sum \limits_{i=1}  P(i)=1$，即所有串的概率总和是1