2024.1 做题记录

P2423 [HEOI2012] 朋友圈

考虑 \(a \oplus b \bmod 2 = 1\) 的限制实际上转化为不同左侧点最多选择两个，因为奇偶性需要不同。

暴力枚举左侧的点集，考虑 B 侧的点，首先需要跟左侧点集任意有边，之后内部还需要是完全图。

B 侧选定点的最大团这个东西是不好做的，但是我们可以借助边的性质。

我们如果按照 B 的奇偶性来分成两类，因为 \(a \oplus b \bmod 2 = 0\)，所以集合内部点两两有边，而第二类又在两个集合中做出了连边。

不难发现如果除去团内的边，实际上这是一张二分图，我们将二分图取补图，这仍然是一张二分图。我们发现，如果在这张图上求 最大独立集，那么在原图上即为最大团。

团要求两两有边，而独立集要求两两没边，将补图还原后两两间必然有边，即为团。

• 引理：最大独立集 = $n \ - $ 最小点覆盖。

最大独立集事实上想要从全集中去掉一些点（尽量少），使得两两间没边，也就是想找最少的点破坏掉所有边（如果有边存在必然有点相连）。正好对应了最小点覆盖。

而最小点覆盖又等于最大匹配。所以我们对补图求最大匹配然后计算即可。

时间复杂度 \(O(|A|^2|B|^2)\)。

code

BZOJ #4664

考虑方案数从前到后并不好表示，因为如果想保证混乱度 \(\le L\)，那么需要记录前一项是什么，还需要记录选了什么，这样的话状态数也许是 \(O(2^nn)\) 的，显然无法接受。

考虑一个插块 dp，设 \(f_{i, j}\) 表示从小到大插入到第 \(i\) 个数，分成了 \(j\) 段的方案数。

转移经典，但是我们发现无法保证混乱度，考虑再设 \(f_{i, j, k}\) 表示从小到大插入到第 \(i\) 个数，分成了 \(j\) 段，总混乱度为 \(k\) 的方案数。

看起来到这就结束了，不过我们发现我们很难考虑一次插值的贡献。事实上，贡献是与邻项强相关的，然而我们的状态并没有记录邻项的值。

考虑一边插值一边计算全局的贡献。具体来说，从小到大给了我们很好的性质，考虑这样一个式子：

事实上这就是差分的前缀和。因为我们从小到大插值，那么未插的地方数字一定比当前值大，为了构造出它，我们给所有连通块的边界位置插上 \(a_i - a_{i - 1}\) 的贡献，一边插值一边算出了整体的贡献。

实现细节上，因为边界只有一边可以产生贡献所以需要再开一维表示边界。

code

accnoi5709 k 大值

事实上也许跟基数排序没什么关系。

考虑值域大概是 \(10^{18}\)，空间正好容得下 \(10^6\)，按照 \(10^{12}\) 确定答案在哪个块里，再按照 \(10^6\) 分块，确定在哪个 \(10^6\) 块里，下一次内部开桶即可。

ps: 事实上值域不是 \(10^{18}\)，而是稍大一些，实现上可以适当调大块长。

P1640 [SCOI2010] 连续攻击游戏

纯题。原本以为是 2-sat 类状物。

将每个阶段设出点，然后每个武器练两条边，只能用一次正好满足匹配的意思，直接匈牙利即可。