首页 > 代码库 > CUGBACM Codeforces Tranning 3 题解
CUGBACM Codeforces Tranning 3 题解
描述:第三场CF训练了,这次做的挺搞笑的,我记得这是内天持续训练九个小时中的最后两个小时,想想也是蛮拼的。
题解:
A. 题意:给四个边,如果能组成判断能不能从其中找三条边组成三角形,不就再判断能不能三条边首尾相接组成一个线段。
思路:三角形判断条件,两条边之和大于第三条边,两边之和等于第三条边就是线段。
代码:
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <ctype.h>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #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 <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <ctype.h>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #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<tot;i++)
- {
- scanf("%d",&aa[i]);
- }
- for(int i=1;i<tot;i++)
- l[i]=l[i-1]+aa[i-1];
- r[tot-1]=0;
- for(int i=tot-2;i>=0;i--)
- r[i]=r[i+1]+aa[i+1];
- int Alice = 0,Bob = 0;
- for(int i=0;i<tot;i++)
- {
- if(l[i]<=r[i])
- Alice++;
- else Bob++;
- }
- cout<<Alice<<" "<<Bob<<endl;
- }
C. 题意:给一个n*m的图,里面用大写字母表示桌子,找到和给出的字母相邻的字母的种类数之和。
思路:对于每个存在的字母找一下上,下,左,右即可。
代码:
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <ctype.h>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #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<row;i++)
- scanf("%s",ss[i]);
- for(int i=0;i<row;i++)
- {
- for(int j=0;j<col;j++)
- {
- if(ss[i][j]==cap[0])
- {
- if(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<row)
- if(ss[i+1][j]!=cap[0]&&ss[i+1][j]>=‘A‘)
- vis[ss[i+1][j]-‘A‘]=1;
- if(j<col)
- if(ss[i][j+1]!=cap[0]&&ss[i][j+1]>=‘A‘)
- vis[ss[i][j+1]-‘A‘]=1;
- }
- }
- }
- int ans = 0;
- for(int i=0;i<26;i++)
- if(vis[i])
- ans++;
- printf("%d\n",ans);
- return 0;
- }
D.Longest Regular Bracket Sequence
题意:给一个长的字符串,其中都是"("和")",问最长的合理括号匹配子串是多长,并且找出该长度的子串有多少个。
思路:比赛的时候,了。是写DP搞了好久都搞不出来,加上脑子糊里糊涂的,就GG了。思路是这样的,对于每个")",如果它左边的是合理的匹配,并且找到 它左边的合理匹配的第一个"("的左端也是"(",那么它的匹配数是左边的匹配数+2,即dp[i]=dp[i-1]+2,并且如果找到的合理匹配的左端 还存在合理匹配,那么它的合理匹配长度还要加上前面合理匹配的长度。
代码:
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <ctype.h>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #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]!=‘\0‘; 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\n",ans,time);
- }
E.Exposition
题意:给出N本书,n<=10^5,这n本书按出版时间给出的,给出了每本书的高度hi。并且给出一个k,k<=10^6,要求在n本书选择其中连续的若干本书,其中最高的高度比最高的高度不能大于k,问最多可以选择多少本书。
思路:二分+RMQ。从左至右依次选择每本书作为起点,二分来选择符合条件的终点来保证以该本书为起点的长度最长,对于每次的终点,找到起点终点之间的最高高度和最低高度,如果符合条件,那么终点右移,否则终点左移。查询最高高度和最低高度的方式是ST表,O(NlogN)的预处理,然后O(1)的查询,二分的过程中的复杂度也是O(NlogN)。
代码:
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <ctype.h>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <vector>
- #define eps 1e-8
- #define INF 0x7fffffff
- #define maxn 100005
- #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 stTable_min[maxn][32],stTable_max[maxn][32];
- int preLog2[maxn];
- int h[maxn];
- int Left[maxn],Right[maxn];
- int ans = 0,times = 0;
- void st_prepare(int n,int *array)
- {
- preLog2[1]=0;
- for(int i=2; i<=n; i++)
- {
- preLog2[i]=preLog2[i-1];
- if((1<<preLog2[i]+1)==i)
- preLog2[i]++;
- }
- for(int i=n-1; i>=0; i--)
- {
- stTable_min[i][0]=array[i];
- stTable_max[i][0]=array[i];
- for(int j=1; (i+(1<<j)-1)<n; j++)
- {
- stTable_min[i][j]=min(stTable_min[i][j-1],stTable_min[i+(1<<j-1)][j-1]);
- stTable_max[i][j]=max(stTable_max[i][j-1],stTable_max[i+(1<<j-1)][j-1]);
- }
- }
- return ;
- }
- int query_sub(int l,int r)
- {
- int len=r-l+1,k=preLog2[len];
- 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]);
- }
- int main()
- {
- int all = 0;
- int tot,k;
- scanf("%d%d",&tot,&k);
- for(int i=0;i<tot;i++)
- scanf("%d",&h[i]);
- st_prepare(tot,h);
- for(int i=0;i<tot;i++)
- {
- int l = i , r = tot;
- while(r>l+1)
- {
- int mid = (l + r) / 2;
- if(query_sub(i,mid)>k)
- r=mid;
- else l=mid;
- }
- if(l-i+1>ans)
- {
- ans=l-i+1;
- times=1;
- Left[0]=i;
- Right[0]=l;
- }
- else if(l-i+1==ans)
- {
- Left[times]=i;
- Right[times++]=l;
- }
- }
- printf("%d %d\n",ans,times);
- for(int i=0;i<times;i++)
- printf("%d %d\n",Left[i]+1,Right[i]+1);
- return 0;
- }
CUGBACM Codeforces Tranning 3 题解