显示原始代码
#include <iostream>
using namespace std;
#define LEN 32
int num1[LEN] = { 0 };
class Tirenode {
public:
Tirenode *child0, *child1;
unsigned int num;
Tirenode() {
child0 = NULL;
child1 = NULL;
num = 0;
return;
}
};
class Tiretree {
public:
Tirenode *head;
Tiretree() { head = new Tirenode(); }
void insert(unsigned int e) {
Tirenode *p = head;
p->num++;
int i = 0;
while (e) {
char b = e & 0x01;
e = e >> 1;
if (b) {
if (p->child1 == NULL)
p->child1 = new Tirenode();
p = p->child1;
num1[i]++;
} else {
if (p->child0 == NULL)
p->child0 = new Tirenode();
p = p->child0;
}
p->num++;
i++;
}
}
};
int main() {
Tiretree *t = new Tiretree();
unsigned n;
cin >> n;
while (n--) {
char c;
cin >> c;
if (c == '1') {
Tirenode *p = t->head, *tmp;
int i = 0;
while (1) {
tmp = p->child0;
p->child0 = p->child1;
p->child1 = tmp;
if (p->child0 == NULL) {
if (p->child1 == NULL)
p->child1 = new Tirenode();
p->child1->num = p->num;
num1[i++] += p->child1->num;
break;
} else {
if (p->child1 == NULL && p->num > p->child0->num) {
p->child1 = new Tirenode();
}
if (p->child1)
p->child1->num = p->num - p->child0->num;
num1[i++] += p->child1->num - p->child0->num;
}
p = p->child0;
}
} else {
Tirenode *p = t->head, *tmp;
unsigned int element;
cin >> element;
t->insert(element);
}
unsigned int sum = 0;
for (int i = LEN - 1; i >= 0; i--) {
sum = sum << 1;
sum |= (num1[i] & 0x01);
}
cout << sum << endl;
}
return 0;
}