概述
链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62515#overview
描述:第三场CF训练了,这次做的挺搞笑的,我记得这是内天持续训练九个小时中的最后两个小时,想想也是蛮拼的。
题解:
A.Triangle
题意:给四个边,如果能组成判断能不能从其中找三条边组成三角形,不就再判断能不能三条边首尾相接组成一个线段。
思路:三角形判断条件,两条边之和大于第三条边,两边之和等于第三条边就是线段。
代码:
#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.
President's Office
题意:给一个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("%dn",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]!='