自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:12:35，当前版本为作者最后更新于2019-11-03 17:32:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

时间跳跃

首先给出一个结论: 对于 $n$ 条边, 这 $n$ 条边能组成一个 $n$ 边形当且仅当 最长边边长小于其余所有边长之和…

啥? 你问我怎么证? 三角函数会不会?? 三角形剖分也行啊…

Subtask1 20pts

给这一档部分分纯属好玩…

发现下发的样例中有了 $n=1,2,3,4,5$ 的点, 然后只需要算 $n=6,7,8,9,10$ 的点…手算就有 $20$ 分了QwQ…

Subtask2 30pts

如果您是猛汉, 那么就可以手算 $n=11, 12, 13, 14, 15, 16, 17, 18, 19, 20$ 的点, 然后打表就行了…

如果您是暴力选手, 那么就可以 $O(2^n)$ 枚举子集之后计算贡献…

Subtask3 15pts

首先我们可以发现, 我们对于一个边集, 其实是只关心 最长边的长度 和 所有边的长度之和 的…

然后可以暴力dp: 设状态 $f[i][j][k]$ 表示考虑长度为 $1$~$i$ 的边, 选出 $k$ 条出来, 长度和为 $j$ 的方案数…

然后我们可以发现, 我们每一次只需要统计: 当 $i$ 作为最长边的时候, $1$~$i-1$ 所组成的所有边集的方案对 $i$ 的贡献就行了…(这一步就是求每一次加入一条边的增量…)

那么我们就只需要统计, 有多少在 $1$~$i-1$ 中选出边数为 $k$ 的边集, 长度之和大于 $i$…

这个我们只需要在每一次 $dp$ 加入长度为 $i$ 的边的时候统计就好了…

然后暴力统计, 复杂度 $O(n^4)$ …

Subtask4 15pts

我们发现, 上一个算法中 $dp$ 的第二维我们要 $O(n^2)$ 的空间去存储…

但是实际上很没有必要…

我们考虑补集转化: 每一次统计所有的方案, 然后统计不合法的方案就行了…

发现: 不合法的方案就是 除去最长边后, 其余边的长度和小于等于 $i$…

然后这样子我们就可以把第二维压缩至 $O(n)$ 级别了…

统计的时候也就只要 $O(n^3)$ 去计算了…

考虑怎么计算所有集合的贡献和:

其实就是下面这个式子:

$$\sum_{i=1}^{n} i \times \binom{n}{i}$$

意思就是: 从 $n$ 条边中选出 $i$ 条来放到边集中, 这样的边集的权值为 $i$, 那么总贡献就是这个的和…

每次统计总贡献的复杂度就是 $O(n)$ 的…

所以总复杂度是 $O(n^3)$ …

Subtask5 20pts

还是考虑这个 $dp$ 的做法…

第二维是没法压缩了…

然后我们发现, 事实上我们在计算答案的时候并不需要第三维的限制, 只是计算时当做一个权重乘上去…

我们考虑能不能在 $dp$ 的时候就把这个权重给带进去…

考虑设状态 $f[i][j]$ 表示前 $i$ 条边中选出边长和为 $j$ 的方案数(第二维用 ${\rm Subtask4}$ 中的方法压缩)

再设状态 $g[i][j]$ 表示前 $i$ 条边中选出边长和为 $j$ 的权值和…

考虑怎么转移:

首先 $f$ 的转移很显然就是一个背包…

考虑 $g$ 的转移: 我们考虑加入一条长度 $i+1$ 的边加入边集, 那么如果是从 $g[i][j-i-1]$ 转移到 $g[i +1][j]$, 那么 就会在 $g[i][j - i - 1]$ 的所有状态的边集中加入一条长度为 $i+1$ 的边…然后考虑$g[i][j - i - 1]$ 的不同的边集个数是 $f[i][j - i - 1]$ 那么在每一个边集中加入一条边的权值和, 就等价于在原本的权值和的基础上加上等同于边集的个数的数…

这样我们就有了这个转移:

$$g[i][j] = g[i-1][j]+g[i-1][j-i]+f[i-1][j-i]$$

这样就可以把状态数压缩至 $O(n^2)$ 的级别…

由于状态之间的转移是 $O(1)$ 的, 所以复杂度就是 $O(n^2)$ 的…可以通过本题…