CUGBACM Codeforces Tranning 3 题解 - c++编程基础

描述：第三场CF训练了，这次做的挺搞笑的，我记得这是内天持续训练九个小时中的最后两个小时，想想也是蛮拼的。

题解：

A.Triangle

题意：给四个边，如果能组成判断能不能从其中找三条边组成三角形，不就再判断能不能三条边首尾相接组成一个线段。

思路：三角形判断条件，两条边之和大于第三条边，两边之和等于第三条边就是线段。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define eps 1e-8 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 #define LOCAL typedef long long LL; typedef unsigned long long ULL; using namespace std; int main() { int a[5]; for(int i=0;i<4;i++) scanf(%d,&a[i]); sort(a,a+4); if(a[0]+a[1]>a[2]||a[1]+a[2]>a[3]) puts(TRIANGLE); else if(a[0]+a[1]==a[2]||a[1]+a[2]==a[3]||a[0]+a[2]==a[3]) puts(SEGMENT); else puts(IMPOSSIBLE); return 0; }

B.Alice, Bob and Chocolate

题意：两个人，一个从左边开始吃巧克力，一个右边开始吃巧克力，两个人吃的速度是一样的，如果两人同时开始吃同一块巧克力，右边人放弃。问两边人各吃多少个巧克力。

思路：记每个个每个巧克力吃的时间，比一下就行。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define eps 1e-8 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 #define LOCAL typedef long long LL; typedef unsigned long long ULL; using namespace std; int main() { int tot; scanf(%d,&tot); int aa[100005]; int l[100005],r[100005]; int sum = 0; l[0]=0; for(int i=0;i
                
                 =0;i--) r[i]=r[i+1]+aa[i+1]; int Alice = 0,Bob = 0; for(int i=0;i
                 
                  C.President's Office
                  ?






                   题意：给一个n*m的图，里面用大写字母表示桌子，找到和给出的字母相邻的字母的种类数之和。
                   思路：对于每个存在的字母找一下上，下，左，右即可。
                   代码：
                  ?
                  #include 
                   
                    
#include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include
                            #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #define eps 1e-8 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 #define LOCAL typedef long long LL; typedef unsigned long long ULL; using namespace std; char ss[105][105]; bool vis[60]; int main() { int row,col; char cap[5]; scanf(%d%d%s,&row,&col,cap); for(int i=0;i
                                 
                                  0) if(ss[i-1][j]!=cap[0]&&ss[i-1][j]>='A') vis[ss[i-1][j]-'A']=1; if(j>0) if(ss[i][j-1]!=cap[0]&&ss[i][j-1]>='A') vis[ss[i][j-1]-'A']=1; if(i
                                  
                                   ='A') vis[ss[i+1][j]-'A']=1; if(j
                                   
                                    ='A') vis[ss[i][j+1]-'A']=1; } } } int ans = 0; for(int i=0;i<26;i++) if(vis[i]) ans++; printf(%d ,ans); return 0; }
                                   
                                  
                                 
                                
                               
                              
                             
                            
                          
                         
                        
                       
                      
                     
                    
                    
                  
 
                  ? 
                  D.Longest Regular Bracket Sequence 
                  题意：给一个长的字符串，其中都是(和)，问最长的合理括号匹配子串是多长，并且找出该长度的子串有多少个。 
                  思路：比赛的时候，了。是写DP搞了好久都搞不出来，加上脑子糊里糊涂的，就GG了。思路是这样的，对于每个)，如果它左边的是合理的匹配，并且找到它左边的合理匹配的第一个(的左端也是(，那么它的匹配数是左边的匹配数+2，即dp[i]=dp[i-1]+2，并且如果找到的合理匹配的左端还存在合理匹配，那么它的合理匹配长度还要加上前面合理匹配的长度。 
                  代码： 
                  ? 
                  #include 
                   
                    
#include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include
                            #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #define eps 1e-8 #define INF 0x7fffffff #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 #define LOCAL typedef long long LL; typedef unsigned long long ULL; using namespace std; int dp[1000005]; char ss[1000005]; int main() { int i , time = 1,ans = 0; scanf(%s,ss); memset(dp,0,sizeof(dp)); for(i=1; ss[i]!=''; i++) { if(i-dp[i-1]-1>=0&&ss[i]==')'&&ss[i-dp[i-1]-1]=='(') { dp[i]=dp[i-1]+2; if(i-dp[i-1]-2>=0) dp[i]+=dp[i-dp[i-1]-2]; } if(dp[i]>ans) { ans = dp[i]; time = 1; } else if(dp[i]==ans&&ans!=0) { time++; } } printf(%d %d ,ans,time); }
                                
                               
                              
                             
                            
                          
                         
                        
                       
                      
                     
                    
                    
                  
 
                  
 
                  ? 
                  E.Exposition
 题意：给出N本书，n<=10^5，这n本书按出版时间给出的，给出了每本书的高度hi。并且给出一个k，k<=10^6，要求在n本书选择其中连续的若干本书，其中最高的高度比最高的高度不能大于k，问最多可以选择多少本书。 
                  思路：二分+RMQ。从左至右依次选择每本书作为起点，二分来选择符合条件的终点来保证以该本书为起点的长度最长，对于每次的终点，

CUGBACM Codeforces Tranning 3 题解(一)