BestCoder Round #20 解题报告 A.B.C. - c++编程基础

A题：who is the best?
题目地址：HDU 5123
水题。
哈希，然后枚举找最大的，从小的开始找。
代码如下：
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 int a[102]; int main() { int t, n, i, x, max1, y; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); scanf("%d",&n); max1=-1; for(i=0;i
             
              
 
              B题：lines 
              题目地址：HDU 5124 
              离散化+扫描线 
              先将各点离散化，然后标记起点+1和终点-1，然后从左向右扫描找最大值。 
              代码如下：





 
               
              #include 
               
                
#include 
                
                  #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                        #include 
                        
                          #include 
                         
                           using namespace std; #define LL __int64 struct node { int x, y; }fei[300000]; int a[300000], c[300000], dp[300000], d[300000], cnt; int bin_search(int x) { int low=0, high=cnt-1, mid; while(low<=high) { mid=low+high>>1; if(d[mid]>x) high=mid-1; else if(d[mid]==x) return mid; else low=mid+1; } } int main() { int t, i, j, x, y, max1, s, n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i
                          
                           
 
                           C题：magic balls 
                           题目地址：HDU 5125 
                            
                           线段树+DP 
                           这题的DP思路很好想。就是找消耗当前能量下的最长上升序列的最大值，然后+1.这样复杂度是n*m*n，显然会超时，在这里可以注意到，最后的n是可以用线段树优化成logn的。于是就用m棵线段树来维护m个能量消耗下的DP信息。 
                           代码如下： 
                            
                           #include 
                            
                             
#include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #include 
                                 
                                   #include 
                                  
                                    #include 
                                   
                                     #include 
                                     #include 
                                     
                                       #include 
                                      
                                        using namespace std; #define LL __int64 const int INF=0x3f3f3f3f; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 #define root 0, cnt-1, 1 struct node { int a, b; } fei[1002]; int Maxdp[1002][8001], d[2001], c[2001], cnt, a[1001],b[1001]; void PushUp(int m, int rt) { Maxdp[m][rt]=max(Maxdp[m][rt<<1],Maxdp[m][rt<<1|1]); } void Update(int m, int p, int x, int l, int r, int rt) { if(l==r) { Maxdp[m][rt]=x; return ; } int mid=l+r>>1; if(p<=mid) Update(m,p,x,lson); else Update(m,p,x,rson); PushUp(m,rt); } int Query(int m, int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r) { return Maxdp[m][rt]; } int mid=l+r>>1; int ans=0; if(ll<=mid) ans=max(ans,Query(m,ll,rr,lson)); if(rr>mid) ans=max(ans,Query(m,ll,rr,rson)); return ans; } int bin_search(int x) { int low=0, high=cnt-1, mid; while(low<=high) { mid=low+high>>1; if(c[mid]>x) high=mid-1; else if(c[mid]