题解 P5616 【[MtOI2019]时间跳跃】
CYJian
·
·
题解
时间跳跃
首先给出一个结论: 对于 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) 的…可以通过本题…