Google APAC 2017 Problem B. Robot Rock Band（位运算）

September 05, 2016

题目链接

题意：四组数字，每组都是 n 个数，要求从每组数中选一个数字，四个数的异或结果等于 k。

一开始在想拆位，后来发现没那么麻烦。

n < 1000，四层循环肯定超时，所以把四组数字分成两次计算异或。

异或性质：x^y^y = x

假设前两组数的异或结果为 x，后两组数字中的异或结果为 y，那么题目就是要求 x^y=k. 即 y=k^x.

所以把所有 x^k 计算出来，用 map 对应 x^k 的个数，然后再遍历后两组出直接取出 map[y]，看存在几次，全部加在一起。（栈区定义 map 默认初始化为 0，因此若不存在加的就是 0）。

注意 ans 要开 long long。

#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
	freopen("../Downloads/B-large-practice.in", "r", stdin);
	freopen("ans.out", "w", stdout);
	int t; cin >> t;
	for(int cas = 1; cas <= t; cas++){
		int n, k;
		scanf("%d %d", &n, &k);
		int a[4005];
		for(int i = 0; i < 4*n; i++){
			scanf("%d", &a[i]);
		}
		map<int, int> m;
		for(int i = 0; i < n; i++){
			for(int j = n; j < 2*n; j++){
				int cal = a[i]^a[j]^k;
				int tmp = m[cal];
				m[cal] = tmp+1;
			}
		}
		//cout << m[0]<< endl;
		long long ans = 0;
		for(int i = 2*n; i < 3*n; i++){
			for(int j = 3*n; j < 4*n; j++){
				ans += m[a[i]^a[j]];
			//	cout << ans << endl;
			}
		}
		printf("Case #%d: %lld\n", cas, ans);
	}
	return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]