求调题目
  • 板块学术版
  • 楼主LonginusMonkey
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/24 20:49
  • 上次更新2023/11/2 11:32:27
查看原帖
求调题目
326254
LonginusMonkey楼主2023/10/24 20:49

U109895 [HDU4825]Xor Sum

这道题目

样例都过了,但是不知道为什么wa了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int tempch[55];
int tot, root;
struct node{
	int ch[2];
	int cnt;
	void init() {
		ch[0] = ch[1] = 0;
		cnt = 0;
	}
}trie[5001000];

void insert() {
	int p = root;
	for(int i=0; i<=31; ++i) {
		if(!trie[p].ch[tempch[i]]) {
			trie[p].ch[tempch[i]] = ++tot;
		}
		p = trie[p].ch[tempch[i]];
		trie[p].cnt ++;
	}
}
int ask() {
	int ans = 0;
	int p = root;
	for(int i=0; i<=31; ++i) {
		if(trie[p].ch[!tempch[i]] == 0) {
			p = trie[p].ch[tempch[i]];
			if(tempch[i] == 1) {
				ans += (1<<(31-i));
			}
		} else {
			p = trie[p].ch[!tempch[i]];
			if(tempch[i] == 0) {
				ans += (1<<(31-i));
			}
		}
	}
	return ans;
}
signed main() {
	root = ++tot;
	int n, m; cin >> n >> m;
	for(int i=1; i<=n; ++i) {
		int temp; cin >> temp;
		for(int j=0; j<=31; ++j) {
			if(temp & (1ll<<(31ll-j))) {
				tempch[j] = 1;
			} else {
				tempch[j] = 0;
			}
		}
//		for(int j=0; j<=31; ++j) {
//			cout << tempch[j] << " ";
//		}
//		cout << endl;
		insert();
	}
	for(int i=1; i<=m; ++i) {
		int temp; cin >> temp;
		for(int j=0; j<=31; ++j) {
			if(temp & (1<<(31ll-j))) {
				tempch[j] = 1;
			} else {
				tempch[j] = 0;
			}
		}
//		for(int j=0; j<=31; ++j) {
//			cout << tempch[j] << " ";
//		}
//		cout << endl;
		cout << ask() << endl;
	}
	return 0;
}
2023/10/24 20:49
加载中...