Codeforces 558（C、D、E）总结

558C

题意：给你n个数，可对每个数进行操作（乘2或者除以2）。求最少的操作使得所有的数都相等。

思路 : dp[ t ] 表示所有的数转化到 t 所需的最少操作， vis[ t ] 表示有多少数可以转化成 t 。

对于一个数 num ， 把它所能到达的数用上述的数组记录下就行了（具体看代码）。

注意 ：

输入：

3

5 4 4

输出 ： 2 （5/2*2=4）

?

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn=100010; int n,vis[maxn],num[maxn]; void initial() { memset(num,0,sizeof(num)); memset(vis,0,sizeof(vis)); } void deal(int op) { int tp=op,ct=0; while(tp) { vis[tp]++; num[tp]+=ct; if(tp%2==1 && tp!=1) { int yp=tp/2*2,cnt=ct+2; while(yp
     
      
?
      
?
 558D
      
?
      
题意：给出n条信息，要你判断信息是否矛盾，或是否有多个出口，或是否有唯一出口。
 信息有两种类型，一个是出口的若干区间，一个不是出口若干区间。
      
思路： 先通过出口的若干区间找出出口所在的树中根节点的区间。然后在通过不是出
      
口的若干区间来判断。
      
?
      
?
      
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            #include 
           
             #define ll long long using namespace std; struct node { ll l,r; node(){} node(ll _l,ll _r):l(_l),r(_r){} }; vector 
            
              G; int n,m; ll st,ed; bool cmp(node p,node q) { if(p.l==q.l) return p.r
             
              ed) break; if(st
              
               
?
               
?
               
558E
               
?
               
题意：给你一个长度为n的字符串（下标从1开始），然后给你m个操作。每个操作有三个值 l,r,t。
               
如果t=1，表示将字符串中[ l ,r ]的部分按照升序排列。
               
如果t=0，表示将字符串中[ l ,r ]的部分按照降序排列。
               
最后要你输出原字符串经过m次操作后所形成的新的字符串。
               
思路：对于26个小写字母（a-z），分别建立线段树，即建26个线段树。
               
即每次修改 [ l , r ] 区间，则先通过26课线段树分别求出这个区间内的a–z的个数。然后将26课线
               
段树内的这一区间和置为0。最后再根据顺序重新给26课线段树的这一区间赋值就行了。
               
?
               
#include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      using namespace std; const int N=100010; const int M=26; struct node { int l,r,sum,cover; } a[M][N*4]; string str; int n,m; void build(int cnt,int l,int r,int k) { a[cnt][k].l=l; a[cnt][k].r=r; a[cnt][k].sum=0; a[cnt][k].cover=-1; if(l==r) return ; int mid=(l+r)>>1; build(cnt,l,mid,2*k); build(cnt,mid+1,r,2*k+1); } void push_down(int cnt,int k) { if(a[cnt][k].cover!=-1) { a[cnt][k*2].cover=a[cnt][k*2+1].cover=a[cnt][k].cover; a[cnt][k*2].sum=(a[cnt][k*2].r+1-a[cnt][k*2].l)*a[cnt][k*2].cover; a[cnt][k*2+1].sum=(a[cnt][k*2+1].r+1-a[cnt][k*2+1].l)*a[cnt][k*2+1].cover; a[cnt][k].cover=-1; } } void update(int cnt,int l,int r,int k,int num) { if(l==a[cnt][k].l && r==a[cnt][k].r) { a[cnt][k].cover=num; a[cnt][k].sum=(a[cnt][k].r+1-a[cnt][k].l)*num; return ; } push_down(cnt,k); int mid=(a[cnt][k].l+a[cnt][k].r)>>1; if(r<=mid) update(cnt,l,r,2*k,num); else if(l>mid) update(cnt,l,r,2*k+1,num); else { update(cnt,l,mid,2*k,num); update(cnt,mid+1,r,2*k+1,num); } a[cnt][k].sum=a[cnt][k*2].sum+a[cnt][k*2+1].sum; } int query(int cnt,int l,int r,int k) { if(l==a[cnt][k].l && r==a[cnt][k].r) return a[cnt][k].sum; push_down(cnt,k); int mid=(a[cnt][k].l+a[cnt][k].r)>>1; if(r<=mid) return query(cnt,l,r,2*k); else if(l>mid) return query(cnt,l,r,2*k+1); else return query(cnt,l,mid,2*k)+query(cnt,mid+1,r,2*k+1); } void input() { for(int i=0; i
                     
                      =0; i--) if(num[i]) { update(i,pos,pos+num[i]-1,1,1); pos=pos+num[i]; } } } for(int i=1; i<=n; i++) for(int j=0; j
                      
                     
                    
                   
                  
                 
 
               
 
               
 
               
?