2025.9.18 模拟赛

分段

位运算 状压dp 前缀和

首先看到一段区间的异或和就可以想到前缀和，先令 $p_i={\oplus }_{j=1}^i{a}_j$，于是我们的要求就变成了对于每一个 $i$ 求出 $\underset{j=0}{\overset{i}{\max }}{p}_j+(p_j\oplus p_i)$。

• [I] 容易想到亦或是不进位的加法，而通过与运算可以得到所有要进位的位，因此有恒等式 $A+B=(A\oplus B)+2\times (A\&B)$，变形得到 $A\oplus B=A+B-2\times (A\&B)$。

应用到原式得到 $p_j+(p_j\oplus p_i)=p_j+p_i+p_j-2(p_i\&p_j)$，即 $p_i+2\times (p_j-p_i\&p_j)$。而 $p_j-p_i\&p_j$ 实际上是 $p_j$ 减去所有 $p_i$ 和 $p_j$ 共有的 $1$ 的位，当 $p_j$ 此位为 $0$ 或者 $p_i,p_j$ 均为 $1$ 时答案为 $0$，否则为 $1$，发现和 $p_j\&\sim p_i$ 的逻辑一样（$\sim$ 是取反）。

• [p] 所以我们的任务就变成了对于每一个 $p_i$，找一个 $p_j$ $(j<i)$ 使得 $p_i+2(p_j\&\sim p_i)$ 最大，答案就是这个表达式的值。

于是我就理所应当地想到了 01 字典树，毕竟涉及到位运算。对于我们需要配对的 $p_i$，贪心地从高到低枚举每一位，如果 $p_i$ 这一位是 $1$，那么优先走 $1$ 的那边，否则走 $0$ 的那边。但是如果 $p_i$ 这一位是 $0$ 的话，问题就来了，$1$ 和 $0$ 的两边都能走，如果都走的话那么时间复杂度就会爆炸。

具体来说，如果 $p_i$ 当中有 $x$ 个 $0$，那么单次查询最坏时间复杂度将会飙到 $\mathcal{O}(2^x{\log }_{2}n)$。当然，这里 $x$ 的期望是 $\frac{{\log }_{2}V}{2}$ 的，由于值域与 $n$ 同阶（其实是分不清楚），单次查询期望时间复杂度是 $\mathcal{O}(\sqrt{n}{\log }_{2}n)$ 的，当然可能会被极端数据卡掉。

不过我想到了一个妙招，就是把所有数取反了之后做按位并，答案再取反和直接做按位与是一样的，因此对于 $0$ 多的就做按位并，$1$ 多的就做按位与，这样子最坏时间复杂度就控制到了 $\mathcal{O}(n\sqrt{n}{\log }_{2}n)$，但变化不大。

• [c] 我就写的这个，挂 $35$ 分。

其实我们离正解很近了。对于一个 $0$ 位，字典树当中需要往两边递归导致复杂度爆炸，但是实际上我们并不需要实际递归下去。回到原式问题之中：

• [?] 我们为什么要用 01 字典树？
• [!] 因为它可以记录之前所有位的前缀。

也就是对于一个数，它必须在我们查询的前缀中才能被选中（也就是前缀是 $1$ 的地方这个数也必须是 $1$，而 $0$ 的地方任意）。这很像什么？前缀必须是我们选择的数的子集，所以我们会想到什么？子集 DP！

但是子集 DP 是离线的，如果非要在线处理需要枚举新加入的数的所有子集，这当然会超时，我们也不需要这种方式。可以把下标存进去，DP 的时候取 $\min$ 用来最后判断是否在要求的前缀 $[0,i]$ 中。

设 $d{p}_i$ 表示所有包含 $i$ 的超集中，最小的下标。收集型的转移就是枚举 $i$ 中未出现 $1$ 的位，然后对下标取最小值，即 $d{p}_i=\underset{j\notin i}{\min }(d{p}_{i|j})$。这个预处理的时间复杂度是 $\mathcal{O}(n{\log }_{2}n)$ 的。

对于查询，我们还是从高到低贪心地枚举位，尝试将这一位变成 $1$，不过所选择的数必须包含已选的前缀（即当前的 $ans$）且被包含在前缀 $[0,i]$ 中。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

• [n] 这道题目思维性质还是很强的，最开始的前缀和转换很简单但是位运算的推导需要灵活应用恒等式。最难的部分就是查询了，很多人像我一样都想到了在线地添加元素并查询，而详细用法的数据结构就是 01 字典树了，但是对于按位与很难解决需要双边递归的问题。其实只需要注意到 01 字典树的本质——高位前缀，转变思路离线下来用子集 DP 模拟前缀被覆盖的过程，并记录下标以满足 $[0,i]$ 的前缀限制条件即可。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5, kLog = 22;
 
LL a[kMaxN], dp[1 << kLog], n, ans;
 
LL query(LL x, LL p) {
  LL res = 0;
  for (LL i = kLog - 1; i >= 0; i--) {
    if (!(x & (1 << i)) && dp[res | (1 << i)] <= p) {
      res |= 1 << i;
    }
  }
  return x + 2 * res;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  fill(begin(dp), end(dp), 1e9);
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] ^= a[i - 1];
    dp[a[i]] = min(dp[a[i]], i);
  }
  dp[0] = 0;
  for (LL i = (1 << kLog) - 1; i >= 0; i--) {
    for (LL j = 0; j < kLog; j++) {
      if (!(i & (1 << j))) {
        dp[i] = min(dp[i], dp[i | (1 << j)]);
      }
    }
  }
  for (LL i = 1; i <= n; i++) {
    ans ^= i * query(a[i], i);
  }
  cout << ans << '\n';
  return 0;
}

删除

我本来写了个简单的区间 DP，发现有些情况满足不了，所以就 WA $0$ 分了。

覆盖

啥也没写。

求和

啥也没写

总结

总分：$35+0+0+0=35$。

这次考试不咋行，全肝 T1 最后没写出来，其实我已经离正解很近了。虽然我一题也没有写出来，不过 T1 的思路确实让我受益匪浅，失败是成功之母，下次再加油。T1 总结在上面。