202610 杂题选做

QOJ 10506

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

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

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

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

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

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

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

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

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

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

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

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

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

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

那么仍然有

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

右侧同理。

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

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

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

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

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

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

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

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

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

否则，把 提了换成 。

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

过程是类似的。

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

（真的有人能看懂吗。）

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

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

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

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

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

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

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

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

• 代码

CF2268C KiaKio and Energy Intervals

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

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

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

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

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

• 代码

P8366 题

注意到只有三种情况：

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

复杂度七次方。

• 代码

P7949 左方之地

牛大了。

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

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

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

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

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

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

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

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

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

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

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

• 代码

  AT_arc160_f Count Sorted Arrays

  超级牛逼题目。

首先考虑一个转化。

考虑把一个序列转化成 个 字符串，第 个串中所有小于 的位置都置 。那么一个排列被排序当且仅当他对应的所有字符串都被排好序了（值域为 是一个非常有用的性质，因为满足条件的字符串只有 个，而排列有 个）。

我们对每一个字符串建点，一个排列唯一对应了 到 的一条路径，连边就是把一个位置的 改成 。

QOJ 3307. 树上查询 17

口胡了一个比较大的做法。

P10105 游戏

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

解个方程就解出来了。

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

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

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

• 代码

P10254 口吃

这也太难了！

首先考虑计数怎么做。

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

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

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

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

复杂度至少是四次方的。

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

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

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

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

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

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

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

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

然后做完了。

• 代码