Google APAC 2017 Problem B. Robot Rock Band(位运算)

题目链接

题意:四组数字,每组都是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;
}

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 位运算