本文共 1376 字，大约阅读时间需要 4 分钟。

题目链接：

当时这个题卡了好久，用了两个map一直超时。 一直想用并查集，但是一直想不出来怎么用。赛后问的lzh大佬才知道的。 map+并查集。 1操作的时候，就把这个值的map设置为x+1。即mp[x]=x+1; 2操作的时候，如果这个值再map里面找不到，就说明还可以用，就输出这个值。如果找得到，就说明不能用了。那我们就用find函数去找能用的那个点，并且压缩路径。假如2,3，4,5不能用。查询2的时候，find会把map[2,3,4,5]的值都变为6.这样就压缩路径，节省了大量的时间。 代码如下：

#include
   
    #define ll long longusing namespace std;map
    
      mp;inline int find(int x){
       map
     
       ::iterator it=mp.find(x);	if(it==mp.end()) return x;	else 	{
   		return mp[x]=find(mp[x]);	}}int main(){
   	int op,x,n,m;	while(~scanf("%d%d",&n,&m))	{
   		while(m--)		{
   			scanf("%d%d",&op,&x);			if(op==1) mp[x]=x+1;			else			{
   				if(mp.find(x)==mp.end()) printf("%d\n",x);				else				{
   					int ans=find(x);					printf("%d\n",ans);				}			}		}	}}
     
    
   

队友比赛的时候用的set过的。

代码如下：

#include
   
    #include
    
     #include
     
      using namespace std;int main(){
   	int n,m;	scanf("%d%d",&n,&m);	set
      
       s;	while(m--){
   		int maxx=0;		int op;		int x;		scanf("%d%d",&op,&x);		if(op==1){
   			s.insert(x);		}		else{
   			set
       
        ::iterator it;			it=s.lower_bound(x);			if(it==s.end()||(*it)!=x){
   				printf("%d\n",x);				continue;			}			else{
   				it++;				int ans=x+1;				for(;it!=s.end();it++){
   					if(ans!=(*it)){
   						break;					}					else{
   						ans++;					}				}				printf("%d\n",ans);			}					}	} }
       
      
     
    
   

努力加油a啊，(^o)/~

转载地址：http://yktvi.baihongyu.com/