怎样做摄影网站,西安做百度推广网站 怎样备案,开发一个进销存app需要多少钱,学校网站建设发展规划XOR Construction—CF1895D 参考文章
翻译
题目要求构造一个长度为 n n n 的数组 b b b#xff0c;满足以下条件#xff1a;
数组 b b b 中包含从 0 0 0 到 n − 1 n-1 n−1 的每个整数#xff0c;且每个整数仅出现一次#xff1b;对于 i i i 从 1 1 1 到 n − …XOR Construction—CF1895D 参考文章
翻译
题目要求构造一个长度为 n n n 的数组 b b b满足以下条件
数组 b b b 中包含从 0 0 0 到 n − 1 n-1 n−1 的每个整数且每个整数仅出现一次对于 i i i 从 1 1 1 到 n − 1 n-1 n−1 b i ⊕ b i 1 a i b_i \oplus b_{i1} a_i bi⊕bi1ai其中 ⊕ \oplus ⊕ 表示按位异或运算符。
输入
第一行包含一个整数 n n n 2 ≤ n ≤ 2 ⋅ 1 0 5 2 \le n \le 2 \cdot 10^5 2≤n≤2⋅105。
第二行包含 n − 1 n-1 n−1 个整数 a 1 , a 2 , … , a n − 1 a_1, a_2, \dots, a_{n-1} a1,a2,…,an−1 0 ≤ a i ≤ 2 n 0 \le a_i \le 2n 0≤ai≤2n。
输入的附加限制条件始终可以从给定序列 a a a 构造出至少一个有效的数组 b b b。
输出
输出 n n n 个整数 b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1,b2,…,bn。如果存在多个满足条件的数组可以输出其中任意一个。
思路
由 b i ⊕ b i 1 a i b_i \oplus b_{i1}a_i bi⊕bi1ai 得 b 1 ⊕ b 2 a 1 b_1 \oplus b_2a_1 b1⊕b2a1 b 2 ⊕ b 3 a 2 b_2 \oplus b_3a_2 b2⊕b3a2 b 3 ⊕ b 4 a 3 b_3 \oplus b_4a_3 b3⊕b4a3异或累加得 b 1 ⊕ b i a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a i − 1 b_1 \oplus b_ia_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_{i-1} b1⊕bia1⊕a2⊕a3⊕...⊕ai−1即 b i b 1 ⊕ a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a i − 1 b_ib_1 \oplus a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_{i-1} bib1⊕a1⊕a2⊕a3⊕...⊕ai−1。
因为题目保证有解所以 b 1 b_1 b1 存在某个取值使得 b b b 中元素各不相同即 a a a 的所有前缀异或和各不相同且不存在 0 0 0。那么我们很容易得到 对于 b 1 b_1 b1 的任意取值 b b b 中元素都互不相同。
因为 every integer from 0 0 0 to n − 1 n-1 n−1 appears in b b b exactly once而我们已经知道了 b b b 中元素互不相同现在的任务就是保证 b b b 中元素最小化。为了达到这一目的我们只能修改 b 1 b_1 b1 的大小。
让 b 1 b_1 b1 的二进制第 k k k 位最优使得 b 2 , . . . , b n b_2, ..., b_n b2,...,bn 中二进制第 k k k 位上的“1”的数量最小进而使得 b b b 数组整体最小。这里使用了贪心的思路来实现局部最优得到整体最优二进制每一位最优得到二级制所有位最优。 C o d e Code Code
#include bits/stdc.h
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII pairint, int;
using i128 __int128;
const int N 2e5 10;int n;void solve(int Case) {cin n;vector int a(n 1, 0);for (int i 1; i n - 1; i ) {cin a[i];a[i] ^ a[i - 1];}int b1 0;for (int i 0; i 30; i ) {int num1 0;int num0 0;for (int j 1; j n - 1; j ) {if (a[j] i 1) {num1 ;} else {num0 ;}}if (num1 num0) {b1 1 i;}}cout b1 ;for (int i 2; i n; i ) {cout (a[i - 1] ^ b1) ;}cout \n;
}signed main() {cin.tie(0)-ios::sync_with_stdio(false);int T 1;
// cin T; cin.get();int Case 0;while ( Case T) solve(Case);return 0;
}
