B: 容易发现 , 显然当区间长度大于
时都有答案
,输出 1 即可,否则区间都满足
,暴力计算答案。
D: 考虑先进行拆位,此时 ,此时操作转换为
, 把每次参与操作的两个点
连边,显然当添加
这条边会令图出现环时,我们可以通过翻转
路径上的所有边达到翻转
的效果。
同时对于任意的连通块 , 我们总可以令
内任意对节点
当前的位翻转,设这个连通块内有
个点当前位为 1, 此时显然有这个连通块操作后的 1 数量
在
区间内且满足
。
注意到题目上 ,这启发我们直接枚举所有连通块的情况,枚举后按照上面的结果我们已经知道了每个连通块当前位的上下界,直接从低到高维护进位进行数位
判可行性即可。
E: 显然有 与存在一个
使得
等价,考虑对
做动态开点懒标记权值线段树, 区间维护
和
的最小值,并维护当前
的最小值作为懒标记,查询时线段树上二分即可。
F: 对 的具有某性质的
计数首先考虑数位
,但这里看上去不好对所有
同时计数,因此我们先考虑如何去检查单独一个
。
那么显然有对于 在二进制下的第
位,如果这一位为
,我们需要选至少一个
满足
且
这一位也为
,否则对于所有我们选了的
,
的这一位都为
。
容易发现选 的过程也像是个数位
,更进一步的,当我们
到第
位时,我们本质上只需要对于
存储是否存在对应的
就可以知道当前位是否可以满足条件,这里显然有
种状态,但是容易发现我们每一步选
可能有多种选择,其中一些选择会导致后续的位不符合条件,因此我们再对当前
所有可能的状态的存在性进行压进另一个大状态,因此现在有
种状态。
那么容易发现 不符合条件当且仅当它在
结束后被转移到大状态内没有任何小状态的情况,显然这样的形式是可以多个
一块转移的,因此再套一层对
的数位
即可。

京公网安备 11010502036488号