不明觉厉的数据结构题2-白红宇

不明觉厉的数据结构题2

阅读量：4322 次

发布时间：2019-06-06

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

例1 Harmony Forever hdu3303

题目要求你维护一个集合，每次插入一个数x，或询问集合中模一个给定数y的最小数。

操作数n<=4*10^4，x,y<=5*10^5。

首先对于一个模y的询问，我们可以在插入的时候就处理出这个答案，假设我们对于<=p的y处理出所有答案，那么插入是O(p)的，询问O(1)。

然后对于>p的y我们可以暴力查询大于等于ky的数最小是多少，暴力枚举这个k，用一些你喜爱的数据结构（set？）来维护这个集合，询问复杂度大约是O(x/p*logn)

不妨设logn≈15（算上常数），那么令x/p*logn=p，p≈2700。保险起见开了3000。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              using namespace std;int P=3000;typedef pair
               
                 pii;set
                
                  s;pii minn[23333];int maxn=0;void sol(int q){ s.clear(); for(int i=1;i<=P;i++) minn[i]=pii(2000000000,-1); int t=0; maxn=0; while(q--) { char o[3]; int a; scanf("%s%d",o,&a); if(o[0]=='B') { pii cur=pii(a,-(++t)); maxn=max(maxn,a); for(int j=1;j<=P;j++) minn[j]=min(minn[j],pii(a%j,-t)); s.insert(cur); } else { if(!maxn) {puts("-1"); continue;} if(a<=P) printf("%d\n",-minn[a].second); else { pii mans=pii(2000000000,-1); for(int k=0;k*a<=maxn;k++) { set
                 
                  ::iterator ii=s.lower_bound(pii(k*a,-23333333)); if(ii!=s.end()) { pii p=*ii; p.first%=a; mans=min(mans,p); } } printf("%d\n",-mans.second); } } }}int main(){ int cs=0,q; while(scanf("%d",&q),q) { if(cs) putchar(10); printf("Case %d:\n",++cs); sol(q); }}

本来还有一题，后来发现那题实在裸的不行就先不放上来了

转载于:https://www.cnblogs.com/zzqsblog/p/5451064.html

你可能感兴趣的文章