集合询问
有一个整数集合,初始时集合为空。
现在,要对该集合进行 t 次操作,操作分为以下三种:
- + x ,将一个非负整数 $x$ 添加至集合中。注意,集合中可以存在多个相同的整数。
- - x,从集合中删除一个非负整数 $x$。可以保证执行此操作时,集合中至少存在一个 $x$。
- ? s,询问操作,给定一个由 $0$ 和 $1$ 组成的模板 $s$,请你计算并输出此时集合中有多少个元素可以与 $s$ 相匹配。
关于判断整数 $x$ 与模板 $s$ 是否匹配的具体方法如下:
- 首先,在进行匹配判断前,应保证 $x$ 与 $s$ 位数相同,如果两者位数不同,则位数更少的一方需补充前导 $0$ 至与位数更多的一方位数相同为止。
- 从最高位开始,对每一位进行逐个判断,如果 $s$ 的第 $i$ 位为 $0$,则 $x$ 的第 $i$ 位必须为偶数,如果 $s$ 的第 $i$ 位为 $1$,则 $x$ 的第 $i$ 位必须为奇数。
- 如果有任意一位不满足上述条件,则视为 $x$ 与 $s$ 不匹配。如果所有位均满足上述条件,则视为 $x$ 与 $s$ 匹配。
例如,如果 $s=010$,则 $92$、$2212$、$50$、$414$ 与 $s$ 匹配,而 $3$、$110$、$25$、$1030$ 与 $s$ 不匹配。
输入格式
第一行包含整数 $t$,表示操作次数。
接下来 $t$ 行,每行包含一个操作,格式如题面描述。
保证至少存在一个查询操作。
输出格式
每个查询操作输出一行结果,一个整数,表示集合中与 $s$ 匹配的元素个数。
数据范围
前 $4$ 个测试点满足 $1 \leq t \leq 20$。
所有测试点满足 $1 \leq t \leq {10}^{5}$,$0 \leq x < {10}^{18}$,$s$ 的长度范围 $[1,18]$。
输入样例1:
1 12 2 + 1 3 + 241 4 ? 1 5 + 361 6 - 241 7 ? 0101 8 + 101 9 ? 101 10 - 101 11 ? 101 12 + 4000 13 ? 0
输出样例1:
2 1 2 1 1
输入样例2:
1 5 2 + 200 3 + 200 4 ? 0 5 - 200 6 ? 0
输出样例2:
1 2 2 1
解题思路
对于任意一个数,我们不关心它每一位上的具体数值,而只用关心每一位数值的奇偶性,因为最多只用$18$位数,每一位上不是$0$就是$1$,因此一共有$2^{18}$种不同的状态。
因此可以开一个$2^{18}$大小的数组作为哈希表,对于每个数字,先把它根据每一位的奇偶性转换成对应的二进制数。对于添加操作,直接在对应的哈希表中加$1$,删除操作就在对应的哈希表中减$1$,查询操作就返回对应的哈希表中的值。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1 << 18; 5 6 int mp[N]; 7 8 int main() { 9 int n; 10 scanf("%d", &n); 11 while (n--) { 12 char op[5], str[20]; 13 scanf("%s %s", op, str); 14 int x = 0; 15 for (int i = 0; str[i]; i++) { 16 x = x << 1 | str[i] & 1; // '0'的ascii为48 17 } 18 19 if (op[0] == '+') mp[x]++; 20 else if (op[0] == '-') mp[x]--; 21 else printf("%d\n", mp[x]); 22 } 23 24 return 0; 25 }
还可以用Trie,就是比较麻烦。比赛的时候就想到Trie,因为想到是维护一堆$01$串,以及匹配查询,然后莫名想到状态机然后就想到用Trie了。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1.8e6 + 10; 5 6 int son[N][2], cnt[N], idx; 7 8 void insert(string str, bool flag) { // flag=true表示插入,flag=false表示删除 9 while (str.size() < 18) { 10 str = '0' + str; 11 } 12 int p = 0; 13 for (int i = 0; i < str.size(); i++) { 14 if (!son[p][str[i] & 1]) son[p][str[i] & 1] = ++idx; 15 p = son[p][str[i] & 1]; 16 } 17 if (flag) cnt[p]++; 18 else cnt[p]--; 19 } 20 21 int query(string str) { 22 while (str.size() < 18) { 23 str = '0' + str; 24 } 25 int p = 0; 26 for (int i = 0; i < str.size(); i++) { 27 if (!son[p][str[i] & 1]) return 0; 28 p = son[p][str[i] & 1]; 29 } 30 31 return cnt[p]; 32 } 33 34 int main() { 35 int n; 36 scanf("%d", &n); 37 while (n--) { 38 char op[5], str[20]; 39 scanf("%s %s", op, str); 40 if (op[0] == '+') insert(str, true); 41 else if (op[0] == '-') insert(str, false); 42 else printf("%d\n", query(str)); 43 } 44 45 return 0; 46 }
参考资料
AcWing 4604. 集合询问(AcWing杯 - 周赛):https://www.acwing.com/video/4244/
标签:匹配,int,18,询问,son,str,集合 From: https://www.cnblogs.com/onlyblues/p/16609395.html