ACM培训练习总结 1

昨天上完课六点开的题,做了一天UVa之后困得要死,做培训提出了各种喜闻乐见的错误。。

除了运行错误和内存超限,其他的错误犯了个遍。。

第一题水题一个。。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#define maxn 110
using namespace std;
void print(int i)
{
switch(i)
{
case 1:cout<<"yi";break;
case 2:cout<<"er";break;
case 3:cout<<"san";break;
case 4:cout<<"si";break;
case 5:cout<<"wu";break;
case 6:cout<<"liu";break;
case 7:cout<<"qi";break;
case 8:cout<<"ba";break;
case 9:cout<<"jiu";break;
case 0:cout<<"ling";break;
}
}
int main()
{
char a[maxn]={0};
while(cin>>a)
{
int sum=0,b,c,d;
for(int i=0;i<strlen(a);i++)
sum+=a[i]-'0';
d=sum/100;
b=sum%100/10;
c=sum%10;
if(d)
{
print(d);
cout<<" ";
}
if(d!=0||b!=0)
{
print(b);
cout<<" ";
}
print(c);
cout<<endl;
memset(a,0,sizeof(a));
}
return 0;
}

第二题是求最大连续和的,之前上课学长说还有种比二分扫描更快的方法,只需要一次扫描。一开始没理解对结束位置的取值。后来子序列开头和结尾一直没有找好,错了好几次
。。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#define maxn 5050
using namespace std;
int main()
{
int n,a[maxn],t=1;
cin>>n;
while(n--)
{
int j=0,m,st=0,ed=0,sum=0,sum_max=0;
cin>>m;
for(int i=0;i<m;i++)
{
cin>>a[i];
if(a[i]<=0)
j++;
}
if(j==m)
{
int maxm=0;
for(int i=0;i<m;i++)
if(a[maxm]<a[i])
maxm=i;
cout<<"Case "<<t<<":"<<endl;
cout<<a[maxm]<<" "<<maxm+1<<" "<<maxm+1<<endl;;
t++;
if(n)
cout<<endl;
continue;
}
int k=0;
for(int i=0;i<m;i++)
{
if(sum<0)
k=i;
sum=max(0,sum)+a[i];
if(sum>sum_max)
{
st=k;
ed=i;
}
sum_max=max(sum_max,sum);
}
cout<<"Case "<<t<<":"<<endl;
cout<<sum_max<<" "<<st+1<<" "<<ed+1<<endl;;
t++;
if(n)
cout<<endl;
}
return 0;
}

第三题是求字母算式的,也挺水的,但一开始理解错了题目的意思,以为都是两位数加两位数。。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstring>
#define maxn 10
using namespace std;
char a[maxn][6],b[maxn][6];
int t1,t2,sum;
int exchange(char c[])
{
if(!strcmp(c,"zero"))
return 0;
if(!strcmp(c,"one"))
return 1;
if(!strcmp(c,"two"))
return 2;
if(!strcmp(c,"three"))
return 3;
if(!strcmp(c,"four"))
return 4;
if(!strcmp(c,"five"))
return 5;
if(!strcmp(c,"six"))
return 6;
if(!strcmp(c,"seven"))
return 7;
if(!strcmp(c,"eight"))
return 8;
if(!strcmp(c,"nine"))
return 9;
return 0;
}
int main()
{
while(1)
{
int asum=0,bsum=0;
t1=t2=0;
sum=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<maxn;i++)
{
cin>>a[i];
if(!strcmp(a[i],"+"))
break;
t1++;
}
for(int i=0;i<maxn;i++)
{
cin>>b[i];
if(!strcmp(b[i],"="))
break;
t2++;
}
if(t1==1&&t2==1&&!strcmp(a[0],"zero")&&!strcmp(b[0],"zero"))
return 0;
for(int i=0;i<t1;i++)
{
asum*=10;
asum+=exchange(a[i]);
}
for(int i=0;i<t2;i++)
{
bsum*=10;
bsum+=exchange(b[i]);
}
sum=asum+bsum;
cout<<sum<<endl;
}
return 0;
}

第四题求素数,一开始直接拿学长给的代码用了,换了两种代码,全部TLE。。

后来自己简化求素数流程。只要能不被比自己小的素数整除的数就是素数。。交了一次格式错了。。。

最后改对了。。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int p[500050];
int is_p(int n,int j)
{
int i;
int c=sqrt(n);
for(i=0;i<j&&p[i]<=c;i++) if(n%p[i]==0) return 0;
return 1;
}
int main() {
int m,n;
while(cin>>m>>n)
{
p[0]=2;p[1]=3;p[2]=5;p[3]=7;p[4]=11;
int t=5;
for(int i=12;t<=n;i++)
{
if(is_p(i,t))
{
p[t]=i;
t++;
}
}
t=0;
for(int i=m-1;i<n;i++)
{
cout<<p[i];
t++;
if(t%10==0||i==n-1)
cout<<endl;
else
cout<<" ";
}
cout<<endl;
}
return 0;
}

第五题水题,建个数组就好了,比起UVa其他的题差远了。。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <cstdlib>
#define maxn 35
using namespace std;
int a[maxn][maxn];
int m,n;
int is_biggest(int i,int j)
{
if(i-1>=0&&a[i-1][j]>=a[i][j])
return 0;
if(j-1>=0&&a[i][j-1]>=a[i][j])
return 0;
if(j+1<n&&a[i][j+1]>=a[i][j])
return 0;
if(i+1<m&&a[i+1][j]>=a[i][j])
return 0;
return 1;
}
int main()
{
int first=1;
while(cin>>m>>n)
{
if(first)
first=0;
else
cout<<endl;
memset(a,0,sizeof(a));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
int t=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(is_biggest(i,j))
{
cout<<a[i][j]<<" "<<i+1<<" "<<j+1<<endl;
t=0;
}
}
}
if(t)
cout<<"None "<<m<<" "<<n<<endl;
}
return 0;
}

最后写几句,审题错太可怕。一开始B、C两道题审题错,死活不过,问清楚题目要求之后一次过的。还有求运行效率问题,以后一定要尽量精简代码。

本文迁移自我的 CSDN博客 ,格式可能有所偏差。