01字典树+1-1

liyuan2023 · 2025-06-01 14:45:22 · 算法·理论

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

struct Node {
    int son[2], cnt;
} tr[maxn*20];
int idx = 1;

void ins(int &num) {
    int u = 1;
    for (int i = 0; i <= 5; i++) {
        int x = (num >> i) & 1;
        if (!tr[u].son[x])
            tr[u].son[x] = ++idx;
        u = tr[u].son[x];
        tr[u].cnt++;
    }
}

void dfs(int u, int num, int d) {
    if (!u)
        return;
    if (d > 5) {
        cout<<"数字"<<num<<"出现了"<<tr[u].cnt<<"次\n";
        return; 
    }
    for (int i = 0; i < 2; i++)
        dfs(tr[u].son[i], num + i * (1<<d), d+1);
}
// 全局 +1：交换左右儿子，进左儿子 
void plus_one() {
    int u = 1;
    for (int i = 0; i <= 5; i++) {
        swap(tr[u].son[0], tr[u].son[1]);
        u = tr[u].son[0];
        if (!u) return;
    }
}

// 全局 -1
void minus_one() {
    int u = 1;
    for (int i = 0; i <= 5; i++) {
        swap(tr[u].son[0], tr[u].son[1]);
        u = tr[u].son[1];
        if (!u) return;
    }
} 

int op, x;

int main() {
    while (cin >> op) {
        if (op == 1) {
            cin >> x;
            ins(x);
        }
        else if (op == 2) {
            plus_one();
        }
        else if (op == 3) {
            dfs(1, 0, 0);
        }
        else { // op == 4
            minus_one();
        }
    }
    return 0;
}