写的很丑的字典树。听王大神的话 需要改进。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std; struct nn
{
int zero;
int one; }node[]; int findd[]; int main()
{
int sb;
scanf("%d", &sb);
while (sb--)
{
int n, i, j, ii, t, tot;
scanf("%d", &n);
char s[]; int ff; for (i = ; i<; i++)
{
node[i].zero = -;
node[i].one = -;
} int jiedian = ;
for (i = ; i<n; i++)
{
scanf("%s", s);
if (strcmp("insert", s) == )
{
tot = ;
scanf("%d", &t);
while (t)
{
findd[tot] = t % ;
t = t / ;
tot++;
}
while ()
{
if (tot == ) break;
findd[tot] = ;
tot++;
}
int bianli = ;
for (ii = ; ii >= ; ii--)
{
if (findd[ii] == )
{
if (node[bianli].zero == -)
{
node[bianli].zero = jiedian;
jiedian++;
}
bianli = node[bianli].zero;
}
else if (findd[ii] == )
{
if (node[bianli].one == -)
{
node[bianli].one = jiedian;
jiedian++;
}
bianli = node[bianli].one;
}
}
}
else if (strcmp("qmin", s) == )
{
scanf("%d", &t);
tot = ;
while (t)
{
findd[tot] = t % ;
t = t / ;
tot++;
}
while ()
{
if (tot == ) break;
findd[tot] = ;
tot++;
}
int bianli = ;
int anss = ;
for (ii = ; ii >= ; ii--)
{
if (findd[ii] == )
{
if (node[bianli].one != -)
{
anss = anss + ;
bianli = node[bianli].one;
}
else if (node[bianli].zero != -)
{
anss = anss + ( << ii);
bianli = node[bianli].zero;
}
}
else if (findd[ii] == )
{
if (node[bianli].zero != -)
{
anss = anss + ;
bianli = node[bianli].zero;
}
else if (node[bianli].one != -)
{
anss = anss + ( << ii);
bianli = node[bianli].one;
}
}
}
printf("%d\n", anss);
}
else if (strcmp("qmax", s) == )
{
scanf("%d", &t);
tot = ;
while (t)
{
findd[tot] = t % ;
t = t / ;
tot++;
}
while ()
{
if (tot == ) break;
findd[tot] = ;
tot++;
}
int bianli = ;
int anss = ;
for (ii = ; ii >= ; ii--)
{
if (findd[ii] == )
{
if (node[bianli].zero != -)
{
anss = anss + ( << ii);
bianli = node[bianli].zero;
}
else if (node[bianli].one != -)
{
anss = anss + ;
bianli = node[bianli].one;
}
}
else if (findd[ii] == )
{
if (node[bianli].one != -)
{
anss = anss + ( << ii);
bianli = node[bianli].one;
}
else if (node[bianli].zero != -)
{
anss = anss + ;
bianli = node[bianli].zero;
}
}
}
printf("%d\n", anss);
}
}
}
return ;
}