题目
题意:
维护一个集合。给定两种操作,1.插入一个集合中没有的数x;2.查找不在集合中的最小的k的倍数。
思路:
拿一个set维护集合中的数,另外拿map维护每个k上一次枚举到哪里,因为mex随着集合的增加只增不减的。这样复杂度也就n+n/2+n/3…≈nlnn
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,m,k,T;
set<ll> sa;
map<ll,ll> mp;
void solve()
{
char ch; ll x;
cin>>ch>>x;
if(ch=='+')
{
sa.insert(x);
}
else
{
for(ll i=mp[x]==0?x:mp[x];;i+=x)
{
if(!sa.count(i))
{
mp[x] = i;
cout<<i<<"\n";
return ;
}
}
}
}
signed main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>T;
while(T--)
solve();
return 0;
}
版权声明:本文为xianqiuyigedao原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。