January 10, 2022
Table of Contents
40 分朴素分十分好拿，考虑到 T 十分大，也很容易想到接下来要矩阵优化。
具体实现，首先这里需要使用广义矩阵乘法维护 dp 状态，这个相信对于熟悉 动态维护树的最大独立集 的小读者来说一定不是什么难题。。。
然后对于美食节这些特殊事件，没有办法放进矩阵里处理，不过美食节数目不是很多，我们可以拉出来单独处理，美食节与美食节之间在用矩阵乘法。
线段树合并必做习题。
给定一个 1 到 n 的排列，q 次询问，每次给定一个下标区间和一个值域区间求在给定区间内的元素的逆序对数。
很像上个月 abc233 的最后一题，不过区间逆序对没有什么太好的性质，貌似只能分块乱搞。
https://www.luogu.com.cn/problem/P6775
01-背包
有 n 种材料，第 i 种材料有 ai 个。现要制作 m 种菜，每种菜恰好使用 k 个材料并且使用至多两种材料。求是否存在方案，如果存在则给出任意一个方案。
保证 \sigma ai = mk。
首先我们希望材料越少越好，再注意到材料最多只有 m+2。
事实上暴力贪心可以解决 <= m+1 的情况，然后对于 m+2 的情况可以用背包分成两个 <= m+1 的情况，各种证明即可。
需要一些智力。。。寻找一些性质用有限去刻画无限。。。
感觉 这篇题解 写的最好。。
Observation 9. 链树森林中，若以当前节点为根的子树中仅有有限棵链树无法被生成，当且仅当：
– 该点在某一棵链树中是叶子节点，或
– 该点拥有全部四个儿子，且四个儿子代表的子树中都仅有有限棵树无法被生成。
这里的四个儿子分表表示了链树中四种情况，既区分兄弟节点是叶子还是空。
如果既不是叶子，也不是空，那么局部不在链树中。
可以提前把这非链树的输入过滤掉，或者更方便的合并的时候不往下一层递归。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。