ARC124B XOR Matching 2

tony102

2021 年 11 月 12 日

1927 次浏览

暂无评论

886字数

题解

[Link](https://atcoder.jp/contests/arc124/tasks/arc124_b)

## Sol

太 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

1. 注意个数这种小细节
2. 仔细观察题目条件，不要一上来就想套路拆位

## Code

```cpp
#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;
}
```

最后修改：2021 年 11 月 12 日