JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归

简要题意

对于一个数列 $num$，一个函数 $f$ 定义如下：
$$
f(num) = \max{(a_1 \oplus a_2 \oplus \dots a_i) + (a_{i+1} \oplus a_{i+2} \oplus\dots a_n) | i \in [0, n] }
$$
现在给你一个数列，依次求出其所有前缀的 $f$ 的值。

策略分析

首先我们需要一些前置知识，我们在求一个数列的子段异或和的时候，可以像其普通加法求和一样处理出前缀和并 $O(1)$ 求解。那么对于异或前缀和数组 $a$ 来讲，区间 $[l,r]$ 的异或和就等于 $a_{l-1} \oplus a_r$。

知道了这个性质以后，我们就可以做出本题 50 分的做法，即对于每个位置 $i$ 都去暴力枚举 $[1,i]$ 或 $[0,i]$ 区间（枚举这两个区间得到的答案是等价的）的最大答案。假设我们枚举到了位置 $j$，那么我们要求的就是答案 $ans$ 就等于 $max(ans,a_j+(a_j \oplus a_i))$。也就是说，想让答案尽可能大，就要让 $a_j+(a_j \oplus a_i)$ 尽可能大。于是我们自然而然地想到拆位来考虑。对于第 $k$ 位（下标从 $0$ 开始），这一位能够让整个数增加当且仅当这一位为 $0$ 且能够被更改为 $1$。也就是说如果第 $k$ 位为 $0$，那么它变成 $1$ 就可以对整个数造成 $2^k$ 的贡献。那么对于一个形如 $x + (x \oplus y)$ 的式子来说，我们设 $x$ 和 $y$ 都只有一位（高位情况不过是拆开考虑），那么当 $y=1$ 时，无论 $x$ 为何值，最终得到的结果都是 $1$，不会对结果产生任何影响。但当 $y=0$ 时，我们就要想办法让它变成 $1$ 从而使得答案增加。那么我们的目的就变成了，找到一个 $a_j$ 能够使其跟当前的 $a_i$ 运算的结果尽可能的大。

那么我们就要考虑能不能往这一位填 $1$，这要求我们去判断在前缀数组的第 $i$ 位之前有没有一个数可以和这个数运算使得我们期望的 $0$ 位变成 $1$ 且不去影响已经填好的，我们知道，只要我们把高位的一个 $0$ 变成 $1$，那么低位的甭管怎么变都不可能比现在大，那么我们直接贪心地从高位往低位讨论就好了。问题就在于怎么去让高位已经填好的不变。这里我们定义一种二进制下的集合关系，即 $x \subseteq y := x & y$，也就是说 $y$ 中为 $1$ 的位置在 $x$ 中也必须为 $1$。这样很抽象不好理解，我们举个例子。

1
2
3
a = 111000101010
b = 110000101010
c = 100000101010

上面的三个二进制数中，$b \subseteq a, c \subseteq b$。

定义了这个以后，我们定义一个数组 $f$，其中 $f_i=j$ 表示包含 $i$ 的数出现的位置的最小下标为 $j$，也就是存在一个数包含 $i$ 且这个数在 $a_i$ 里（当然也有可能不存在）最早出现的那个下标为 $j$。如果这个下标不存在那么显然值就是无穷大。我们在处理异或前缀和的时候就要初始化这个数组，初始化的过程非常显然但不便于用语言描述所以直接给出：

1
f[a[i]] = min(f[a[i]], i);

接下来我们要预处理这个数组，处理的时候从大的数向小的处理，这样可以一遍就找到我们想要的最小位置。因为本题数据范围是 $10^6$，所以我们大概从 $2^{21}-1$ 开始枚举即可，每次判断一下，如果 $f_i < \infty $ 那么我们就可以用 $f_i$ 去更新 $i$ 的子集（这里的子集和前面的包含关系定义是一样的）内的所有元素，更新的方法就是逐位枚举，如果是 $1$ 变成 $0$ 就是它的子集内的元素，那么更新就好了，但是更新完了要记得把改成 $0$ 的这一位再变回来更新下一位，实现过程如下：

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]);
            }
        }			
    }
}

注：这里的 $p_i$ 即表示 $2^i$ 次方的值，这个值在我们这道题中用其另一性质，即其二进制表示下第 $i$ 位为 $1$，其余均为 $0$，用一个数和 $p_i$ 做与运算可以判断这个数第 $i$ 位为 $1$ 还是 $0$。

预处理结束以后，我们就可以开始做了，逐个枚举前缀和，对于当前枚举到的 $a_i$，我们用一个 $s$ 来代表前面一半异或前缀和的值，那么我们仍然是从高位往低位枚举（基于贪心思想，高位为 $1$ 的贡献高于低位为 $1$ 的贡献。如果当前这一位是 $1$，那么我们就不用管它了，因为它不会再产生贡献。如果这一位为 $0$，那么我们就看能不能找到一个小于 $i$ 的位置上的元素使得其是 $s$ 这一位变成 $1$ 后的数的子集，只有这样才能保证操作完后以前操作的位上的值不会被改变，如果找到了就把 $s$ 这位变成 $1$，相反的，如果没找到就变回 $0$，再去枚举下一位。枚举完后按照 $a_j+(a_j \oplus a_i)$ 这个式子的形式算一下输出就好了，这个式子在这里变成了 $s + (s \oplus a_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();
}

说些什么吧！

twikoo