专栏文章

0609

CCap1taL
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip44qel
此快照首次捕获于
2025/12/03 05:51
3 个月前
此快照最后确认于
2025/12/03 05:51
3 个月前
查看原文
在 github 阅读 以查看图片

NFLS T1

你有一个序列 aa，长度为 nn。
有 qq 组查询。每组查询包含五个整数 A,B,C,k,xA, B, C, k, x。
对于每组查询，你需要构造一个新序列 bb，其中：
bi=A×popcnt(ai & x)+B×popcnt(ai ∣ x)+C×popcnt(ai ⊕ x)b_i = A \times \text{popcnt}(a_i \,\&\, x) + B \times \text{popcnt}(a_i \,|\, x) + C \times \text{popcnt}(a_i \,\oplus\, x)
即：
  • & 表示按位与 (AND)
  • | 表示按位或 (OR)
  • ^ 或 ⊕ 表示按位异或 (XOR)
  • popcnt(x) 表示整数 xx 的二进制表示中 1 的个数（即 popcount）
你需要输出序列 bb 中的第 kk 小的元素。
n,A,B,Cn,A,B,C 不重要，值域和询问次数都 <216\lt 2^{16}

题解

首先立刻注意到异或的 popcount 是假的，可以拆成与和或。变成：
bi=(A−C)×popcnt(ai & x)+(B+C)×popcnt(ai ∣ x)b_i = (A-C) \times \text{popcnt}(a_i \,\&\, x) + (B+C) \times \text{popcnt}(a_i \,|\, x)
询问没有很多，每次询问我们可以枚举与和或的 popcount。于是考虑这个问题：
给定数组 aia_i，多次询问，每次询问给定 x,P,Qx,P,Q，要求你求出原数组里有多少 aia_i 满足：
popcnt(ai & x)=Ppopcnt(ai  ∣ x)=Q\text{popcnt}(a_i\,\&\,x)=P\\ \text{popcnt}(a_i\,\,|\,x)=Q\\
只要能解决这个，每次询问我们枚举 16216^2 之后对权值排序，取前 kk 个即可。
朴素做法是遍历 2162^{16} 一个一个算，我们有一个高明的多的 DP。
我们数量不多，我们可以处理出答案数组 ansx,P,Qans_{x,P,Q}。考虑一位一位地处理这个东西。
fi,x,P,Qf_i,x,P,Q 表示考虑了前 ii 个二进制位，前 i−1i-1 为原数组值、后 16−i+116-i+1 位为输入值，与为 PP，或为 QQ 的原数组值数量。
相当抽象，先看初始化，有 f0,v,0,0=∑i=1n[ai=v]f_{0,v,0,0}=\sum_{i=1}^n[a_i=v] 。
即，最开始，数组里的值就是自己原本的值，呈待处理。
我们要解决的问题是，一开始给你 AA，多次询问给出 B,CB,C，需要求出满足 A opt B=CA\ \text{opt}\ B=C 的 AA 的数量
于是这个 DP 的起点就是 AA，终点就是 BB，我们在过程中把 CC 维护进状态。
对于手头上已有的 vv（要求 vv 这一位为 00），若枚举到了第 ii 位，直接放代码感觉更直观
CPP
g[v][AND][OR]+=f[v][AND][OR];
g[v][AND][OR+1]+=f[v|(1<<i)][AND][OR];
g[v|(1<<i)][AND][OR+1]+=f[v][AND][OR];
g[v|(1<<i)][AND+1][OR+1]+=f[v|(1<<i)][AND][OR];
就是在枚举这一位的情况。
不妨来考虑一些更本质的东西。为什么这么做能节约复杂度，或者说，为什么要这样做？这样做的动机是什么？
先只关注 AND 的情况。考虑这样的图：
这描述了一个暴力的过程，对于每个 vv，枚举所有可能的 xx，一个一个 bit 地判断这一位与是否为 11（当然代码里不会体现这一点），记录 popcount，最后穿过去之后变为 (v,x,popcount)(v,x,popcount)，这个三元组的权值 valval 会被累加给 (x,popcount)(x,popcount)。
权值是什么呢，容易发现其实已经隐含了一步映射，我们把 nn 个 aia_i 映射到了更小的值域上，并给每个值赋权了（即在 aa 中的出现次数）
我们发现枚举 (v,x)(v,x) 耗费了大量时间复杂度 O(V2)O(V^2)，但最后我们却不关心 vv 的值，这实在太浪费了！
我们希望避免这种浪费，暂时没有什么思路。来仔细推敲一下这根红色运算线。随着 bit 的推进，我们会发现，我们不再关心这个 bit 之前的 vv 的具体数值，我们只需要保留这个 bit 前面 xx 的数值——毕竟我们最后统计是真的会用到 xx 的。
能不能据此改进呢？哪怕一点点也可以。容易想到这个：
AND 的值不在此画出，实际上是另外一个维度，我们也暂时不太关心它
这样确实减少了状态，具有相同的 (prex,sufx,sufv,AND)(pre_x,suf_x,suf_v,AND) 的状态被合并，而它们的 prevpre_v 我们则不再加以区分。注意到 prexpre_x 和 sufvsuf_v 或 sufxsuf_x 一定无交，直接把其中二者合并，我们的状态数还是 O(V2)O(V^2) 的
但这并没有完全解决我们的问题。你会发现让我们的状态数维持在 O(V2)O(V^2) 级别的罪魁祸首是 sufxsuf_x 和 sufvsuf_v——我们不得不同时记录它们二者，只有这样才能正确地在后面计算 AND。
然后你会立刻发现这蠢到家了——如果两个状态的 prexpre_x、sufvsuf_v 和 ANDAND 都是一样的，那么它们目前的值显然完全一样，sufxsuf_x 的影响完全不会体现，因为它在后面才会被考虑！
那我们自然会想去丢掉这个 sufxsuf_x，会发现很简单，真的直接把它丢掉就行了。我们完全没必要分配 O(V2)O(V^2) 个起点，只需要分配 O(V)O(V) 个起点，在每个 Bit 考虑这一位的 xx 是 00 还是 11，就可以避免记录 sufxsuf_x 了。
当然，对于一个状态，就需要转移到两个状态，代表枚举的 xx 是 00 还是 11。这是非常合理的。
然后你会发现我们做完了，复杂度对了，和之前描述的做法一模一样。核心在于，对于任何一个 bit，它前面的 vv 和它后面的 xx 我们都不关心，于是同 bit 状态数变成了 O(V)O(V)。
如果多维护一个 OR 也是简单的，加个维度多讨论一下就行了，反正这都是省不掉的维度，不用考虑优化，是小问题
多画图讨论一下是极好的啊（赞赏）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...