集合询问（哈希）

题意

题目链接：https://www.acwing.com/problem/content/4607/

数据范围

\(1 \leq t \leq 10^5\)
\(0 \leq x < 10^{18}\)
\(1 \leq |s| \leq 18\)

思路

该题的关键在于如何快速的计算有多少元素能够匹配\(s\)。

我们可以将\(s\)看作某种模式，用哈希表去维护不同模式有多少元素即可。

具体来说，对于一个整数\(x\)，我们从最低位（第\(1\)位）开始一直到最高位（第\(18\)位）。对于每一位，如果为偶数，则模式的对应位为\(0\)，反之为\(1\)。

因此，对于一个新的\(x\)，我们将其转化为对应的模型，哈希表相应位置加\(1\)。如果是去掉\(x\)，则哈希表相应位置减\(1\)。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <unordered_map>

using namespace std;

string s;
unordered_map<string, int> mp;

string trans(string s)
{
    int n = s.size();
    string t = "";
    for(int i = n - 1; i >= 0; i --) {
        int k = s[i] - '0';
        if(k % 2) t += '1';
        else t += '0';
    }
    for(int i = n; i <= 18; i ++) {
        t += '0';
    }
    return t;
}

int main()
{
    int T;
    cin >> T;
    while(T --) {
        char op;
        cin >> op >> s;
        if(op == '+') {
            mp[trans(s)] ++;
        }
        else if(op == '-') {
            mp[trans(s)] --;
        }
        else {
            string t = trans(s);
            cout << mp[t] << '\n';
        }
    }
    return 0;
}