首页 > 其他分享 >集合询问

集合询问

时间:2022-08-21 10:11:07浏览次数:87  
标签:匹配 int 18 询问 son str 集合

集合询问

有一个整数集合,初始时集合为空。

现在,要对该集合进行 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

相关文章

  • day23--Java集合06
    Java集合0613.Map接口0213.2Map接口常用方法put():添加remove():根据键键删除映射关系get():根据键获取值size():获取元素个数isEnpty():判断个数是否为0clear():清除containsKey():查......
  • Java集合框架
    Java集合一、定义1、对象的容器,定义了对多个对象进行操作的常用方法,可实现数组的功能集合所在包为:Java。util.*2、集合和数组区别:数组长度固定,集合长度不固定数组可......
  • 2022-8-20 剑指offer-滑动窗口+(桶排序或者有序集合)
    剑指OfferII057.值和下标之差都在给定的范围内难度中等55收藏分享切换为英文接收动态反馈给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在......
  • python 中 判断列表、元组、字符串、字典、集合为空的方法
     001、>>>test1=[]>>>test1[]>>>ifnottest1:##判断列表为空...print("noelement")...noelement 002、>>>test......
  • JavaSE——Properties集合
    Properties集合Properties作为Map集合的使用介绍:是一个Map体系的集合类Properties可以保存到流中或从流中加载属性列表中的每个键及其对应的值都是一个字符串基本......
  • Python集合(Set)常用操作
    定义set是一个无序且不重复的元素集合。集合对象是一组无序排列可哈希的值,集合成员可以做字典中的键。集合用in和notin操作符检查成员,以len()內建函数得到集合的基数(大......
  • java-集合
    目录集合的分类:单列集合双列集合集合的分类:单列集合:只能存储一列数据的集合双列集合:有两列可以存储数据,是key-value键值对进行存储集合的框架:单列集合主要是Colle......
  • 集合框架5-----Map体系
    Map体系集合参考视频:13.33Map集合概述哔哩哔哩bilibili  HashMap(),代码如下:importjava.util.HashMap;importjava.util.Map;​​publicclassHashDemo2{ ......
  • 集合框架6-----Collection工具类
    Collection工具类:packagecom.mokuiran.collection;​importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Collections;importjava.util.List;​/**......
  • 解决查询问题-分库分表后
     多维度分片需求,如何解决查询问题? 大家好,我是【架构摆渡人】,一只十年的程序猿。这是分库分表系列的第一篇文章,这个系列会给大家分享很多在实际工作中有用的经验,如果......