洛谷4294 [WC2008]游览计划
Luogu 分析 斯坦纳树模板题。 设 $f_{i, S}$ 表示 $i$ 号结点，与其它节点连通性为 $S$ 时的最小代价。 转移分两种情况： 由子集转移而来 第二个方程是有后效性的，但是它长得很像三角形不等式，所以可以跑最短路转移。 代码 //It is made by M_sea #include <algorithm> #include <iostream...
Luogu 分析 斯坦纳树模板题。 设 $f_{i, S}$ 表示 $i$ 号结点，与其它节点连通性为 $S$ 时的最小代价。 转移分两种情况： 由子集转移而来 第二个方程是有后效性的，但是它长得很像三角形不等式，所以可以跑最短路转移。 代码 //It is made by M_sea #include <algorithm> #include <iostream...
AtCoder 分析 考虑把边权转为点权。设每个点的点权为所有与它相连的边的边权的异或和。 那么可以发现，$u$ 到 $v$ 的路径上的边权异或 $w$，相当于 $u$ 和 $v$ 的点权异或一个 $w$。 于是问题变成给你一些数，每次可以选出两个数并让它们异或一个数，求让所有数变为 $0$ 的最小操作次数。 显然可以先贪心地去消，把所有相同的先消掉。这样子会剩下至多 $15$ 个互不相同的...
Luogu 分析 考虑费用流。对于每个球队建一个点，向汇点连边；对于每场比赛建一个点，从源点向其连 $1$ 边、其向对应的两个球队连 $1$ 边，表示只有一个队能赢球。 考虑加入费用。注意到 $x+y$ 固定，于是 $Cx^2 + Dy^2$ 是关于 $x$ 的凹函数，因此可以使用费用递增的技巧。具体的，我们先将后面全负的代价算入答案中，然后依次连费用为 $C(x + 1)^2 + D(y ...
Luogu 分析 这可以看作，如果 $i, j$ 都选则有 $b_{j, i}$ 的收益，如果 $i$ 选了则有 $c_i$ 的代价，求最大收益。 这是一个很经典的问题，考虑使用最小割建图。 对于每个数，从源点向其连 $0$ 边表示不选，从其向汇点连 $c_i$ 边表示选。 对于每个 $b_{j, i}$，新建一个点 $x$，从源点向 $x$ 连 $b_{j, i}$ 边，然后从 $x$ ...
Codeforces 分析 设 $f_{i, j}$ 表示第一段到了 $i$，第二段到了 $j$ 的最大长度。容易写出 $\mathcal{O}(n^3)$ 的 DP。 考虑优化。设 $maxmod_k$ 表示最大的满足 $a_j\equiv k\pmod 7$ 的 $f_{i, j}$，$maxnum_k$表示最大的满足 $a_j = k$ 的 $f_{i, j}$。于是转移变为 每次计...
Luogu 分析 显然两个手环增加非负整数亮度，等于其中一个增加一个整数亮度。 设亮度改变了 $c$，则新的差异值为 前面两项是定值；带 $c$ 的两项是关于 $c$ 的二次函数，而且因为 $n>0$，所以有最小值，可以直接算出来；最后一项可以倍长 $a$ 并翻转，然后和 $b$ 卷积即可求出每个旋转角度的值，取个 $\max$ 即可。 代码 //It is made by M_se...
CodeForces 分析 考虑点分治，那么需要考虑如何拼合两条路径。 设根到 $x$ 的路径上的数是 $d_1$，根到 $y$ 的路径上的数是 $d_2$，根到 $y$ 的距离为 $dep$。那么若 $x\to y$ 这条路径合法，则需要满足： 这样子两条路径就独立了，分别存下来后枚举 $y$ 统计即可。 代码 //It is made by M_sea #include <alg...
Luogu BZOJ 分析 异或满足可减性，所以可以维护前缀和，然后 $\mathrm{a[p]\ xor\ a[p+1]\ xor\ ...\ xor\ a[n]\ xor\ x=s[p-1]\ xor\ s[n]\ xor\ x}$ 然后就只要维护$s[]$。添加很好维护，重点是如何查询。 此时查询转变为：已知$val=\mathrm{s[n]\ xor\ x}$，求一个$p\in[l-...
BZOJ 分析 正着很难想，考虑反着做。 已知一个非降序列，将其分成尽量少的几段，使得每一段对应一个合法的双端队列。 然后发现一个合法的双端队列，一定满足下标先递减再递增。 然后就可以先sort，再贪心地凑。 对于相同的数，它们的顺序是可以交换的。显然下标递增或递减时最优。 然后就可以按照相同的数去划，每一个区间往后放，尽量的使得这样的单谷区间少。 举一个样例的例子： $A=[[0],[3,...