202610 杂题选做

QOJ 10506

非常有趣的题目。观察样例不难发现区分两个物品的方法就是两边同时加上一个子集,然后让其中一个超过分界线另一个不超过。

实际上这个观察并不显然,但是 GPT 给了一个比较有力的解释,稍后将给出。

然后剩下的问题是如何快速维护。

你发现首先有两个问题需要处理。第一个是你加入的物品有上线,第二个是每个物品只能用一次。

第二个限制通常都处理方法就是可删除背包。

但是考虑第一个限制,我们可能需要对背包做一些改造。比方说记录 表示到达 同余 的最小重量。 不过你发现改造完之后就很难撤销了。

另一方面是,我们一共有 次撤销。无论如何是不能接受的。

我们还需要一个更强的性质。

我们发现,我们实际上希望用一个子集合将两个物品从中间分开来。

那么,假设存在一种方案区分 ,假设其子集和是 。我们显然有

此时假设有 。我们发现 也是可区分的。

首先如果这个方案里没有 ,那么看上去直接沿用即可。否则你把 踢了换成 。变化量是 。

不妨假设 和 单独称量结果都一样。所以加上这个量显然不会使得 产生变化,因此我们可以直接对余数加减。

后面所有的表达式全部省略掉对 取模了。我们只保留取模后的余数。

那么仍然有

另一方面,左侧显然大于 ,因为这个是正的。

右侧同理。

但是这个性质仍然不够强劲啊。发现还是没有用。

我们还有更加强力的性质。假设 不可比, 不可比,那么 也不可比。

证明其实本质还是上面的交换论证。假设存在区分 的方案 。不妨假设 。另一边是对称的。

如果 没用 ,那么我们可以直接拿 来区分 。

否则,我们根据 和 的大小关系分讨。

如果前者比较大,考虑把 踢掉换成 。影响是 。

和上面的理由一样,我们不会对下取整后的值产生影响,因此我们可以直接对余数进行加减。

然后由于实际上超过 的距离是 。我们有 。换句话说 。

所以 ,,满足了左端点,可以区分 。

否则,把 提了换成 。

不等式推一推发现可以区分 。

过程是类似的。

感觉我的表述有点混乱。反正大概是这样一张图:

(真的有人能看懂吗。)

GPT 给出的观察就是,就是不可区分当且仅当交换物品质量不会改变任意子集的称重结果。

然后仔细想一下就发现这个其实非常对。而且可以很天然的给出不可比传递性的性质。

因为如果 交换不改变子集合, 也不改变,那么先 在 也不会有子集和发生改变。

那么,后续就是划分出这些等价类。

如果两个元素包含了一个可比对,那么就不在一个等价类。否则就在。

因此不可比关系构成的图是一个团。另一方面,我们还发现不可比的点是连续的(因为可比也是有传递性的,不可能出现断点)。

我们只需要找到相邻的两个元素,检查这两个元素是否满足条件即可。

套路的,我们可以考虑线段树分治来解决。

CF2268C KiaKio and Energy Intervals

赛时看到区间 发狂了疯狂优化笛卡尔数启发式分裂状物。然后得到了一个 的奇异搞笑做法。

首先注意到位运算相关,因此我们考虑从高位往低位贪心。我们要检测的是是否有一个答案是 的超集(这是从高到低贪心和二分相比的方便之处)。

换句话说,答案和 按位与之后的结果是 。

那么我们可以考虑先把所有数都按位与一下。那么首先答案和区间最大值需要按位与,那么只有区间最大值是 的时候答案才是有意义的。

因此我们只需要将所有数和 按位与,然后扔到可持久化 Trie 树上随便做一下即可。

值得一提的是,其实也不需要可持久化 Trie 树。因为 是全集,因此我们只需要找一下是否存在 即可。

P8366 题

这也太无聊了。

注意到只有三种情况:

直接子序列自动机全扔到状态里 DP 即可。

复杂度七次方。

P7949 左方之地

牛大了。

首先考虑什么时候有解。注意到每个数都是从 开始异或一个 的数得到的。

因此我们把所有 的数抽出来,考虑其生成空间。如果维度小于 就爆了,因为肯定有一个元素生成不出来。

那么假设维度是 是否一定可行。

这个题目看上去很像格雷码的描述,因而可以从格雷码的角度去思考。但是格雷码是相邻元素差一位。 我们希望把这个转化一下。

首先我们找到一组基底,满足每个元素的 。这可以通过一次把每个满足条件的元素插入线性基得到。

然后我们有 种组合这 个元素的方式,里面每个元素都不同,恰好构成了 的排列。

我们希望相邻两项只差一个 的数,考虑特殊化一下,相邻两项差一个基中的元素。

你发现考虑一个 位二进制数 ,如果第 位是 就异或上第 个元素,否则不异或。

然后你发现每个二进制数唯一对应了一个元素。我们发现按照格雷码的顺序排列这个二进制数,把对应的排列取出来就对了。相邻两项差一个基中的元素。

本质上是给每个向量乘上一个矩阵换基。然后相差一个元素的性质就保留到了相差基里一个元素。

也有硬构造的方法。但是这个做法牛大了所以不说。

P10105 游戏

考虑枚举中心点。假设中心点到三个点的距离是 ,那么有

解个方程就解出来了。

然后我们考虑是否存在满足条件的点。考虑求出每个子树的最大深度。我们肯定是先选择深度最大的满足给 中最大的深度,深度次大的给 中次大的深度,第三大的给剩下的一个。

因此实际上我们只会取出这个点深度最大的三个儿子。

然后对于所有询问,要查询是否至少有一个偏序这个询问的节点。三位偏序问题,CDQ 一下即可。

P10254 口吃

这也太难了!

首先考虑计数怎么做。

我们考虑从小往大插入元素,每个元素的逆序对个数就是插入位置后面的所有元素。

换句话说,第 次插入的元素可以贡献 到 之间任意一个数量的逆序对。我们可以直接前缀和优化一下。

接下来考虑如何对题目中提到的式子进行计数。

你注意到如果还是直接插入的话我们需要给后缀所有数的排名 ,转移的时候需要维护每个后缀的和,比较难做。

复杂度至少是四次方的。

我们考虑拆一下贡献。我们来考察一次临项交换对这个值的贡献是什么。你会发现,其中一个位置增加 ,值增加 。另一个位置减少 ,值减少 。因此贡献就是 。

而我们每次挑一个逆序对交换都会造成一次贡献。因此假设 是一对逆序对,那么他对值的贡献就是 。最后加上 乘上排列个数。

因此我们希望求出来所有满足条件的排列所有逆序对的 之和。

但是注意到这里一项仍然有两个数,我们仍然不方便计算。我们继续拆一下贡献,把贡献拆到每个 上面。

我们依旧从小到大插入。假设当前的数是 ,那么 在排列中的贡献就是 乘上 后比 小到元素减去 前比 大的元素。

我们分开计算 后比 小到元素和 前比 大的元素。因为后者涉及未来的状态,比较难办。不过我们可以从大往小插入再做一次。

具体的,如果插入第 个数的时候选择了贡献 个逆序对,那么就会对题目的式子贡献 。

这个仍然可以前缀和优化一下。

然后做完了。

AT_arc176_d Swap Permutation

牛大了。

首先考虑转概率。

注意到直接求不好求,我们考虑转概率。

考虑期望的线性性质转化成每一对数做贡献的次数。我们考虑枚举一个数 ,相邻两个数做贡献当且仅当一个大一个小,我们用 到 分别表示一下这四种状态,然后转移是容易的,你可以直接算出来剩下的大于或者小于的数的个数,然后算出系数。

然后系数可以矩阵快速幂。

值得一题的是,维护每对数最终的位置往往是不好做的。因为可能出现边界这种情况,而且你可能会慢慢移动到边界。

实际上可以写成多个的数相加的情况下在满足总数好求的情况下都可以转概率期望线性性来拆贡献(当前前提是拆完之后每项涉及的变量更少了或者以其他方式更好求了)。其实可能可以有一些其他的组合意义来解释(例如把式子写出来交换内外求和号,实际上期望的线性性也是这么证的),但是期望线性性是对认知负担最小的一个理解方式。

实际上感觉有些时候转概率之后会更有可能想到比较激进的拆贡献方法(比如这个题目的拆到每个位置上面,计算每个位置上的概率)。可能是因为期望线性性不要求独立,所以可以更大胆的做一些贡献的拆而不用关心各个局部之间如何相互影响。


202610 杂题选做
https://blogs.sving1024.top/posts/49563/
发布于
2026年10月14日
许可协议