2016 ECJTU - STL-白红宇

2016 ECJTU - STL

阅读量：4672 次

发布时间：2019-06-09

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

1、　　STL

2、总结：学长出的题，本来还想ak的，结果又被虐了。。。

3、标程和数据：

01 水

02 　水。题意：将1~n 全排列按字典序输出。

（1）dfs　　

//1002#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define F(i,a,b) for (int i=a;i

View Code

（2）next_permutation()

#include
      
       #define F(i,a,b) for (int i=a;i

View Code

03　　好题

1、题意：给你一个集合，n个整数，求出所有子集合的和的异或和。

2、总结：第一次用bitset。当要处理二进制位的有序集，每个位可能包含的是0（关）或1（开）的值，就应该可用bitset。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define F(i,a,b) for (int i=a;i
             
              A(0); //关键就是，用i表示集合的和，A[i]的0，1开关值表示这个集合出现的次数奇偶 while(~scanf("%d",&n)){ A.reset(); A.set(0); sum=0; FF(i,1,n) { scanf("%d",&x); A^=(A<

View Code

04 水，map应用。题意：n个点，求曼哈顿距离|xi-xj|+|yi-yj| 与欧几里得距离sqrt((xi-xj)^2+(yi-yj)^2) 相同的点对数

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #define F(i,a,b) for (int i=a;i
             
              ,int >S; map
              
               A,B; LL x,y,sum=0; while(n--){ scanf("%lld%lld",&x,&y); sum+=(A[x]+B[y]); sum-=S[make_pair(x,y)]; S[make_pair(x,y)]++; A[x]++;B[y]++; } cout<
               
                <

View Code

05 　好但很恶心的题，双端队列，类似。题意：模拟栈操作。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define F(i,a,b) for (int i=a;i

DQ; scanf("%d",&t); FF(cas,1,t){ DQ.clear(); flag=0; tot1=((N>>1)-1),tot2=(N>>1); scanf("%d",&n); printf("Case #%d:\n",cas); while(n--){ scanf("%s",str); if(str[2]=='S'){ scanf("%d",&x); if(!flag){ if(!x)DQ.push_back(tot1); a[tot1--]=x; }else { if(!x)DQ.push_front(tot2); a[tot2++]=x; } } else if(str[1]=='O'){ if(!flag){ tot1++; if(!a[tot1])DQ.pop_back(); }else { tot2--; if(!a[tot2])DQ.pop_front(); } } else if(str[0]=='R'){ flag^=1; } else { scanf("%d",&x); if(DQ.empty()) puts("Invalid."); else if(DQ.size()

::iterator it; if(!flag){ it=DQ.end(); cout<<*(it-x)-tot1<

View Code

06　好题，优先队列。题意：给出一个字符串，输出第k小的连续子串

//1006#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define F(i,a,b) for (int i=a;i
            
             s1.a; }};int main(){ string str; int k,i,j; S m; priority_queue
              Q; /* while(cin>>str){ scanf("%d",&k); while(!Q.empty()) Q.pop(); for(i=0;str[i];i++){ for(j=i;str[j];j++){ m.a=str.substr(i,j); //一开始先把所有的连续子串都压入，结果一直超内存，看了标程才发现可以简单地优化一下 Q.push(m); } } if(k>Q.size()) k=Q.size(); for(i=1;i
              
               >str){ scanf("%d",&k); while(!Q.empty()) Q.pop(); for(int i=0;str[i];i++) { st.a=str[i]; st.a_r=i; Q.push(st); } while(!Q.empty()){ st=Q.top(); Q.pop(); //cout<
               
                <

View Code

07 set.lower_bound()函数。题意：给你两个长度相同的序列A,B。求每一个Ai，在B序列中min(|A[i] - B[j]|) (1<=j<=i)是多少

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define F(i,a,b) for (int i=a;i

S; while(~scanf("%d",&n)) { S.clear(); S.insert(-MAX); S.insert(MAX); //先插入前后端，用lower_bound()时更方便一点 F(i,0,n) scanf("%d",&a[i]); F(i,0,n) scanf("%d",&b[i]); int pos,pre; set

::iterator it; F(i,0,n) { //scanf("%d",&b); //不能在这输入b[]，题目是要全部输入后一起输出 S.insert(b[i]); it=S.lower_bound(a[i]); pos=*it; pre=*(--it); //迭代器只能++，--，不能+1，-1 printf("%d\n",min(pos-a[i],a[i]-pre)); } } return 0;}

View Code

转载于:https://www.cnblogs.com/sbfhy/p/5981718.html