洛谷2150 [NOI2015]寿司晚宴
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子，因此我们可以只状压 $<\sqrt{500}$ 的质因子，然后再单...
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子，因此我们可以只状压 $<\sqrt{500}$ 的质因子，然后再单...
Luogu LOJ 分析 首先看到题目里的提示： 对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\cdots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 。 考虑一个暴力做法：枚举边权的相对大小，然后 Kruskal 求最小生成树并用这个提示算答案。 进一步考虑这样的一个做法：钦定一个边集 $S$ 作为前 $|S|$ 小的边，如果这个...
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$ 个互不相同的...