首页 > 代码库 > CUGBACM Codeforces Tranning 3 题解

CUGBACM Codeforces Tranning 3 题解

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

题解:

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

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

代码:

[cpp] view plaincopy
  1. #include <algorithm>  
  2. #include <cmath>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <cstring>  
  6. #include <ctime>  
  7. #include <ctype.h>  
  8. #include <iostream>  
  9. #include <map>  
  10. #include <queue>  
  11. #include <set>  
  12. #include <stack>  
  13. #include <string>  
  14. #include <vector>  
  15. #define eps 1e-8  
  16. #define INF 0x7fffffff  
  17. #define maxn 10005  
  18. #define PI acos(-1.0)  
  19. #define seed 31//131,1313  
  20. #define LOCAL  
  21. typedef long long LL;  
  22. typedef unsigned long long ULL;  
  23. using namespace std;  
  24. int main()  
  25. {  
  26.     int a[5];  
  27.     for(int i=0;i<4;i++)  
  28.         scanf("%d",&a[i]);  
  29.     sort(a,a+4);  
  30.     if(a[0]+a[1]>a[2]||a[1]+a[2]>a[3])  
  31.         puts("TRIANGLE");  
  32.     else if(a[0]+a[1]==a[2]||a[1]+a[2]==a[3]||a[0]+a[2]==a[3])  
  33.         puts("SEGMENT");  
  34.     else puts("IMPOSSIBLE");  
  35.     return 0;  
  36. }  

B.Alice, Bob and Chocolate

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

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

代码:

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <algorithm>  
  2. #include <cmath>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <cstring>  
  6. #include <ctime>  
  7. #include <ctype.h>  
  8. #include <iostream>  
  9. #include <map>  
  10. #include <queue>  
  11. #include <set>  
  12. #include <stack>  
  13. #include <string>  
  14. #include <vector>  
  15. #define eps 1e-8  
  16. #define INF 0x7fffffff  
  17. #define maxn 10005  
  18. #define PI acos(-1.0)  
  19. #define seed 31//131,1313  
  20. #define LOCAL  
  21. typedef long long LL;  
  22. typedef unsigned long long ULL;  
  23. using namespace std;  
  24. int main()  
  25. {  
  26.     int tot;  
  27.     scanf("%d",&tot);  
  28.     int aa[100005];  
  29.     int l[100005],r[100005];  
  30.     int sum = 0;  
  31.     l[0]=0;  
  32.     for(int i=0;i<tot;i++)  
  33.     {  
  34.         scanf("%d",&aa[i]);  
  35.     }  
  36.     for(int i=1;i<tot;i++)  
  37.         l[i]=l[i-1]+aa[i-1];  
  38.     r[tot-1]=0;  
  39.     for(int i=tot-2;i>=0;i--)  
  40.         r[i]=r[i+1]+aa[i+1];  
  41.     int Alice = 0,Bob = 0;  
  42.     for(int i=0;i<tot;i++)  
  43.     {  
  44.         if(l[i]<=r[i])  
  45.         Alice++;  
  46.     else Bob++;  
  47.     }  
  48.     cout<<Alice<<" "<<Bob<<endl;  
  49. }  

C. 题意:给一个n*m的图,里面用大写字母表示桌子,找到和给出的字母相邻的字母的种类数之和。

 

思路:对于每个存在的字母找一下上,下,左,右即可。

代码:

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <algorithm>  
  2. #include <cmath>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <cstring>  
  6. #include <ctime>  
  7. #include <ctype.h>  
  8. #include <iostream>  
  9. #include <map>  
  10. #include <queue>  
  11. #include <set>  
  12. #include <stack>  
  13. #include <string>  
  14. #include <vector>  
  15. #define eps 1e-8  
  16. #define INF 0x7fffffff  
  17. #define maxn 10005  
  18. #define PI acos(-1.0)  
  19. #define seed 31//131,1313  
  20. #define LOCAL  
  21. typedef long long LL;  
  22. typedef unsigned long long ULL;  
  23. using namespace std;  
  24. char ss[105][105];  
  25. bool vis[60];  
  26. int main()  
  27. {  
  28.     int row,col;  
  29.     char cap[5];  
  30.     scanf("%d%d%s",&row,&col,cap);  
  31.     for(int i=0;i<row;i++)  
  32.         scanf("%s",ss[i]);  
  33.     for(int i=0;i<row;i++)  
  34.     {  
  35.         for(int j=0;j<col;j++)  
  36.         {  
  37.             if(ss[i][j]==cap[0])  
  38.             {  
  39.                 if(i>0)  
  40.                     if(ss[i-1][j]!=cap[0]&&ss[i-1][j]>=‘A‘)  
  41.                         vis[ss[i-1][j]-‘A‘]=1;  
  42.                 if(j>0)  
  43.                     if(ss[i][j-1]!=cap[0]&&ss[i][j-1]>=‘A‘)  
  44.                         vis[ss[i][j-1]-‘A‘]=1;  
  45.                 if(i<row)  
  46.                     if(ss[i+1][j]!=cap[0]&&ss[i+1][j]>=‘A‘)  
  47.                         vis[ss[i+1][j]-‘A‘]=1;  
  48.                 if(j<col)  
  49.                     if(ss[i][j+1]!=cap[0]&&ss[i][j+1]>=‘A‘)  
  50.                         vis[ss[i][j+1]-‘A‘]=1;  
  51.             }  
  52.         }  
  53.     }  
  54.     int ans = 0;  
  55.     for(int i=0;i<26;i++)  
  56.         if(vis[i])  
  57.         ans++;  
  58.     printf("%d\n",ans);  
  59.     return 0;  
  60. }  

 

D.Longest Regular Bracket Sequence

题意:给一个长的字符串,其中都是"("和")",问最长的合理括号匹配子串是多长,并且找出该长度的子串有多少个。

思路:比赛的时候,了。是写DP搞了好久都搞不出来,加上脑子糊里糊涂的,就GG了。思路是这样的,对于每个")",如果它左边的是合理的匹配,并且找到 它左边的合理匹配的第一个"("的左端也是"(",那么它的匹配数是左边的匹配数+2,即dp[i]=dp[i-1]+2,并且如果找到的合理匹配的左端 还存在合理匹配,那么它的合理匹配长度还要加上前面合理匹配的长度。

代码:

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <algorithm>  
  2. #include <cmath>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <cstring>  
  6. #include <ctime>  
  7. #include <ctype.h>  
  8. #include <iostream>  
  9. #include <map>  
  10. #include <queue>  
  11. #include <set>  
  12. #include <stack>  
  13. #include <string>  
  14. #include <vector>  
  15. #define eps 1e-8  
  16. #define INF 0x7fffffff  
  17. #define maxn 10005  
  18. #define PI acos(-1.0)  
  19. #define seed 31//131,1313  
  20. #define LOCAL  
  21. typedef long long LL;  
  22. typedef unsigned long long ULL;  
  23. using namespace std;  
  24. int dp[1000005];  
  25. char ss[1000005];  
  26. int main()  
  27. {  
  28.     int i , time = 1,ans = 0;  
  29.     scanf("%s",ss);  
  30.     memset(dp,0,sizeof(dp));  
  31.     for(i=1; ss[i]!=‘\0‘; i++)  
  32.     {  
  33.         if(i-dp[i-1]-1>=0&&ss[i]==‘)‘&&ss[i-dp[i-1]-1]==‘(‘)  
  34.         {  
  35.             dp[i]=dp[i-1]+2;  
  36.             if(i-dp[i-1]-2>=0)  
  37.                 dp[i]+=dp[i-dp[i-1]-2];  
  38.         }  
  39.         if(dp[i]>ans)  
  40.         {  
  41.             ans = dp[i];  
  42.             time = 1;  
  43.         }  
  44.         else if(dp[i]==ans&&ans!=0)  
  45.         {  
  46.             time++;  
  47.         }  
  48.     }  
  49.     printf("%d %d\n",ans,time);  
  50. }  


E.Exposition
题意:给出N本书,n<=10^5,这n本书按出版时间给出的,给出了每本书的高度hi。并且给出一个k,k<=10^6,要求在n本书选择其中连续的若干本书,其中最高的高度比最高的高度不能大于k,问最多可以选择多少本书。

思路:二分+RMQ。从左至右依次选择每本书作为起点,二分来选择符合条件的终点来保证以该本书为起点的长度最长,对于每次的终点,找到起点终点之间的最高高度和最低高度,如果符合条件,那么终点右移,否则终点左移。查询最高高度和最低高度的方式是ST表,O(NlogN)的预处理,然后O(1)的查询,二分的过程中的复杂度也是O(NlogN)。

代码:

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include <algorithm>  
  2. #include <cmath>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <cstring>  
  6. #include <ctime>  
  7. #include <ctype.h>  
  8. #include <iostream>  
  9. #include <map>  
  10. #include <queue>  
  11. #include <set>  
  12. #include <stack>  
  13. #include <string>  
  14. #include <vector>  
  15. #define eps 1e-8  
  16. #define INF 0x7fffffff  
  17. #define maxn 100005  
  18. #define PI acos(-1.0)  
  19. #define seed 31//131,1313  
  20. #define LOCAL  
  21. typedef long long LL;  
  22. typedef unsigned long long ULL;  
  23. using namespace std;  
  24. int stTable_min[maxn][32],stTable_max[maxn][32];  
  25. int preLog2[maxn];  
  26. int h[maxn];  
  27. int Left[maxn],Right[maxn];  
  28. int ans = 0,times = 0;  
  29. void st_prepare(int n,int *array)  
  30. {  
  31.     preLog2[1]=0;  
  32.     for(int i=2; i<=n; i++)  
  33.     {  
  34.         preLog2[i]=preLog2[i-1];  
  35.         if((1<<preLog2[i]+1)==i)  
  36.             preLog2[i]++;  
  37.     }  
  38.     for(int i=n-1; i>=0; i--)  
  39.     {  
  40.         stTable_min[i][0]=array[i];  
  41.         stTable_max[i][0]=array[i];  
  42.         for(int j=1; (i+(1<<j)-1)<n; j++)  
  43.         {  
  44.             stTable_min[i][j]=min(stTable_min[i][j-1],stTable_min[i+(1<<j-1)][j-1]);  
  45.             stTable_max[i][j]=max(stTable_max[i][j-1],stTable_max[i+(1<<j-1)][j-1]);  
  46.         }  
  47.     }  
  48.     return ;  
  49. }  
  50. int query_sub(int l,int r)  
  51. {  
  52.     int len=r-l+1,k=preLog2[len];  
  53.     return max(stTable_max[l][k],stTable_max[r-(1<<k)+1][k])-min(stTable_min[l][k],stTable_min[r-(1<<k)+1][k]);  
  54. }  
  55. int main()  
  56. {  
  57.     int all = 0;  
  58.     int tot,k;  
  59.     scanf("%d%d",&tot,&k);  
  60.     for(int i=0;i<tot;i++)  
  61.         scanf("%d",&h[i]);  
  62.     st_prepare(tot,h);  
  63.     for(int i=0;i<tot;i++)  
  64.     {  
  65.         int l = i , r = tot;  
  66.         while(r>l+1)  
  67.         {  
  68.             int mid = (l + r) / 2;  
  69.             if(query_sub(i,mid)>k)  
  70.                 r=mid;  
  71.             else l=mid;  
  72.         }  
  73.         if(l-i+1>ans)  
  74.         {  
  75.             ans=l-i+1;  
  76.             times=1;  
  77.             Left[0]=i;  
  78.             Right[0]=l;  
  79.         }  
  80.         else if(l-i+1==ans)  
  81.         {  
  82.             Left[times]=i;  
  83.             Right[times++]=l;  
  84.         }  
  85.     }  
  86.     printf("%d %d\n",ans,times);  
  87.     for(int i=0;i<times;i++)  
  88.         printf("%d %d\n",Left[i]+1,Right[i]+1);  
  89.     return 0;  

CUGBACM Codeforces Tranning 3 题解