补题记录（不定时更新）

2019/5/26：

河北省赛, A I J，几何转图判连通；cdq 分治；贪心拓扑排序匹配。
HDU - 6326，树上勇者斗恶龙，转有根树后，贪心的取，每取一个点就往父节点合并，并查集维护。
计蒜之道第一场 C，树 dp，边权两两不同，枚举 $gcd$ 保证复杂度严格 $O(n^2)$。
uestc Training for dp I，数位 dp，用个 pair 很好写。

2019/5/27：

HDU - 6540，省赛树 dp，$dp[i][j]$ 表示以 $i$ 结点为根，选中关键点种离 $i$ 最大距离为 $j$ 的方案数，枚举深度对复杂度的贡献是严格 $O(n^2)$ 的。
HDU - 6532，省赛 A 费用流，鬼畜建图。
ZOJ - 4100，浙江省赛 A，线段树下标维护 $size$，连边先在连通块内连，再从大到小连，要优化常数。
牛客练习赛 46，D 二分答案，贪心打怪兽。E 鬼畜树状数组。

2019/5/28：

华东理工校赛 F，hihocoder 1384，倍增 + 反向倍增，均摊复杂度 $O(nlogn)$。
GYM - 102082J，染色查询连通子图大小，染色是一个点一个点染的，所以对每种颜色用一个 set 维护，set 维护插入的点在 dfs 序上相同颜色的前驱和后继结点，然后算一算贡献。
计算之道第二场 C，$dp[i][j]$ 表示前 $i$ 个数，选了第 $i$ 个数的子序列长度为 $j$，另一个子序列最后一个数的最小值，转移时枚举长度 $j$，看看可以插入在哪个序列。

利用 $meet$ $in$ $the$ $middle$ 计算最大团 & 最大独立集

首先，原图的最大独立集 = 补图的最大团。
状压一下。
假设有 $n$ 个点。
先分成 $S_1$ $S_2$ 两堆，$f[i]$ 表示选了 $S_1$ 堆子集 $i$ 的点中的最大团，$g[i]$ 表示选了 $S_2$ 堆子集 $i$ 的点中的最大团，然后两堆分别用高维前缀和计算出来，计算一堆的复杂度是 $O(2^{\frac{n}{2}}\frac{n}{2}^{2})$。

for (int i = 0; i < s1; i++)
    f[1 << i] = 1;
for (int i = 0; i < 1 << s1; i++) {
    for (int j = 0; j < s1; j++) if (!(i & (1 << j))) {
        bool flag = true;
        for (int k = 0; k < s1; k++) if (i & (1 << k))
            flag &= G[j][k];
        f[i | (1 << j)] = max(f[i | (1 << j)], f[i] + flag);
    }
}

最后合并的时候，枚举 $S_1$ 堆的状态，把 $S_2$ 堆中与 $S_1$ 堆中的点没有边相连的消去。然后统计答案。

for (int i = 0; i < 1 << s1; i++) {
    int flag = (1 << s2) - 1;
    for (int j = 0; j < s1; j++) if (i & (1 << j)) {
        for (int k = 0; k < s2; k++) if ((flag & (1 << k)) && !G[j][k + s1])
            flag ^= 1 << k;
    }
    res = max(res, f[i] + g[flag]);
}

还有第二种方法，$f[sta]$ 表示 $S_1$ 堆 $sta$ 状态的点集和 $S_2$ 堆状态点集都连有边。比如 $f[101]=011$ 表示 $S_1$ 堆里面编号为 $1,3$ 的点和 $S_2$ 堆里面编号为 $2,3$ 右边，同时 $sta$ 是团。

$g[sta]$ 表示 $S_2$ 堆状态为 $sta$ 的点集中的最大团大小。

答案就是，然后 $max(\sum_{i=0}^{1<<s_1}(pointnum(sta) + g[f[sta]]))$

相比最大团模板，$meet$ $in$ $the$ $middle$ 做法是复杂度稳定，还可以做最大加权独立集，对高维前缀和稍作修改就可以了。

区间 $k$ 段子段和最大

利用线段树维护区间最大子段，累加答案然后对子段取反，继续找，直到 $k$ 段或者最大子段为负停止，可以用费用流证明正确性，反流负费用之类的。

区间取反操作可以维护区间最小子段，然后取反就是最大最小的交换。

区间加等比等差数列

维护区间和，区间首项。

图上的路径 $xor$ 问题

求无向图一个点到另一个点的 $xor$ 路径。

可以求出任意一条从一个点到另一个点的 $xor$ 路径，同时把图中的环插入线性基。因为一个点的一条 $xor$ 路径可以看成是这条路径和环的 $xor$，通过线性基就能求出每一条路径。以此解决一些相关的问题。

可持久化 $01Trie$ 的一些主要应用

求区间最大连续 $xor$ 和。

从左到右扫一遍，边扫边把前缀 $xor$ 和加入到 $01Trie$ 中，一边更新答案，这里可以不用可持久化，如果要做区间查询的就要。
$root[i]$ 插入 $pre[i - 1]$，这样就是 $update$ 完再 $query(pre)$。

要做区间查询就要可持久化 + 分块，$f[i][j]$ 表示从 $i$ 块到位置 $j$ 的最大连续 $xor$ 和，$O(n^{1.5})$ 预处理，查询 $O(\sqrt{n})$，查询 $f[bl[L]+1][R]$ 还有左边不完整的块。

int getAns(int L, int R) {
    int res = 0;
    if (bl[R] - bl[L] <= 1) {
        for (int i = L; i <= R; i++)
            res = max(res, query(root[i], root[L - 1], pre[i]));
        return res;
    }
    res = f[bl[L] + 1][R];
    for (int i = L; i <= blo * bl[L]; i++)
        res = max(res, query(root[R + 1], root[i], pre[i - 1]));
    return res;
}

求树上路径的点权与 $val$ 的最大 $xor$

按 $dfs$ 的顺序把点权插入可持久化 $01Trie$ 中，

1	update(root[u], root[f], w[u], 16);

那么对于一个查询 $u,v$，我们有两种方法，一种是树剖，一种是倍增 $LCA$，倍增 $LCA$ 的方法是求出他们的 $lca$，然后从高位到低位看看这一位是否有

u = root[u];
v = root[v];
lca = root[lca];
sum[ch[u][idx ^ 1]] + sum[ch[v][idx ^ 1]] - 2 * sum[ch[lca][idx ^ 1]] > 0

然后按位获得答案。

或者是在求 $lca$ 的时候每跳一次父节点就 $query$ 一次，但是要注意此时父节点是没有被算进去的，所以要注意细节。

int getAns(int x, int y, int val) {
    if (deep[x] < deep[y])
        swap(x, y);
    int res = 0;
    for (int i = 21; i >= 0; i--) if (deep[fa[x][i]] >= deep[y]) {
        res = max(res, query(root[x], root[fa[x][i]], val, 16));
        x = fa[x][i];
    }
    if (x == y)
        return max(res, val ^ w[x]);
    for (int i = 21; i >= 0; i--) if (fa[x][i] != fa[y][i]) {
        res = max(res, query(root[x], root[fa[x][i]], val, 16));
        res = max(res, query(root[y], root[fa[y][i]], val, 16));
        x = fa[x][i];
        y = fa[y][i];
    }
    res = max({res, val ^ w[fa[x][0]], val ^ w[x], val ^ w[y]});
    return res;
}

$Gauss$

把模板的代码掌握了就可以。

小数版本一般用来辅助求解那些难以转移的概率 $dp$，$01$ 版本是解决开关问题。

线性基应用

直接贴个师兄的线性基学习总结

概率期望相关

一般都是期望 $dp$ 或者概率 $dp$。
期望 $dp$ 大多是从后往前，转移大多是

1	dp[i] = 1 / x * (dp[i + 1] + v[i]);

诸如这种形式。

求期望还可以利用期望的可加性，用概率 $dp$ 求出每一个 $dp[i]$，然后 $ans += dp[i] * v[i]$

求概率 $dp$ 的转移公式可以列式子，然后移项获得。

利用主席树和 $hash$ 解决最短路

当 $dis$ 无法直接用数组表示的时候。

比如边权是 $2^w$ 的图，让你找出从 $S$ 到 $T$ 的最短路。
- 主席树维护 $dis[i]$ 的一个 $01$ 串，还有 $hash$ 值，$dis$ 之间的比较利用 $hash$，从高位开始比较，如果 $hash$ 值相同则往低位走，不同则往高处走，复杂度是 $O(logn)$ 的。
- 而更新操作，你可以找 $w$ 这一位是否为 $0$，是的话直接更新，否则就找往后第一个 $0$ 的位置，然后把中间这一段连续的 $1$ 修改为 $0$，有个 $trick$ 直接把中间这段的结点连到一棵全 $0$ 的树上。if (l <= L && R <= r) rt = 0;
比如一个点权有优先级的图，让你找出从 $S$ 到 $T$ 的一条优先级大的点尽量少的路径。
- 也是用主席树维护 $dis$，还有 $hash$ 值，只不过这道比较直观，不用进位，直接写就可以。

数位 dp 求和

$dp.first$ 表示符合条件的个数，$dp.second$ 表示和。

for (int i = 0; i <= top; i++) {
    pii t = dfs(cur - 1);
    add(res.first, t.first);
    add(res.first, i * pow(10, cur) * t.first + t.second);
}

倍增 + 二分或者倍增 + 反向倍增

若当前区间合法，则继续倍增右端点，直到遇到一个不合法的右端点，再在这中间进行二分，或者反向倍增，这样子暴力处理可以保证复杂度是均摊的 $O(nlogn)$。