ACdream 1063 - 밸 런 스 트 리
2. 분석: 이것 은 어떻게 하 는 것 입 니까? 바로 trie 나무 입 니 다. 우 리 는 trie 나 무 를 만 들 고 나 무 를 01 진법 으로 저장 한 다음 에 조회 할 때...
저 희 는 욕심 내 서 트 리 에서 쭉 걸 어 요.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Trie{
int ch[1000000][3];
int num;
inline void insert(int k){
int u = 0;
for(int i = 30; i >= 0; i --){
int s = ((1 << i) & k);
if(s){
if(!ch[u][1]){
num ++;
ch[u][1] = num;
}
u = ch[u][1];
}
else{
if(!ch[u][0]){
num ++;
ch[u][0] = num;
}
u = ch[u][0];
}
}
return;
}
inline int qmin(int k){
int u = 0;
int ret = 0;
for(int i = 30; i >= 0; i --){
int s = ((1 << i) & k);
if(s) {
if(ch[u][1]){
u = ch[u][1];
ret += (1 << i);
}
else{
u = ch[u][0];
}
}
else{
if(ch[u][0]){
u = ch[u][0];
}
else{
u = ch[u][1];
ret += (1 << i);
}
}
}
return ret;
}
inline int qmax(int k){
int u = 0;
int ret = 0;
for(int i = 30; i >= 0; i --){
int s = ((1 << i) & k);
if(s) {
if(ch[u][0]){
u = ch[u][0];
}
else{
u = ch[u][1];
ret += (1 << i);
}
}
else{
if(ch[u][1]){
u = ch[u][1];
ret += (1 << i);
}
else{
u = ch[u][0];
}
}
}
return ret;
}
} wt;
int main(){
int T;
scanf("%d", &T);
while(T --){
memset(wt.ch, 0, sizeof(wt.ch));
wt.num = 0;
int n;
scanf("%d", &n);
char str[10];
int k;
for(int i = 1; i <= n; i ++){
scanf("%s", str);
scanf("%d", &k);
if(str[2] == 's'){
wt.insert(k);
}
else if(str[2] == 'i'){
int ans = wt.qmin(k);
printf("%d
", ans^k);
}
else {
int ans = wt.qmax(k);
printf("%d
", ans^k);;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ACdream 1063 - 밸 런 스 트 리1. 제목 의 대의: 데이터 구 조 를 설계 하고 하나의 수 를 삽입 하 는 것 을 지원 하 며 이 구조 에서 구조 중의 어느 수 와 주어진 수의 차이 나 값 이 가장 작은 지 조회 할 수 있 습 니 다. 2. 분석...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.