程序设计算法竞赛基础——练习1解题报告

1001 最小公倍数

问题描述：

给定两个正整数，计算这两个数的最小公倍数。

输入

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数。

输出

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

样本输入

10 14

样本输出

70

资源

POJ

解题思路

设两个数为x和y，两数最大公因数为T，最小公倍数为P。

P = x * y / T

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

//GYS用于查找最大公约数
int GYS(const int a, const int b) {
    if(a % b != 0) {
        return GYS(b, a % b);
    }
    return b;
}

//GBS查找最大公倍数
int GBS(const int a, const int b) {
    if(a != b)return (a * b) / GYS(a, b);
    else return b;
}

int main () {
    int x, y;
    while(cin >> x >> y) {//输入
        cout << GBS(x, y) << "\n";//输出
    }
    return 0;
}

1002 人见人爱A^B

问题描述

求甲^B的最后三位数表示的整数。

说明：甲^B的含义是”A的乙次方“

输入

输入数据包含多个测试用例，每个实例占一行，由两个正整数A和B组成(1 <= A, B <= 10000) ,如果A=0, B=0,

则表示输入数据的结束，不做处理。

输出

对于每个测试实例，请输出甲^B的最高后三位表示的整数，每个输出占一行。

样本输入

2 3
12 6
6789 10000
0 0

样本输出

8
984
1

作者

LCY

资源

ACM程序设计期末考试(2006/06/07)

解题思路

由于只需要最后三位数，所以只需边计算边对于1000取模即可。

代码实现

#include<iostream>
using namespace std;

int main(){
	int a, b, s;//s保存输入结果
	while((cin >> a >> b) && (a != 0 && b !=0)){
		s = 1;//s初始化为1
		while(b--){
			s = s * a % 1000;//每乘一次a取余一次，避免数据过大
		}
		cout << s << "\n";
	}
	return 0;
}

1003 Rightmost Digit

Problem Description

Given a positive integer N, you should output the most right digit of N^N.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number

of test cases. T test cases follow.

Each test case contains a single positive integer N (1 <= N <= 1,000,000,000).

Output

For each test case, you should output the rightmost digit of N^N.

Sample Input

2
3
4

Sample Output

7
6

Hint

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.

In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

Author

Ignatius.L

解题思路

输出只取N^N的个位数，所以只需找出0~9的N次方的规律即可。

代码实现

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;

//定义一个不定长数组分别存放0~9N次方后的规律
vector<int> a[10];

//CSH()找出0~9的N次方后的规律
void CSH() {
	int j;
	for(int i = 0; i < 10; i++) {
		a[i].push_back(i);
		j = 0;
		while(a[i][j] * i % 10 != a[i][0]) {
			int t = a[i][j] * i % 10;
			a[i].push_back(t);
			j++;
		}
	}
}

int main() {
	CSH();
	int t, n, k;
	cin >> t;
	while(t--){
		cin >> n;
		k = (n - 1)% a[n % 10].size();//k = N % 个位数的循环周期
		cout << a[n % 10][k] << endl;
	}
	return 0;
}

1004 Climbing Worm

Problem Description

An inch worm is at the bottom of a well n inches deep. It has enough to climb u inches every minute,

but then has to rest a minute before climbing again. During the rest, it slips down d inches. The process

of climbing and resting then repeats. How long before the worm climbs out of the well? We’ll always

count a portion of a minute as a whole minute and if the worm just reaches the top of the well at the

end of its climbing, we’ll assume the worm makes it out.

Input

There will be multiple problem instances. Each line will contain 3 positive integers n, u and d. There

give the values mentioned in the paragraph above. Furthermore, you may assume d < u and n < 100.

A value of n = 0 indicates end of output.

Ouput

Each input instance should generate a single integer on a line, indicating the number of minutes it

for the worm to climb out of the well.

Sample Input

10 2 1
20 3 1
0 0 0

Sample Output

17
19

Source

East Central North America 2002

解题思路

利用for循环直到s >= d，输出所用时间h。

代码实现

#include<iostream>
using namespace std;

int main(){
	int n, u, d;
	int s, h;
    //读取数据直到输入为"0 0 0"时退出
	while(cin >> n >> u >> d && n != 0 && u != 0 && d != 0){
		s = 0, h = 0;
        //先向上爬一分钟
		s += u;
		min++;
        //如果已经爬出则跳出循环，未爬出则先下滑1分钟然后向上爬1分钟
		while(h < n){
			s -= d;
			s += u;
            //每次循环需要花费2分钟(下滑+上爬)
			h += 2;
		}
		cout << min << endl;
	}
	return 0;
}

1005 Balloon Comes!

Problem Description

The contest starts now! How excited it is to see balloons floating around. You, one of the best

programmers in HDU, can get a very beautiful balloon if only you have solved very very very … easy

problem.

Give you an operator(+,-,*,/ --denoting addition, subtraction, multiplication, division respectively) and

two positive integers, your task is to output the result.

Is it very easy?

Come on, guy! PLMM will send you a beautiful Balloon right now!

Good Luck!

Input

Input contains multiple test cases. The first line of the input is a single T (0<T<1000) which is the

number of the cases. T test cases follow. Each test case contains a char C (+,-,*,/) and two integers A

and B (0<A, B<10000). Of course, we all know that A and B are operands and C is an operator.

Output

For each case, print the operation result. The result should be rounded to 2 decimal places If and only

if it is not an integer.

Sample Input

4
+ 1 2
- 1 2
* 1 2
/ 1 2

Sample Output

3
-1
2
0.50

Author

Icy

解题思路

本题十分简单，注意数据不要溢出以及输出格式。

当C为”/“时需要判断能否整除。

代码实现

#include<cstdio>
#include<iostream>
using namespace std;

int main(){
	int t, a, b;
	char ch;
	cin >> t;
	while(t--){
		cin >> ch >> a >> b;
		if(ch == '+')printf("%d\n", a + b);
		else if(ch == '-')printf("%d\n", a - b);
        //lld保证数据不会溢出
		else if(ch == '*')printf("%lld\n", a * b);
        //不能整除时输出保留两位小数
		else if(ch == '/' && a % b != 0)printf("%.2f\n", a * 1.0 / b);
		else printf("%d\n", a / b);
	}
	return 0;
}

1006 Fibonacci Again

Problem Description

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = F(n-1) + F(n-2) (n >= 2).

Input

Input consists of a sequence of lines, each containing an integer n.(n < 1,000,000).

Output

Print the word “yes” if 3 divide evenly into F(n).

Print the word “no” if not.

Sample Input

0
1
2
3
4
5

Sample Output

no
no
yes
no
no
no

Author

Leojay

解题思路

既然是判断能否被3整除，那么可以将F(N)对于3取模，然后找出循环周期。

代码实现

#include<iostream>
using namespace std;

int main(){
	int n;
	while(cin >> n){
        //循环周期为8，即“1 2 0 2 2 1 0 1”——f(0)包括在内
		if(n % 8 == 2 || n % 8 == 6)cout << "yes\n";
		else cout << "no\n";
	}
	return 0;
}

1007 Number Sequence

Problem Description

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).

Input

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). There zeros signal signal the end of input and this test case

is not to be processed.

Output

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

Sample Input

1 1 3
1 2 10
0 0 0

Sample Output

2
5

Author

CHEN, Shunbao

Source

ZJCPC2004

解题思路

可将f(n) = (A * f(n-1) + B * f(n-2)) mod 7化为f(n) = ((A mod 7) * f(n-1) + (B mod 7) * f(n-2)) mod 7。

这样可以看出AB输入其实仅仅只有7*7种情况，我们只需预先找出49种情况各自的循环周期即可。

代码实现

#include<vector>
#include<iostream>
using namespace std;

//定义一个不定长的三维数组用于储存49种情况的循环情况
vector<int> s[7][7];

int main() {
	int a, b;
	long long n;
    
    //在输入前先找出49种情况的循环情况
	for(int i = 0; i < 7; i++) {
		for(int j = 0; j < 7; j++) {
			int sum, kase = 2;
			int f1 = 1, f2 = 1;
			f1 = (f2 * i + f1 * j) % 7;
			f2 = (f1 * i + f2 * j) % 7;
			s[i][j].push_back(f1);
			s[i][j].push_back(f2);
			do {
				sum = (s[i][j][kase - 1] * i + s[i][j][kase - 2] * j) % 7;
				s[i][j].push_back(sum);
				kase = s[i][j].size();
			} while(s[i][j][kase - 2] != s[i][j][0] || s[i][j][kase -1] != s[i][j][1]);
			s[i][j].pop_back();
			s[i][j].pop_back();
		}
	}
    
    //读入输入直到"0 0 0"为止
	while(cin >> a >> b >> n && a != 0 && b != 0 && n != 0) {
		if(n <= 2){
			cout << 1 << endl;
			continue;
		}
        //对AB分别进行 mod 7 处理
		a = a % 7;
		b = b % 7;
		n = (n - 3) % s[a][b].size();
		cout << s[a][b][n] << endl;
	}
	return 0;
}

1008 sort

Problem Description

给你n个整数，请按从大到小的顺序输出其中前m大的数。

Input

每组测试数据有两行，第一行有两个数n，m(0 < n, m < 1000000)，第二行包含n个各不相同，且都处于区间[-500000, 500000]的整数。

Sample Input

5 3
3 -35 92 213 -644

Sample Output

213 92 3

Author

LL

Source

ACM暑假集训队练习赛(三)

解题思路

输出n个数中最大的m个数，可以通过多种方法实现，但是由于数据量比较多，使用cin或cout可能导致超时。

下面以堆排序为例。

代码实现

#include<cstdio>

const int maxn = 1000005;
int a[maxn];
//将m定义为全局变量可表示还需要输出多少数，heapsize用于存储每次输出后剩下数的数量
int heapsize, m;

//用于交换位置
void exchange(const int x, const int y){
	int temp = a[x];
	a[x] = a[y];
	a[y] = temp;
}

//将数组中i~heapsize间的数据进行从大到小的堆排序
void heap_max(const int i) {
	int left = i * 2;
	int right = left + 1;
	int max2;
	if(left <= heapsize && a[left] > a[i]) max2= left;
	else max2 = i;
	if(right <= heapsize && a[max2] < a[right])max2 = right;
	if(max2 != i) {
		exchange(i, max2);
		heap_max(max2);
	}
}

int main() {
	int n;
    
	while((scanf("%d %d", &n, &m) != EOF)) {
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
        //将heapsize初始化为n
		heapsize = n;
        
        //将整个数组进行堆排序
		for(int i = n / 2; i >= 1; i--) {
			heap_max(i);
		}
        
        //先输出最大数并m--
		printf("%d", a[1]);
		m--;
        
        //重新排序再输出下一个最大数，直到m为0时停止
		while(m){
			for(int i = n; i >= 2; i--){
				heapsize--;
				exchange(i, 1);
				heap_max(1);
				printf(" %d", a[1]);
				m--;
				if(m == 0)break;
			}
		}
		printf("\n");
	}
	return 0;
}

1009 吃糖果

Problem Descriptiong

HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样

糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使

得他能把所有糖果都吃完？请你写个程序帮忙计算一下。

Input

第一行有一个整数T，接下来T组数据，每组数据占2行，第一行是一个整数N(0 < N < 1000000)，第二行是N

个数，表示N种糖果的数目Mi(0 < MI < 1000000)。

Output

对于每组数据，输出一行，包含一个“Yes”或者“No”。

Sample Input

2
3
4 1 1
5
5 4 3 2 1

Sample Output

No
Yes

Author

Gardon

Source

Gardon-DYGG Contest 2

解题思路

设糖的总数为sum，最多的那种糖有max颗，则只需判断是否满足 max * 2 <= sum + 1即可

代码实现

#include<iostream>
using namespace std;

int main(){
	long long t;
	cin >> t;
	while(t--){
        //sum设为long long可以防止数据过大
		long long max = 0, sum = 0;
		long long n;
		cin >> n;
		while(n--){
			long long a;
			cin >> a;
			if(a > max) max = a;
			sum += a;
		}
        //如果max > (sum + 1) / 2即不满足max * 2 <= sum + 1
		if(max > (sum + 1) / 2)cout << "No\n";
		else cout << "Yes\n";
	}
	return 0;
}

1010 Sum Problem

Problem Description

Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).

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

Input

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

Output

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.

Sample Input

1
100

Sample Output

1

5050

Author

DOOM III

解题思路

本题实现方法多种多样，可以使用数组预处理，也可以用sum = n * (n + 1) / 2，也可以直接for循环

虽然直接for循环傻瓜式求解是最差选择，但代码实现还是采用了这种方法。

代码实现

#include<iostream>
using namespace std;

int main(){
	int n;
	while(cin >> n){
		int sum = 0;
		for(int i = 1; i <= n; i++)sum += i;
		cout << sum << endl << endl;
	}
	return 0;
}

1011 Elevator

Problem Description

The highest building in our city has only one elevator. A request list is made up with N positive

numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6

seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator

will stay for 5 seconds at each stop.

Input

There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers.

All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test

case is not to be processed.

Output

Print the total time on a single line for each test case.

Sample Input

1 2
3 2 3 1
0

Sample Output

17
41

Author

ZHENG, Jianqiang

Source

ZJCPC2004

解题思路

定义一个sum用于存储时间，tp表示电梯所在位置，temp表示要前往楼层

只需注意电梯在每次停下后会停5s

代码实现

#include<iostream>
using namespace std;

int main() {
	int n;
	while(cin >> n && n != 0) {
		int temp, sum = 0, tp = 0;
		while(n--) {
			cin >> temp;
			if(temp > tp) {
				sum += (temp-tp) * 6 + 5;
				tp = temp;
			} else if (temp < tp) {
				sum += (tp - temp) * 4 + 5;
				tp = temp;
			} else sum += 5;
		}
		cout << sum << endl;
	}
	return 0;
}

1012 七夕节

Problem Description

七夕节那天，月老来到数字王国，他在城门上贴了一张告示，并且和数字王国的人们说：“你们想知道你们的

另一半是谁吗？那就按照告示上的方法去找吧！”

人们纷纷来到告示前，都想知道谁才是自己的另一半。告示如下：

数字N的因子就是所有比N小又能被N整除的所有正整数，如12的因子有1，2，3，4，6.

你想知道你的另一半吗？

Input

输入数据的第一行是一个数字T(1 <= T <= 500000)，它表明测试数据的组数.然后是T组测试数据,每组测试数

据只有一个数字N(1 <= N <= 500000).

Output

对于每组测试数据,请输出一个代表输入数据N的另一半的编号.

Sample Input

3
2
10
20

Sample Output

1
8
22

Author

Ignatius.L

Source

杭电ACM省赛集训队选拔赛之热身赛

解题思路

该题不难理解,只需注意优化以免超时即可.

代码实现

#include<iostream>
#include<cmath>
using namespace std;

//数组a[n]用于存放n除1外所有因子和,long long以免溢出
const long long maxn = 500001;
long long a[maxn];

int main(){
	long long t;
    //首先进行预处理
	for(long long i = 2; i < sqrt(maxn); i++){
		a[i * i] += i;
		long long kase = i + 1;
		while(i * kase < maxn){
			long long sum = i * kase;
			a[sum] += i + kase;
			kase ++;
		}
	}
    
    //进行多组数据测试
	cin >> t;
	while(t--){
		long long n;
		cin >> n;
        //因为a[n]不包含因子1,所以输出时要加回去
		cout << a[n] + 1 << endl;
	}
	return 0;
}