刷题记录:牛客NC17508指纹锁(基于学习算法对部分重载运算符进行个人理解)

传送门:牛客

   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即可打开锁）。初始状态，指纹锁中没有任何指纹。
输入:
4 3
add 1
add 10
query 5
query 4
输出:
No
Yes

刚开始的思路:
首先观察1e7的数值,直接用数组有爆内存的危险,然后想了想采用map来记录指纹差异内拥有的情况,同时采用set来记录指纹录取人的情况(这是确定的),每次输入opt的时候for循环判断一下正负k的情况

map<int,int>vis;
set<int>a;
int main() {ios::sync_with_stdio(0);int m,k;m=read();k=read();string opt;int x;vis.clear();a.clear();for(int i=1;i<=m;i++) {cin>>opt>>x;if(opt[0]=='a') {if(vis[x]==0) {a.insert(x);for(int j=x+k;j>=x-k;j--) {vis[j]=vis[j]+1;}}}else if(opt[0]=='d') {for(int j=x+k;j>=x-k;j--) {if(a.find(j)!=a.end()) {a.erase(j);for(int kk=j+k;kk>=j-k;kk--) vis[kk]=vis[kk]-1;}}}else if(opt[0]=='q') {if(vis[x]>0) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

然后很快乐的得到了0分(全部超时,我当时直接NM,一分都没有,这思路有这么烂吗)

然后看了题解,发现set用的是没有毛病的,但是for循环可以直接使用stl的重载运算符来优化

下面就是本题解与众不同的地方了[其他大部分算法题解里面对于重载运算符的解释几乎没有,有也是一笔带过(不排除当事人不会,或者不屑于讲的情况包括刘汝佳的紫书中对于STL这部分的内容也不是很详细)]
    虽然这部分是属于工程代码差不多的一部分了,网上大多数的讲解也是对于熟悉类(class,public)等操作的人群,代码又臭又长,对于纯算法方面的几乎没有(百度,google都一样),因此在经过大量查阅和YY之后,我有了一些理解,力求能够帮助各位理解

首先是对于本题中将要用到的set中重载运算符(为什么我要强调是set呢?)

struct cmp {bool operator()(int l,int r) const {if(abs(l-r)<=k) return false;else return l<r;}
};
set<int,cmp>

注意上面的cmp函数,首先对于这样形式的表示(下面[ ]里的为解释,不是代码)

bool[也可以是其他,比如int] operator ()[也可以是其他符号,比如>,<] (int l,int r) const {} 

在上面的代码中()表示这个是一个伪函数,我们可以当做这是一个要运作的函数,这个函数在不同的地方有不同的规范(所以在其他地方使用的时候,重载运算符的方法并不是一样的!!!,不要被搞混了)
而对于上面的这种表示法中我们的l,r是没有用cmp来定义的.所以我们能定义不止一个的变量(请对我讲述的顺序不要介意,如果不清楚这一部分可以先忍一忍,在之后会解释),而如果用外部成员来定义,比如cmp l,cmp r,这样的话就被成为是成员函数

我们先来讲非成员函数,列如上面set用到的函数,在这之前我们先来看下面这个代码

对于上面的Adder,我们此时是定义了一个类,对于后面的x,y.我们是用Adder这个类来定义了x,y两个实例对象,然后看向下面的英文解释,对于Adder{}(42,35),我们在实例化的同时调用了()这个运算符,然后又因为()是被重载的,所以此时我们就会调用下面的重载函数,注意,此时的左边的a即被赋值为42,而b即被赋值为35[可以类似的认为,前面的对应左边的参数,后面定义的对应右边的参数]并且注意此时的const是不能省略的.

然后类似的看向这个代码

对于上面的Add_k(int x) :k(x){}不理解没有任何问题,可以当做是在类里面提前声明x,相当于一种规范,去掉照样能够运行.然后看向for_each,这种函数类似于javascript中的foreach函数,是枚举元素的作用,然后第三个参数调用了一个struct,这时候就会给每一个元素都运行这个函数,也就是给每一个元素都加上10

看完上面的函数,我们应该类似的猜想出这种重载在set中的使用了吧,类似的,在set的运行过程中,a代表当前的函数,b代表枚举到的值(这种就类似于javascript中foreach有value,index,array等参数),这种参数的名字是没有意义的,但是顺序却代表了数组值,数组索引和数组本身.类似的,在set中也是这样,算是相当于set的重载方法吧(注意,在其他地方,重载运算符的规定和写法不一定与上方相同)

ps:这种伪函数是绑定在每一个set中的元素中的,相当于for枚举了一遍(不要问我怎么枚举set里的元素,c++STL并没有提供)

理解了这些时候就可以写出代码了,

set<int,cmp>num;
char opt[10];
int main() {m=read();k=read();int x;while(m--) {scanf("%s",opt);scanf("%d",&x);if(opt[0]=='a') num.insert(x);else if(opt[0]=='d') num.erase(x);else {if(num.find(x)!=num.end()) {printf("Yes\n");}else {printf("No\n");}}}return 0;
}

注意下方代码涉及到了Dijksla堆优化求最短路的算法,请了解此方法后实用,想直接看代码可以移步这里

struct heapnode{int d,u;bool operator<(const heapnode &rhs) const{return d>rhs.d;}
};
priority_queue<heapnode>q;