202610 杂题选做
QOJ 10506
非常有趣的题目。观察样例不难发现区分两个物品的方法就是两边同时加上一个子集,然后让其中一个超过分界线另一个不超过。
实际上这个观察并不显然,但是 GPT 给了一个比较有力的解释,稍后将给出。
然后剩下的问题是如何快速维护。
你发现首先有两个问题需要处理。第一个是你加入的物品有上线,第二个是每个物品只能用一次。
第二个限制通常都处理方法就是可删除背包。
但是考虑第一个限制,我们可能需要对背包做一些改造。比方说记录
另一方面是,我们一共有
我们还需要一个更强的性质。
我们发现,我们实际上希望用一个子集合将两个物品从中间分开来。
那么,假设存在一种方案区分
此时假设有
首先如果这个方案里没有
不妨假设
后面所有的表达式全部省略掉对
那么仍然有
右侧同理。
但是这个性质仍然不够强劲啊。发现还是没有用。
我们还有更加强力的性质。假设
证明其实本质还是上面的交换论证。假设存在区分
如果
否则,我们根据
如果前者比较大,考虑把
和上面的理由一样,我们不会对下取整后的值产生影响,因此我们可以直接对余数进行加减。
然后由于实际上超过
所以
否则,把
不等式推一推发现可以区分
过程是类似的。
感觉我的表述有点混乱。反正大概是这样一张图:


(真的有人能看懂吗。)
GPT 给出的观察就是,就是不可区分当且仅当交换物品质量不会改变任意子集的称重结果。
然后仔细想一下就发现这个其实非常对。而且可以很天然的给出不可比传递性的性质。
因为如果
那么,后续就是划分出这些等价类。
如果两个元素包含了一个可比对,那么就不在一个等价类。否则就在。
因此不可比关系构成的图是一个团。另一方面,我们还发现不可比的点是连续的(因为可比也是有传递性的,不可能出现断点)。
我们只需要找到相邻的两个元素,检查这两个元素是否满足条件即可。
套路的,我们可以考虑线段树分治来解决。
CF2268C KiaKio and Energy Intervals
赛时看到区间
首先注意到位运算相关,因此我们考虑从高位往低位贪心。我们要检测的是是否有一个答案是
换句话说,答案和
那么我们可以考虑先把所有数都按位与一下。那么首先答案和区间最大值需要按位与,那么只有区间最大值是
因此我们只需要将所有数和
值得一提的是,其实也不需要可持久化 Trie 树。因为
P8366 题
这也太无聊了。
注意到只有三种情况:
直接子序列自动机全扔到状态里 DP 即可。
复杂度七次方。
P7949 左方之地
牛大了。
首先考虑什么时候有解。注意到每个数都是从
因此我们把所有
那么假设维度是
这个题目看上去很像格雷码的描述,因而可以从格雷码的角度去思考。但是格雷码是相邻元素差一位。 我们希望把这个转化一下。
首先我们找到一组基底,满足每个元素的
然后我们有
我们希望相邻两项只差一个
你发现考虑一个
然后你发现每个二进制数唯一对应了一个元素。我们发现按照格雷码的顺序排列这个二进制数,把对应的排列取出来就对了。相邻两项差一个基中的元素。
本质上是给每个向量乘上一个矩阵换基。然后相差一个元素的性质就保留到了相差基里一个元素。
也有硬构造的方法。但是这个做法牛大了所以不说。
P10105 游戏
考虑枚举中心点。假设中心点到三个点的距离是
解个方程就解出来了。
然后我们考虑是否存在满足条件的点。考虑求出每个子树的最大深度。我们肯定是先选择深度最大的满足给
因此实际上我们只会取出这个点深度最大的三个儿子。
然后对于所有询问,要查询是否至少有一个偏序这个询问的节点。三位偏序问题,CDQ 一下即可。
P10254 口吃
这也太难了!
首先考虑计数怎么做。
我们考虑从小往大插入元素,每个元素的逆序对个数就是插入位置后面的所有元素。
换句话说,第
接下来考虑如何对题目中提到的式子进行计数。
你注意到如果还是直接插入的话我们需要给后缀所有数的排名
复杂度至少是四次方的。
我们考虑拆一下贡献。我们来考察一次临项交换对这个值的贡献是什么。你会发现,其中一个位置增加
而我们每次挑一个逆序对交换都会造成一次贡献。因此假设
因此我们希望求出来所有满足条件的排列所有逆序对的
但是注意到这里一项仍然有两个数,我们仍然不方便计算。我们继续拆一下贡献,把贡献拆到每个
我们依旧从小到大插入。假设当前的数是
我们分开计算
具体的,如果插入第
这个仍然可以前缀和优化一下。
然后做完了。
AT_arc176_d Swap Permutation
牛大了。
首先考虑转概率。
注意到直接求不好求,我们考虑转概率。
考虑期望的线性性质转化成每一对数做贡献的次数。我们考虑枚举一个数
然后系数可以矩阵快速幂。
值得一题的是,维护每对数最终的位置往往是不好做的。因为可能出现边界这种情况,而且你可能会慢慢移动到边界。
实际上可以写成多个的数相加的情况下在满足总数好求的情况下都可以转概率期望线性性来拆贡献(当前前提是拆完之后每项涉及的变量更少了或者以其他方式更好求了)。其实可能可以有一些其他的组合意义来解释(例如把式子写出来交换内外求和号,实际上期望的线性性也是这么证的),但是期望线性性是对认知负担最小的一个理解方式。
实际上感觉有些时候转概率之后会更有可能想到比较激进的拆贡献方法(比如这个题目的拆到每个位置上面,计算每个位置上的概率)。可能是因为期望线性性不要求独立,所以可以更大胆的做一些贡献的拆而不用关心各个局部之间如何相互影响。