JZOJ5952.
【NOIP2018模拟11.5A组】凯旋而归
简要题意
对于一个数列 ，一个函数 定义如下： 现在给你一个数列，依次求出其所有前缀的 的值。
策略分析
首先我们需要一些前置知识，我们在求一个数列的子段异或和的时候，可以像其普通加法求和一样处理出前缀和并
求解。那么对于异或前缀和数组
来讲，区间 的异或和就等于 。
知道了这个性质以后，我们就可以做出本题 50 分的做法，即对于每个位置
都去暴力枚举 或
区间（枚举这两个区间得到的答案是等价的）的最大答案。假设我们枚举到了位置
，那么我们要求的就是答案 就等于 。也就是说，想让答案尽可能大，就要让
尽可能大。于是我们自然而然地想到拆位来考虑。对于第 位（下标从
开始），这一位能够让整个数增加当且仅当这一位为 且能够被更改为 。也就是说如果第 位为 ，那么它变成 就可以对整个数造成 的贡献。那么对于一个形如 的式子来说，我们设 和
都只有一位（高位情况不过是拆开考虑），那么当 时，无论 为何值，最终得到的结果都是 ，不会对结果产生任何影响。但当 时，我们就要想办法让它变成
从而使得答案增加。那么我们的目的就变成了，找到一个 能够使其跟当前的 运算的结果尽可能的大。
那么我们就要考虑能不能往这一位填 ，这要求我们去判断在前缀数组的第
位之前有没有一个数可以和这个数运算使得我们期望的 位变成
且不去影响已经填好的，我们知道，只要我们把高位的一个 变成 ，那么低位的甭管怎么变都不可能比现在大，那么我们直接贪心地从高位往低位讨论就好了。问题就在于怎么去让高位已经填好的不变。这里我们定义一种二进制下的集合关系，即
，也就是说 中为 的位置在 中也必须为 。这样很抽象不好理解，我们举个例子。
1
2
3
| a = 111000101010
b = 110000101010
c = 100000101010
|
上面的三个二进制数中，。
定义了这个以后，我们定义一个数组 ，其中 表示包含 的数出现的位置的最小下标为 ，也就是存在一个数包含 且这个数在
里（当然也有可能不存在）最早出现的那个下标为 。如果这个下标不存在那么显然值就是无穷大。我们在处理异或前缀和的时候就要初始化这个数组，初始化的过程非常显然但不便于用语言描述所以直接给出：
1
| f[a[i]] = min(f[a[i]], i);
|
接下来我们要预处理这个数组，处理的时候从大的数向小的处理，这样可以一遍就找到我们想要的最小位置。因为本题数据范围是
，所以我们大概从 开始枚举即可，每次判断一下，如果
那么我们就可以用
去更新
的子集（这里的子集和前面的包含关系定义是一样的）内的所有元素，更新的方法就是逐位枚举，如果是
变成
就是它的子集内的元素，那么更新就好了，但是更新完了要记得把改成
的这一位再变回来更新下一位，实现过程如下：
1
2
3
4
5
6
7
8
9
| for (int i = (1 << 20) - 1;i >= 0; --i) {
if(f[i] < INF) {
for (int j = 0; j < 20; ++j) {
if(i & p[j]) {
f[i ^ p[j]] = min(f[i ^ p[j]], f[i]);
}
}
}
}
|
注：这里的 即表示
次方的值，这个值在我们这道题中用其另一性质，即其二进制表示下第 位为 ，其余均为 ，用一个数和 做与运算可以判断这个数第 位为 还是 。
预处理结束以后，我们就可以开始做了，逐个枚举前缀和，对于当前枚举到的
，我们用一个
来代表前面一半异或前缀和的值，那么我们仍然是从高位往低位枚举（基于贪心思想，高位为
的贡献高于低位为 的贡献。如果当前这一位是 ，那么我们就不用管它了，因为它不会再产生贡献。如果这一位为
，那么我们就看能不能找到一个小于
的位置上的元素使得其是 这一位变成
后的数的子集，只有这样才能保证操作完后以前操作的位上的值不会被改变，如果找到了就把
这位变成 ，相反的，如果没找到就变回 ，再去枚举下一位。枚举完后按照
这个式子的形式算一下输出就好了，这个式子在这里变成了 ，实现过程如下：
1
2
3
4
5
6
7
8
9
| for (int i = 1; i <= n; ++i) {
int s = 0;
for (int j = 19; j >= 0; --j) {
if (!(a[i] & p[j]) && f[s | p[j]] <= i) {
s |= p[j];
}
}
cout << s + (a[i] ^ s) << '\n';
}
|
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
namespace SHAWN {
const int N=5e5 + 7, M = 2e6 + 7, INF = 1e9;
int a[N], f[M], p[32];
int n;
signed work()
{
cin >> n;
memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; ++i) {
cin >> a[i]; a[i] ^= a[i - 1];
f[a[i]] = min(f[a[i]], i);
}
p[0] = 1;
for (int i = 1; i < 20; ++i) { p[i] = p[i - 1] << 1; }
for (int i = (1 << 20) - 1;i >= 0; --i) {
if(f[i] < INF) {
for (int j = 0; j < 20; ++j) {
if(i & p[j]) {
f[i ^ p[j]] = min(f[i ^ p[j]], f[i]);
}
}
}
}
for (int i = 1; i <= n; ++i) {
int s = 0;
for (int j = 19; j >= 0; --j) {
if (!(a[i] & p[j]) && f[s | p[j]] <= i) {
s |= p[j];
}
}
cout << s + (a[i] ^ s) << '\n';
}
return 0;
}
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
return SHAWN :: work();
}
|
