本文主要是介绍[ARC145E] Adjacent XOR 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
推荐在 cnblogs 上阅读。
[ARC145E] Adjacent XOR 题解
这道题真的是道神仙题,是那种考场想不出来、补题也补得十分艰难的题。可能我还是太菜了。
看了 APJ 大神的题解,琢磨很久才懂。为了帮助像我一样的同学,特地写一篇题解。
这是 2 月的第一篇题解、更是我的第一道黑题题解,谨纪念。
参考文献
- [1] APJifengc,「解题报告」[ARC145E] Adjacent XOR
题意
给你 n n n 个整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an,再给你 n n n 个整数 b 1 , b 2 , … , b n b_1,b_2,\dots,b_n b1,b2,…,bn。通过执行以下操作,问你能不能操作 70000 70000 70000 次以内使得 a a a 与 b b b 相同。
- 操作:选择整数 k ∈ [ 1 , n ] k\in[1,n] k∈[1,n],进行 a i ← a i − 1 ⊕ a i a_i\leftarrow a_{i-1}\oplus a_i ai←ai−1⊕ai, i ∈ [ 2 , k ] i\in[2,k] i∈[2,k] 的赋值操作。
数据范围: 2 ≤ n ≤ 1000 2\le n\le 1000 2≤n≤1000, 0 ≤ a i , b i < 2 60 0\le a_i,b_i \lt 2^{60} 0≤ai,bi<260。
Solution
转化目标
题意清晰,就是告诉你要构造方案。
由于每一次操作都是 a i ← a i − 1 ⊕ a i a_i\leftarrow a_{i-1}\oplus a_i ai←ai−1⊕ai,这个及其难下手。不妨反过来,从 b b b 入手。
在此之前,先琢磨透这个在 a a a 上做手脚的操作,到底是个啥?
其实一次操作,钦定 k k k 以后,就是去把每一个在 [ 2 , k ] [2,k] [2,k] 的 a i a_i ai 都赋值为原 a a a 数组下标从 1 ∼ i − 1 1\sim i-1 1∼i−1 的异或和。
而我们对 a i a_i ai 做手脚,是因为我们期望得到 b i b_i bi。这个对 a a a 数组的操作,每次都依靠前缀。
形式化地,这样:
b 1 = a 1 ′ = a 1 b 2 = a 2 ′ = a 1 ⊕ a 2 b 3 = a 3 ′ = a 1 ⊕ a 2 ⊕ a 3 … b i = a i ′ = ⊕ j = 1 i a j b_1=a'_1=a_1\\b_2=a'_2=a_1\oplus a_2\\b_3=a'_3=a_1\oplus a_2\oplus a_3\\\dots\\b_i=a'_i=\oplus_{j=1}^i a_j b1=a1′=a1b2=a2′=a1⊕a2b3=a3′=a1⊕a2⊕a3…bi=ai′=⊕j=1iaj
现在考虑从 b b b 入手,从而推出 a a a。那么题意变为:
选择 k ∈ [ 1 , n ] k\in[1,n] k∈[1,n],进行 b i = ⊕ j = 1 i b j b_i=\oplus_{j=1}^i b_j bi=⊕j=1ibj, i ∈ [ 1 , k ] i\in[1,k] i∈[1,k] 的赋值操作。
为什么这样得到的 b i b_i bi 会等于 a i a_i ai 呢?展开一下就明白了:
b 1 ′ = b 1 b 2 ′ = b 1 ′ ⊕ b 2 b 3 ′ = b 1 ′ ⊕ b 2 ′ ⊕ b 3 b'_1=b_1\\b'_2=b'_1\oplus b_2\\b'_3=b'_1\oplus b'_2\oplus b_3 b1′=b1b2′=b1′⊕b2b3′=b1′⊕b2′⊕b3
如果一项一项带入,就会发现 b i ′ = b i − 1 ⊕ b i b'_i=b_{i-1}\oplus b_i bi′=bi−1⊕bi。又把 b i b_i bi 用 a i a_i ai 表示,可以得到 b i ′ = ( a 1 ⊕ ⋯ ⊕ a i − 1 ) ⊕ ( a 1 ⊕ ⋯ ⊕ a i ) = a i b'_i=(a_1\oplus\dots\oplus a_{i-1})\oplus (a_1\oplus \dots \oplus a_i)=a_i bi′=(a1⊕⋯⊕ai−1)⊕(a1⊕⋯⊕ai)=ai。
至此,题意与解题目标发生了转化、也更加清晰。
能否构造
观察一手数据范围,可以跑 n log b n\log b nlogb。考虑对于每个 i i i,就用 O ( log b ) O(\log b) O(logb) 构造出一个 a i a_i ai。这里为了防止前缀和影响已更新好的数,我们选择倒着构造。
先判断能否构造,不难想到,可以构造的充要条件是:每一个 a i a_i ai 都可以由 b [ 1 , i − 1 ] b_{[1,i-1]} b[1,i−1] 中的若干数与 b i b_i bi 异或得到。
构造开始
这个 b b b 数组,不是个善茬,想不到怎么很好处理。思考一下 b b b 数组需要做的操作,都是它的线性基可以处理的(其实看到异或问题,多多少少要想到一点线性基)。
我们把基底按先后加入顺序标号,来表示 b b b 的每一个数。此刻来考虑这个新数组 c c c。
我们想从 a n ∼ a 1 a_n\sim a_1 an∼a1 进行构造,如果我们此时构造 a i a_i ai,那么我们不能动 a k a_k ak, k ∈ [ i + 1 , n ] k\in[i+1,n] k∈[i+1,n];否则就打乱了。
所以,当我们改变到第 i i i 位的时候,只能对 k = i k=i k=i 进行操作: b i ← ⊕ j = 1 i b j b_i\leftarrow \oplus_{j=1}^ib_j bi←⊕j=1ibj。实际上,就是构造异或和等于 a i a_i ai。
我们按加入的先后顺序标号,所以当第 i i i 位最早在 p o s i pos_i posi 出现时,在 [ 1 , p o s i − 1 ] [1,pos_i-1] [1,posi−1] 中 i i i 这一位都为零。这个很显然。
那得知这个有什么用呢?我们可以通过这个将前缀异或和进行某一位的翻转。既然 p o s i pos_i posi 是第一次出现 i i i,那如果我对 k = p o s i + 1 k=pos_i+1 k=posi+1 进行操作,只有 b p o s i + 1 b_{pos_i+1} bposi+1 的异或和多了 i i i 这一位,总异或和这一位也就可以翻转了。
也是从大到小考虑, p o s i pos_i posi 递减,不会影响之前的数。
构造总结
那现在构造方法就很明了了:
- 从大到小枚举 i i i,计算当前异或和。
- 当异或和与 a i a_i ai (重标号后的)某一位不一样,就对那一位进行翻转操作。
- 最后对 k = m k=m k=m 进行操作,即可得出 a m a_m am。
- 重复 n n n 遍,最后把操作序列翻转,就是从 a a a 到 b b b 的操作了。
代码
code
#include <bits/stdc++.h>
using namespace std;#define int long longconst int MAXN = 1e3 + 5;int n;
int a[MAXN], b[MAXN], c[MAXN];
int pos[64];
vector<int> ans;struct XXJ {int d[64]; // 基底int id[64], tot;void Clear() {memset(d, 0, sizeof(d));memset(id, 0, sizeof(id));tot = 0;}bool Count(int x) {for (int i = 59; ~i; i--)if (x >> i & 1) {if (d[i] == 0)return 0;x ^= d[i];}return 1;}int Insert(int x) {int res = 0;for (int i = 60; ~i; i--)if (x >> i & 1) {if (d[i] == 0) {d[i] = x;id[i] = tot++;return res | (1ll << id[i]);}res |= (1ll << id[i]);x ^= d[i];}return res;}
} X;void work(int x) {ans.push_back(x);for (int i = 1; i <= x; i++) {b[i] ^= b[i - 1];c[i] ^= c[i - 1];}
}signed main() {scanf("%lld", &n);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);for (int i = 1; i <= n; i++) {if (X.Count(a[i] ^ b[i]) == 0)return puts("No"), 0;X.Insert(b[i]);}for (int i = n; i; i--) {X.Clear();for (int j = 1; j <= i; j++) {bool flg = X.Count(b[j]);c[j] = X.Insert(b[j]);if (flg == 0)pos[__lg(c[j])] = j;}int tmp = X.Insert(a[i]);for (int j = X.tot; ~j; j--) {int sum = 0;for (int k = 1; k <= i; k++) sum ^= c[k];if ((sum >> j & 1) != (tmp >> j & 1))work(pos[j] + 1);}work(i);}reverse(ans.begin(), ans.end());printf("Yes\n%lld\n", (int)ans.size());for (int i : ans) printf("%lld ", i);return 0;
}
这篇关于[ARC145E] Adjacent XOR 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!