【CSU-1323】解题报告（字典树）

原始题目

1323: ZZY and his little friends

  • Time Limit: 5 Sec
  • Memory Limit: 256 Mb
  • Submitted: 708
  • Solved: 258

Description

zzy养了一只小怪兽和N只凹凸曼，单挑的话每只凹凸曼都不是小怪兽的对手， 所以必须由两只凹凸曼合作来和小怪兽战斗。凹凸曼A和凹凸曼B合作的战斗力为他们战斗力的异或值。 现在由zzy从N只凹凸曼中选出两只来和小怪兽战斗。

请问zzy能否选出两只凹凸曼使他们能够战胜小怪兽(他们的战斗力比小怪兽大)。

Input

输入有多个例子，直到文件结束。 每个例子的第一行含两个数N和M，表示有 $ N ( 2 N 10^5 )\(只凹凸曼，小怪兽的战斗力为\) M (0 < M 10^9 )$。接着有一行N个数，每个数 $ A_i ( 0 < A_i < M )$表示每只凹凸曼的战斗力。

Output

对于每个例子输出一行，如果能选出两只凹凸曼使他们战胜小怪兽输出"YES", 否则输出"NO"(不含引号)

Sample Input

2 5
1 1
2 6
5 2

Sample Output

NO
YES

Author

CSU_CX

Source

CSU Monthly 2013 Oct.

题目大意

如题

解题思路

01字典树，将数字转换为32位的01数字串（高位在前）储存到树中。然后扫一遍求异最大值，与题目给定的\(M\)比较。

接替代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <iomanip>
#include <stack>
#define rep(i,a,n) for(int i=a ; i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define fi first
#define se second
#define cl(x,a) memset(x,a,sizeof(x)) 
#define all(x) x.begin(),x.end()
#define insert(x) x,x.begin()
#define debug printf("======================\n");
#define mp make_pair
#define np next_permutation
#define pb push_back
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int maxn=1e5+5;
const int maxm=1e5+5;
const int maxl=2;
const int K=32;

typedef long long ll;
typedef struct Trie{
	int v;
	Trie* next[maxl];
}Trie;

Trie *root;

void iniTrie(){
	root=(Trie*) malloc(sizeof(Trie));
	rep(i,0,maxl) root->next[i]=NULL;
	root->v=-1; 
}

bool creTrie(int a){
	//预处理整数为01数组 
	int temp[35];
	int id=K-1;
	while(a){
		temp[id--]=(a&1);
		a>>=1;
	}
	rep(i,0,id+1) temp[i]=0;
	
	int l=K;
	Trie *p=root,*q;
	rep(i,0,l){
		int id=temp[i];
		if(p->next[id]!=NULL){
			p=p->next[id];
		} 
		else {
			q=(Trie*) malloc(sizeof(Trie));
			q->v=1;  //新建节点染色
			for(int j=0;j<maxl;j++) q->next[j]=NULL;
			p->next[id]=q;
			p=p->next[id]; 
		}
		
	} 
	 
}

int findTrie(int a){
	int aa=a;
	int temp[35];
	int id=K-1;
	while(a){
		temp[id--]=(a&1);
		a>>=1;
	}
	rep(i,0,id+1) temp[i]=0;  //前面位置补0
	int aans=0;
	Trie *p=root;
	int l=K;
	for(int i=0;i<l;i++){
		int index= !temp[i];
		if(p->next[index] !=NULL ){
			aans=(aans<<1)+index;
			p=p->next[index];
		}
		else {
			aans=(aans<<1)+temp[i];
			p=p->next[temp[i]];
		}
	} 
	return aans^aa;
	
}


void delTrie(Trie *p){
	int i;
	for(int i=0;i<maxl;i++){
		if(p->next[i]!= NULL)	delTrie(p->next[i]);
	}
	free(p);
	p=NULL;
	return ;
}

int a[maxn],n,m;


int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		iniTrie();
		rep(i,0,n){
			cin>>a[i];
			creTrie(a[i]);
		}
		int fans=0;
		rep(i,0,n){
			fans=max(fans,findTrie(a[i]));
		}
		if(fans>m) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
	} 
}

收获与反思

熟悉求异或最大值01字典树的操作。