牛客小白月赛6-G-指纹锁（STL set 集合& 线段树 )

程序员文章站 2022-05-14 09:26:10

...

题目

HA实验有一套非常严密的安全保障体系，在HA实验基地的大门，有一个指纹锁。

    该指纹锁的加密算法会把一个指纹转化为一个不超过1e7的数字，两个指纹数值之差越小，就说明两个指纹越相似，当两个指纹的数值差≤k时，这两个指纹的持有者会被系统判定为同一个人。
    现在有3种操作，共m个，
操作1：add x，表示为指纹锁录入一个指纹，该指纹对应的数字为x，如果系统内有一个与x相差≤k的指纹，则系统会忽略这次添加操作
操作2：del x，表示删除指纹锁中的指纹x，若指纹锁中多个与x相差≤k的指纹，则全部删除，若指纹锁中没有指纹x，则可以忽略该操作，
操作3：query x，表示有一个持有指纹x的人试图打开指纹锁，你需要设计一个判断程序，返回该人是否可以打开指纹锁（只要x与存入的任何一个指纹相差≤k即可打开锁）。
    初始状态，指纹锁中没有任何指纹。

输入描述:

第一行有2个正整数m，k。
接下来m行，每行描述一种操作：add x，del x或query x。

输出描述:

对于每个query操作，输出一行，包含一个单词“Yes”或“No”，表示该人是否可以打开指纹锁。

解题过程：题目意思很好理解，对指纹进行增删查的操作，第一个就想到线段树，但是线段树的操作中遇到了很多问题，1e7的数量级担心开int的树会爆内存，开了char的字符数组，还有一个问题就是一开始没想到插入节点时应该查找一下，因为两个相邻节点的区间如果出现交集的话，这两个指纹就没法识别了，所以不能插入。

#include<iostream>
#include<cstring>
using namespace std;
char tree[80000010];
bool father[80000010];
int flag=0;
void add(int i,int l,int r,int x){
//	cout<<"250"<<endl;
	if(l==r){
		tree[i]=1;
		father[i]=false;
		return;
	}
	if(father[i]){
		father[i]=false;
		father[i<<1]=father[(i<<1)+1]=true;
		tree[i<<1]=tree[(i<<1)+1]=0;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		add(i<<1,l,mid,x);
	else
		add((i<<1)+1,mid+1,r,x);
	tree[i]=max(tree[i<<1],tree[(i<<1)+1]);
}
void que(int i,int l,int r,int ll,int rr){
	if(rr<l||ll>r||father[i]||tree[i]==0||father[i]){
		return;
	}
	if(ll<=l&&r<=rr){
		if(tree[i]==1){
			flag=1;
		}
		return;
	}
	int mid=(l+r)>>1;
	if(ll<mid)
		que(i<<1,l,mid,ll,rr);
	if(rr>mid)
		que((i<<1)+1,mid+1,r,ll,rr);
}
void del(int i,int l,int r,int ll,int rr){
	if(father[i])return;
	if(ll<=l&&r<=rr){
		tree[i]=0;
		father[i]=true;
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)
	del(i<<1,l,mid,ll,rr);
	if(rr>mid)
	del((i<<1)+1,mid+1,r,ll,rr);
	tree[i]=max(tree[i<<1],tree[(i<<1)+1]);
}
int main(){
	int m,k;
	cin>>m>>k;
	while(m--){
		char c[10];
		int x;
		int n=20000001;
		cin>>c>>x;
		x+=10000001;
		if(c[0]=='a'){
			flag=0;
			int l=max(1,x-k),r=min(n,x+k);
			que(1,1,n,l,r);
			if(!flag)
				add(1,1,n,x);
		}
		else if(c[0]=='q'){
			int l=max(1,x-k),r=min(n,x+k);
			flag=0;
			
			que(1,1,n,l,r);
			
			if(flag){
				cout<<"Yes"<<endl;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		else{
			int l=max(1,x-k),r=min(n,x+k);
			del(1,1,n,l,r);
		}
	}
}

后来又看到好多大佬用set写，不会用set就学了下set的操作：

(转）

set集合容器实现了红黑树（Red-Black Tree）的平衡二叉检索树的的数据结构，在插入元素时，它会自动调整二叉树的排列，把该元素放到适当的位置，以确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的键值；另外，还得确保根节点的左子树的高度与有字数的高度相等，这样，二叉树的高度最小，从而检索速度最快。要注意的是，它不会重复插入相同键值的元素，而采取忽略处理。

set的特性是，所有元素都会根据元素的键值自动排序，set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。

set的各成员函数列表如下:

1. begin()--返回指向第一个元素的迭代器

2. clear()--清除所有元素

3. count()--返回某个值元素的个数

4. empty()--如果集合为空，返回true

5. end()--返回指向最后一个元素的迭代器

6. equal_range()--返回集合中与给定值相等的上下限的两个迭代器

7. erase()--删除集合中的元素

8. find()--返回一个指向被查找到元素的迭代器

9. get_allocator()--返回集合的分配器

10. insert()--在集合中插入元素

11. lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

12. key_comp()--返回一个用于元素间值比较的函数

13. max_size()--返回集合能容纳的元素的最大限值

14. rbegin()--返回指向集合中最后一个元素的反向迭代器

15. rend()--返回指向集合中第一个元素的反向迭代器

16. size()--集合中元素的数目

17. swap()--交换两个集合变量

18. upper_bound()--返回大于某个值元素的迭代器

19. value_comp()--返回一个用于比较元素间的值的函数

#include<iostream>
#include<set>
#include<cmath>
using namespace std;
int m,k;
struct cmp{
	bool operator()(int a,int b){
		if(abs(a-b)<=k)
			return false;
		return a<b;
	}
};
set<int,cmp>s;
int main(){
	cin>>m>>k;
	int x;
	char c[10];
	while(m--){
		cin>>c>>x;
		if(c[0]=='a'){
			if(s.find(x)==s.end()){
				s.insert(x);
			}
		}
		else if(c[0]=='d'){
			s.erase(x);
		}
		else{
			if(s.find(x)!=s.end())
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}
	}
	return 0;
}