day6

正睿青岛

相对误差：
L,R大于1的时候：
ans = [0.999999ans,1.000001ans]
$int~~ mid = \sqrt {L \times R}$
绝对误差：

T1

T2

大于4400的，都是没有用的。都写成一个。
f[i][j]到前i场，rating为j的最多次数。

T3

枚举切开的位置，然后求把两边改成一样的次数。编辑距离。

T4

一个格子可以移动到任意的格子！！！
f[i][j][k1][k2]到i,j，k1个浮桥，k2个非浮桥。

T5

f[i][j]必须选i,j，合法的序列，(X),[X]。
G[i][j]必须选i,j，所有合法的序列。

$f[i][j] = \sum_{i<=p<=q<=j}G[i][j] + 1$
$G[i][j] = F[i][j] + \sum_{i<=p<=q<=j}F[i][p] + G[q][j] + 1$
()因为有这样的情况，所以让i和p必须匹配。

T6

变成求方案。
f[i]到第i个人的方案数。第i个说的是ai，那么可以让i-ai~i，i-ai+1~i，i-ai+2~i...是一个国家的，如果可以在共同一个国家的话。

T7

一共2^10个点，每个点表示
${f_n,f_{n-1},f_{n-2},...f_{n-5}\\ g_n,g_{n-1},g_{n-2},...g_{n-5}}$
然后每个点都可到一个点，然后可以倍增。
还可以找周期。

T8

dp[i][j]A的i子树和B的j子树，能不能匹配。
然后从A的子树里枚举所有的儿子，与b判断时候能不能匹配，然后在A的儿子里找一个子序列（有顺序的子序列，和B的所有儿子的顺序是一样的），与B的儿子匹配哦。
还有贪心。

T9

就是开始时一些长度为2的边，可以用两个长度为1的点代替一个长度为2的，然后求最小价值。
枚举这样的断点。f[i]到i的，当前图还是边双的边权。

但是两个长度为2的边不可以挨着替换。

T10

T11 SRM 719 OwaskiAndTree

考虑求最大子段和的过程，就是将前面一段标成0（这部分的权值不要了），中间一段标成1（要加的权值），后面的标成2（还没算到的权值）。

于是，在树上也是这样，子节点的标号<=父节点的标号，为1的加上，为0的不加，为2的也不加。

dls：然后小dp一下。

dp[u][j]，j=0/1/2，然后dp。1有代价。

T12

每个位置-i。
小于->小于等于
然后离散化。
将区间离散化，如果不同区间，就直接加，否则，组合数算一算。

13

redisgood

dp[n][m]还剩n张黑牌，m张红牌的期望，转移：翻倒红牌+1，黑牌与0取max（最优策略，）

TCO18 wildcard hard

本质不同的公共回文子序列。
f[l1][r1][l2][r2]

CF E：
dp[u]子树u最少剖成多少条链。

spfa判负环

复杂度$O(nm)$
进队列n次，说明有负环。
如果可能过不去，直接判进队次数，如果进了500w，直接返回有负环。
常数优化：判最短路树上，前面边的条数>n。

if (dis[u] + w < dis[v]) {
    dis[v] = dis[u] + w;
    deth[v] = deth[u] + 1;
    if (deth[v] > n) {
        break;
    }
}

0/1边，如果是0，插到队首，否则，插到队尾。
$O(m+W)$，$W$总长为W。

边权都是1~n，最短路：开n个桶，每个桶里表示权值为dis的点，然后链表维护。
复杂度：$O(n+m+W)$，$W$为总权值。

差分约束

$\sum_p^qa[i] ∈ [l,r]$

字典序最小的拓扑序

队列->优先队列
对于dag，按照反图dfs，出栈序列为拓扑序。
dag上找一个环：拓扑后，剩下的点，找一个，顺着走。

ABland Yard (AGC 27 C)

CF div1+div2 D：如果一个人的朋友小于k，那么它不能出去玩，删掉他后，他的朋友们的朋友数也减少1，拓扑。
正难则反，选哪些人很难，于是选哪些人删掉；加边影响的很多，于是改成删边，影响两个人。

二分图匹配

dinic $O(\sqrt n m)$

Life of the Party (ONTAK 2010)

先求最大匹配，然后一定在最大匹配中的点首先是求出的最大匹配中的点。
如果一个点，去掉后，可以再用一个点与它匹配的点匹配，就不一定去掉。
将右边的点，与它匹配的点，之间的边，方向为右->左，剩余点方向为左->右。
然后从剩余点跑，跑到的方向取反，点也不一定在匹配中了。