1000:A+B Problem

题目描述:

Calculate A + B.

输入:

Each line will contain two integers A and B. Process to end of file.

输出:

For each case, output A + B in one line.

在一行中输入A和B的值,然后输出A+B的值

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main()
{
int a, b;
while(cin >> a >> b) //这里不能用while(1),会超时
cout << a + b << endl;
}

1001:Sum Problem

题目描述:

In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + … + n.

输入:

The input will consist of a series of integers n, one integer per line.

输出:

For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.

这道题有两个坑,第一个是one line, followed by a blank line,输出结果后要空一行,所以要输出两个换行

第二个坑就是You may assume the result will be in the range of 32-bit signed integer,你需要保证你的答案在int范围内

int的范围是[-2^31, 2^31 - 1]

这里有人看到题目就想起了等差数列求和公式n*(n+1)/2

但是在c++中,如果变量为int型,那么计算结果也为int型,如果计算结果中最大的一步大于了2^32 - 1的话,就会造成溢出
所以我们先求一下如果我们用等差数列求和来做,可以输入的n的最大值
用python脚本来求这个值:

1
2
3
4
5
6
7
n = 0
while 1:
if (n*(n+1) <= (2**31-1)):
n += 1
else:
break
print n-1

得到

1
46340

n超过这个值就会造成溢出,我们可以用如下c++代码来验证

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
cout << n * (n + 1) / 2 << endl << endl;
}
}


从运行结果我们可以看到,当我们输入46340的时候输出了46340*(46340+1)/2的正确结果

而当输入46341的时候,发生了溢出,结果变成了一个负数
该负数的值等于n*(n+1)/2 - 2^31的结果再取负得到的

1
-1073716337 = 46341*(46341+1)/2 - 2^31

而如果我们用传统的累加法n可以取到多少呢,python脚本如下:

1
2
3
4
5
6
7
8
n = 0
i = 0
while 1:
i += 1
n += i
if (n > (2**31-1)):
break
print i-1

结果:

1
65535

可以一直取到数字65535,所以如果我们用等差求和的时候,取值范围在(46340, 65535]区间的时候都会出错

最终我的通关脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int main()
{
int n;
int i;
while (cin >> n)
{
if (n <= 46340)
{
cout << n * (n + 1) / 2 << endl << endl;
}
else
{
int result = 0;
for (i = 0;i <= n;i++)
{
result += i;
}
cout << result << endl << endl;
}
}
}

当然也可以直接使用累加法通关

1002:A + B Problem II

题目描述:

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

输入:

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

输出:

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line is the an equation “A + B = Sum”, Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

很明显是考大整数相加
一般大整数相加我们都是采用字符串的形式,然后逐位相加取余进位。那么我们先写出一个大整数相加的函数,其他的就很简单了。
代码如下:

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<string>
using namespace std;
string add(string a, string b);
int main()
{
int T;
cin >> T;
string res[20];
string a_[20];
string b_[20];
string a, b;
for (int i=0;i<T;i++)
{
cin >> a >> b;
a_[i] = a;
b_[i] = b;
res[i] = add(a, b);
}
for (int i=0;i<T;i++)
{
cout << "Case " << i + 1 << ":" << endl;
cout << a_[i] << " + " << b_[i] << " = " << res[i];
if (i != T - 1)
{
cout << endl << endl;
}
else
{
cout << endl;
}
}
}
string add(string num_1, string num_2)
{
int len_num_1, len_num_2;
if (num_1.size() < num_2.size())
{
string temp;
temp = num_1;
num_1 = num_2;
num_2 = temp;
}// 确保了num_1是比较长的那个数
len_num_1 = num_1.size();
len_num_2 = num_2.size();
int flag = 0; // 进位值
while (len_num_1--)
{
int a = num_1[len_num_1] - '0';// 通过减字符0来将字符转为数字
int b;
if (len_num_2 > 0)
{
b = num_2[len_num_2 - 1] - '0';
len_num_2--;
}
else
{
b = 0;
}
int s = a + b + flag;
num_1[len_num_1] = s % 10 + '0';// 通过加字符0将数字转换成字符串
flag = s / 10;
}
string result = num_1;
if (flag == 1)
{
result = "1" + num_1;
}
return result;
}

1003:Max Sum

题目描述:

Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

输入:

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

输出:

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

很明显这道题主要考最大子序列的算法,注意要考虑序列全为负数的情况
参考文章:https://blog.csdn.net/zzl913657644/article/details/52431011

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>
using namespace std;
int main()
{
int T;
int N;
int n[100000];
int sum[20];
int left[20];
int right[20];
cin >> T;
for (int i = 0;i < T;i++)
{
cin >> N; // 该序列元素个数
for (int j = 1;j <= N;j++)// 位置从1开始
{
cin >> n[j];
}

// 先判断是否为全负数
sum[i] = n[1];
left[i] = 1;
right[i] = 1;
for (int j = 2;j <= N;j++)
{
if (n[j] > sum[i])
{
sum[i] = n[j];
left[i] = j;
}
}
if (sum[i] < 0) // 此时sum[i]为序列中最大的元素
{
right[i] = left[i];
}
else
{
int s = 0;
int templeft=1; // 临时存储下一个序列开始,如果下一个序列大于前一个最大序列,就将值赋给left[i]
left[i] = 1;
right[i] = 1;
for (int j = 1;j <= N;j++) // 最优起点法找最大子序列
{
s += n[j];
if (s >= sum[i]) // 前面sum[i]不置0,可能会出现最大序列等于最大的一个元素的情况
{
sum[i] = s;
right[i] = j;
left[i] = templeft;
}
else if (s < 0)
{
templeft = j + 1;
s = 0;
}
}
}

//
}
for (int i = 0;i < T;i++)
{
cout << "Case " << i + 1 << ":" << endl;
cout << sum[i] << " " << left[i] << " " << right[i] << endl;
if (i != T - 1)
{
cout << endl;
}
}
}

1004:Let the Balloon Rise

题目描述:

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges’ favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.
This year, they decide to leave this lovely job to you.

输入:

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) – the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.
A test case with N = 0 terminates the input and this test case is not to be processed.

输出:

For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.

这道题考的就是一个找字符串数组中找出现最多的字符串的问题

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
#include<iostream>
#include<string>
using namespace std;

int main()
{
int N;
int i = 0;
int j = 0;
int max;
int pos;
int n = 0;
int count[1000];
string result[1000];
string arr[1000];

while (cin >> N && N!=0)
{
max = 0;
pos = 0;
for (i = 0;i < N;i++)
{
cin >> arr[i];
}

// 找出出现次数最多的字符串
for (i = 0;i < N;i++)
{
count[i] = 0;
for (j = i;j < N;j++)
{
if (arr[i].compare(arr[j])==0)// string对象用compare方法来比较
{
count[i]++;
}
}
if (max < count[i])
{
max = count[i];
pos = i;
}
}
result[n] = arr[pos];
n++;
}

for (i = 0;i < n;i++)
{
cout << result[i] << endl;
}
}

1005:Number Sequence

问题描述:

A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).

输入:

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

输出:

For each test case, print the value of f(n) on a single line.

示例输入:

1
2
3
1 1 3
1 2 10
0 0 0

示例输出:

1
2
2
5

看到这个式子f(n) = (A f(n - 1) + B f(n - 2)) mod 7 ,刚开始采用的递归

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
#include<iostream>
using namespace std;
int f(int a, int b, int n);
int result[1000];
int main()
{
int i = 0;
int a, b, n;
while (cin >> a >> b >> n)
{
if (a==0 && b==0 && n==0)
{
break;
}
result[i] = f(a, b, n);
i++;
}
for (int j = 0;j < i;j++)
{
cout << result[j] << endl;
}

}
int f(int a, int b, int n)
{
if (n == 1 || n==2)
{
return 1;
}
return (a*f(a, b, n-1) + b * f(a, b, n-2)) % 7;
}

提交上去后内存占用太大没有通过,因此这里不能直接用递归,得换一种方法。
网上看了一下别人得解答,知道了这道题是用最大周期来解决
f(n-1)和f(n-2) 在模7之后的值都只有7种情况,那么f(n-1)和f(n-2)的组合一共有49种,那么49就为其最大循环周期,当然其周期可能为49的因数,这并不影响我们的计算结果。
那么我们用 n mod 49 之后的值再来调用递归算法岂不是就能降低很多开销了,最终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
#include<iostream>
using namespace std;
int f(int a, int b, int n);
int result[1000];
int main()
{
int i = 0;
int a, b, n;
while (cin >> a >> b >> n)
{
if (a==0 && b==0 && n==0)
{
break;
}
else if (n > 49) // 通过最大周期降低开销
{
n = n % 49;
}
result[i] = f(a, b, n);
i++;
}
for (int j = 0;j < i;j++)
{
cout << result[j] << endl;
}
}
int f(int a, int b, int n)
{
if (n == 1 || n==2)
{
return 1;
}
return (a*f(a, b, n-1) + b * f(a, b, n-2)) % 7;
}

1006:Tick and Tick

问题描述:

The three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.

输入:

The input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.

输出:

For each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.

示例输入:

1
2
3
4
0
120
90
-1

示例输出:

1
2
3
100.000
0.000
6.251

刚开始我是以一秒为梯度来求的,结果精度不够,和标准答案差了一点点,代码如下:

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
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cmath>
#include<iomanip>
double result[1000];
using namespace std;
int tangle(double D);
int main()
{
double D;
int i = 0;
while (cin >> D)
{
if (D == -1)
{
break;
}
double temp = (tangle(D)*1.0)/43200*100;
result[i] = temp;
i++;
}
for (int j = 0;j < i;j++)
{
cout << fixed << setprecision(3) << result[j] << endl;
}
cin >> i;
}
// 24*60*60 = 86400秒
// 计算一天只用计算12小时,前12小时和后12小时情况相同 12*60*60 = 43200
// 6°
int tangle(double D)// D为必须大于的角度
{
double a=0;// 时针
double b=0;// 分针
double c=0;// 秒针
int num = 0;
for (int i = 1;i <= 43200;i++)
{
// 时针一小时转30°,每分钟转0.5°,每秒钟转0.5/60°
a = a + 0.5/60;

// 分针一秒钟转0.1°
b = b + 0.1;
if (b >= 360)
{
b = b - 360;
}

// 秒针一秒钟转6°
c = (i * 6) % 360;

double temp1 = fabs(a - b);
double temp2 = fabs(a - c);
double temp3 = fabs(b - c);
double min = temp1;
double max = temp1;
if (temp2 < min)
{
min = temp2;
}
if (temp2 > max)
{
max = temp2;
}
if (temp3 < min)
{
min = temp3;
}
if (temp3 > max)
{
max = temp3;
}

if (min >= D && max <= 360-D)
{
num++;
}
}
return num;
}

然后改良了一下,将一天时间划分为280000份,精度上去了,运行时间又超了

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cmath>
#include<iomanip>
double result[1000];
using namespace std;
int tangle(double D);
int main()
{
double D;
int i = 0;
while (cin >> D)
{
if (D == -1)
{
break;
}
double temp = (tangle(D)*1.0) / 280000 * 100;
result[i] = temp;
i++;
}
for (int j = 0;j < i;j++)
{
cout << fixed << setprecision(3) << result[j] << endl;
}
}

int tangle(double D)// D为必须大于的角度
{
double a = 0;// 时针
double b = 0;// 分针
double c = 0;// 秒针
int num = 0;
for (int i = 1;i <= 280000;i++)
{
// 360/100000
a = a + (360 * 1.0 / 280000);
if (a > 360)
{
a = a - 360;
}
//cout << a << endl;

// 360*12/100000
b = b + (360 * 12 * 1.0 / 280000);
if (b > 360)
{
b = b - 360;
}
//cout << b << endl;

// 360*12*60/100000
c = c + (360 * 12 * 60 * 1.0 / 280000);
if (c > 360)
{
c = c - 360;
}
//cout << c << endl;

double temp1 = fabs(a - b);
double temp2 = fabs(a - c);
double temp3 = fabs(b - c);
double min = temp1;
double max = temp1;
if (temp2 < min)
{
min = temp2;
}
if (temp2 > max)
{
max = temp2;
}
if (temp3 < min)
{
min = temp3;
}
if (temp3 > max)
{
max = temp3;
}

if (min >= D && max <= 360 - D)
{
num++;
}
}
return num;
}

那么

最后更新: 2018年09月04日 20:11

原始链接: http://drac0nids.top/2018/08/26/杭电acm训练平台刷题/

× 请我吃糖~
打赏二维码