Tony102's Blog - 二进制
type: channel
link: https://tony102.com/index.php/tag/%E4%BA%8C%E8%BF%9B%E5%88%B6/
items: ARC124B XOR Matching 2
items: ARC127D Sum of Min of Xor

ARC124B XOR Matching 2
type: item
date: 2021-11-12T19:25:00+08:00
description: LinkSol太 naive 了。讲真，每次看见位运算和计数都头大。先考虑拆位，发现有一个无法解决的问题：因为 b 可以随意排列，所以没有办法解决顺序的问题。突破点：$\forall i \in [1,n], a_i \oplus b_i = x$ 。相当于我们每次检查 $x$ 合不合法只需要看 $a$ 任意一个元素和 $b$ 中每一个元素异或是不是 $x$ 就行了。$x$ 也根本不需要拆位算，只需要每次枚举每一个 $b_i$ 。令 $x = a_1 \oplus b_i$ ，因为若 $a_i \oplus b_i = x$，则 $a_i \oplus x = b_i$ （太显然了）。所以只需要每次检查每一个 $a_i \oplus x$ 是不是在 $b$ 中出现过就行了。出现了一个巨大的问题，就是假如 $a_i \oplus x$ 确实在 $b$ 中出现过，需要每出现一次就删掉一个，否则有可能一个值多次出现然而 $b$ 中并没有这么多导致不合法。不这样做过不去第一个点......Idea注意个数这种小细节仔细观察题目条件，不要一上来就想套路拆位Code#include <bits/stdc++.h> using namespace std; typedef vector < int > vec; const int SIZE = 2e3 + 5; int n; int a[SIZE], b[SIZE]; unordered_map < int, bool > vis; vec ans; multiset < int > tmp; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int main() { n = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); for (int i = 1; i <= n; ++ i) b[i] = read(); for (int i = 1; i <= n; ++ i) { int ok = 1, x = a[1] ^ b[i]; if (vis[x]) continue; vis[x] = 1; tmp.clear(); for (int j = 1; j <= n; ++ j) if (i != j) tmp.insert(b[j]); for (int j = 2; j <= n; ++ j) { int c = x ^ a[j]; auto it = tmp.find(c); if (it == tmp.end()) { ok = 0; break; } else tmp.erase(it); } if (ok) ans.emplace_back(x); } sort(ans.begin(), ans.end()); ans.resize(unique(ans.begin(), ans.end()) - ans.begin()); printf("%d\n", (int) ans.size()); for (int it: ans) printf("%d\n", it); return 0; }

ARC127D Sum of Min of Xor
type: item
date: 2021-10-22T09:09:00+08:00
description: Link你大可不必相信 CF 都是好题，但是 AtCoder 一定不会让你失望。Sol先来考虑一个简单的问题：求 $\sum_{i<j} A_i \oplus A_j$ 。考虑拆位，首先有贡献的肯定是不同位 $0$ 和 $1$ 配，那么统计每一位上的 $0,1$ 数量，乘起来然后乘以 $(1 << i)$ （当前在 $i$ 位）。现在要求的是 $\sum_{1 \leq i < j \leq n} \min{(A_i \oplus A_j, B_i \oplus B_j)}$ 。首先两个数在二进制下取 $\min$，就是 $X=(000001\dots)_2 > Y = (0000001\dots)$ 这样的形式：前面一段前缀都相同，然后有一位的 $0/1$ 不同开始就有大小差别。现在关键的就是要比较第一个不同的这一位。非常 NB 的比较方法：设 $D_i = A_i \oplus A_j \oplus B_i \oplus B_j$，那么 $C_i$ 哪一位上是 $1$，哪一位就是不同的。对 $D_i$ 再移一下项，可以得到更加有利于接下来步骤的形式：$D_i = A_i \oplus B_i \oplus A_j \oplus B_j$ ，这一样每个下标都是一样的位置，令 $C_i = A_i \oplus B_i$。我们通过分治来计算每次分治区间内的数从哪里开始 $C_i$ 有 $0/1$（说明该区间内的数有大小差异）。具体地，当前分治的区间是 $[L,R]$，我们从左找到第一个 $C_i$ 为 $1$ 的位置 $i$，从右找到第一个 $C_i$ 为 $0$ 的位置 $j$，也就是 $[L,i)$ 为 $0$，$[i,j)$ 为 $1$。把区间中的每一个数在这一位的贡献独立计算。分类讨论即可，例如：$A_i, B_i, A_j$ 在当前枚举的位置上是 $0$, $B_j$ 是 $1$，那么贡献就应该是 $A_i \oplus A_j$Idea二进制挂钩请直接考虑拆位计算贡献，大小关系判断可以在位上异或判断，成对的贡献可以分治。Code#include <bits/stdc++.h> using namespace std; typedef long long LL; const int SIZE = 2.5e5 + 5; int n; LL ans; int a[SIZE], b[SIZE], c[SIZE], w[2][2][2][2]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; void exchange(int i, int j) { std::swap(a[i], a[j]), std::swap(b[i], b[j]), std::swap(c[i], c[j]); } void merge(int l, int r, int bit) { if (l > r) return; if (bit == -1) { int v[2]; for (int i = 0; i < 18; ++ i) { v[0] = v[1] = 0; for (int j = l; j <= r; ++ j) ++ v[(a[j] >> i) & 1]; ans += 1ll * v[0] * v[1] * (1ll << i); } return; } int i = l, j = r; while (i < j) { while (i <= r && !(c[i] >> bit & 1)) ++ i; while (i < j && c[j] >> bit & 1) -- j; if (i < j) exchange(i, j); } for (int k = 0; k < 18; ++ k) { memset(w, 0, sizeof(w)); int …