本文详细解析了ZUST程序设计算法竞赛的基础题目，包括最小公倍数、A^B的最后三位数、数的最右位数字、爬虫虫、气球问题、斐波那契数列等。通过解题思路和代码展示，帮助读者理解和解决这些问题。
ZUST 程序设计算法竞赛基础【1】
1001 最小公倍数
题目：
Problem Description
给定两个正整数，计算这两个数的最小公倍数。
Input
输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.
Output
对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。
Sample Input
10 14
Sample Output
70
添加链接描述
解题思路：不用for循环一个个乘下去，可能会溢出，
改用*a，b的最小公倍数=a/（a，b的最大公约数）b
代码：
#include<stdio.h>
int main()
{
int a,b,c,i,j;
while(scanf("%d%d",&a,&b)!=EOF)
{
for(i=1;i<=a;i++)
{
if(a%i==0&&b%i==0)
{
j=i;
}
}
c=a/j*b;
printf("%d\n",c);
}
return 0;
}
1002 人见人爱A^B
题目：
Problem Description
求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”
Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。
Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。
Sample Input
2 3
12 6
6789 10000
0 0
Sample Output
8
984
1
添加链接描述
解题思路：可先去a的后几位（如a%100），再用for循环依次是后几位相乘。
代码：
#include<stdio.h>
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a==0&&b==0)
{
break;
}
int c,i;
c=a%1000;
a=1;
for(i=1;i<=b;i++)
{
a=a%1000;
a=a*c;
}
printf("%d\n",a%1000);
}
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.
解题思路：方法一 利用快速幂，模板如下：
Int ans=1;
a=a%c;
while(b>0)
{
if(b%2==1)
{
ans=(ans*a)%c;
}
b=b/2;
a=(a*a)%c;
}
return ans;
方法二 找规律，会发现2,22,42的结果相同，说明每20为一个周期。
代码：
1.快速幂：
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[n],i,t,j,x;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
t=a[i];
x=1;
a[i]=a[i]%10;
while(t>0)
{
if(t%2==1)
{
x=(x*a[i])%10;
}
t=t/2;
a[i]=(a[i]*a[i])%10;
}
printf("%d\n",x);
}
return 0;
}
2.找规律
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,a,i,j,ans,b;
long long int sum=1;//防止sum溢出
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a);
b=a%20;
if(b==0)
b=10;
ans=1;
for(j=0;j<b;j++)
{
sum=ans*b;
ans=sum%10;
}
printf("%d\n",ans);
}
return 0;
}
1004 Climbing Worm
题目：
Problem Description
An inch worm is at the bottom of a well n inches deep. It has enough energy 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. These 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.
Output
Each input instance should generate a single integer on a line, indicating the number of minutes it takes for the worm to climb out of the well.
Sample Input
10 2 1
20 3 1
0 0 0
Sample Output
17
19
解题思路：纯数学计算，可分布累加时间，用for循环。
代码：
#include<stdio.h>
int main()
{
int n,u,d;
while(scanf("%d%d%d",&n,&u,&d)!=EOF)
{
if(n==0&&u==0&&d==0)
{
break;
}
int x,i;
x=0;
for(i=1;i<10000;i++)
{
x=x+u;//向上爬的路程
if(x>=n)
{
printf("%d\n",i);
break;//判断是否爬出井
}
i=i+1;//若没有爬出，则休息一分钟
x=x-d;//休息时下滑
}
}
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 the 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 integer T (0<T<1000) which is the number of test 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
解题思路：分情况讨论，符号用字符串存储是只去第一个字符；用字符存储时，记得在scanf之前去掉多余的回车。（getchar（）；）。
代码：
#include<stdio.h>
#include<math.h>
int main()
{
int N,a,b;
char ch,s[2];
scanf("%d",&N);
while(N--)
{
scanf("%s%d%d",s,&a,&b);//scanf函数遇到空格结束
ch=s[0];
if(ch=='+')
printf("%d\n",a+b);
else if(ch=='-')
printf("%d\n",a-b);
else if(ch=='*')
printf("%d\n",a*b);
else
if(a%b==0)
printf("%d\n",a/b);
else
printf("%.2f\n",(double)a/b);//除法情况要四舍五入，double自动四舍五入
}
return 0;
}
1006 Fibonacci Again
题目：
Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = 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
解题思路：找规律，发现如果n除以4的余数为2，那么其函数值%3=0，为yes，
否则为no。
代码：
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
if(n%4==2)
printf("yes\n");
else
printf("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). Three zeros 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
解题思路：一．为使数据不会溢出，可采用Amod7f（n-1）+Bmod7f（n-2），但是这样还是会超时。
二． f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.从该式可以得出，f（n）始终不会大于7.而每个f(n)均是由这个递推公式而得来，所以f(n)=f(n mod (7*7))。—>找规律，没49位一周期。
代码：
#include<stdio.h>
int main()
{
int a,b,n;
while(scanf("%d%d%d",&a,&b,&n)!=EOF)
{
if(a==0&&b==0&&n==0)
{
break;
}
int f[50],i;
f[1]=1;
f[2]=1;
for(i=3;i<=49;i++)
{
f[i]=(a*f[i-1]+b*f[i-2])%7;
}
if(n%49==0)
{
printf("%d\n",f[49]);
}
else
{
printf("%d\n",f[n%49]);//49的倍数单独拿出来，不然余数为0，而f[0]并不知道
}
}
return 0;
}
1008 sort
题目：
Problem Description
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3
3 -35 92 213 -644
Sample Output
213 92 3
Hint
Hint
请用VC/VC++提交
解题思路：利用哈希算法查找，将一组数据放入数组中并标记，在按大小顺序找出。
代码：
GNU C（方便理解哈希算法，题目要求VC/VC++）
#include<stdio.h>
int h[1000001] = {0};//初始化数组，使其值都为0；
int main()
{
int n,m,i,t;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d",&t);
h[t+500000]=1;//放入数组下标，标记
}
for(i=500000;i>=-500000;i--)
{
if(h[i+500000]==1)//直接设i，从大到小查找
{
printf("%d ",i);
m--;//输出m个数
}
if(m==0)
{
break;
}
}
printf("\n");
return 0;
}
Visual C++
#include <iostream>
#define MAXNUM 500000
int a[1000000];
using namespace std;
int main(int argc, char *argv[])
{
int n,n1,tmp=2*MAXNUM;
while(scanf("%d%d",&n,&n1)!=EOF){
for(int i=0;i<=tmp;i++){
a[i]=0;
}
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
a[x+MAXNUM]=1;
}
for(int i=500000;i>=-500000;i--){
if(a[i+MAXNUM]==1){
cout<<i;
n1--;
if(n1!=0) printf(" ");
else{
cout<<endl;
break;
}
}
}
}
return 0;
}
1009 吃糖果
题目：
Problem Description
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
Hint
Hint
Please use function scanf
解题思路：根据抽屉原理，数量最多的糖果数小于等于剩余糖果数+1就是Yes，否则是No。为防止数据溢出，求和变量要是long long类型。
代码：
#include <stdio.h>
int main()
{
int t, n, mi, max, i;
long long sum;//防止数据溢出，否则会WA
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
sum = 0;
max = 0;
for(i=1; i<=n; i++)
{
scanf("%d", &mi);
sum += mi;
max = (mi > max) ? mi : max;
}
printf("%s\n", (max > sum - max + 1) ? "No" : "Yes");
}
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
解题思路：简单的累加。
代码：
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int sum,i;
sum=0;
for(i=1;i<=n;i++)
{
sum=sum+i;
}
printf("%d\n\n",sum);//记得空一格
}
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.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.
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
解题思路：简单的数学问题，没相邻两数进行比较，后一个大，就上升，否则下降。
代码：
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n!=0)
{
int i,N[n+1],t;
N[0]=0;//开始时在第0层
for(i=1;i<=n;i++)
{
scanf("%d",&N[i]);
}
t=0;
for(i=1;i<=n;i++)
{
if(N[i]>N[i-1]) t=t+(N[i]-N[i-1])*6;
else if(N[i]<N[i-1]) t=t+(N[i-1]-N[i])*4;
}
t=t+n*5;//每一站停留5秒
printf("%d\n",t);
}
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
解题思路：折半简化寻找。如寻找20的因子，先算20的平方根，找打平方根左边的，就可找到右边的。
代码：
#include<stdio.h>
#include<math.h>
int main()
{
int n,a,i,t,q;
scanf("%d",&n);
while(n--)
{
scanf("%d",&a);
t=0;
q=sqrt(a);
for(i=2;i<=q;i++)
{
if(a%i==0) t=t+i+(a/i);
}
if(q*q==a) t=t-q;
printf("%d\n",t+1);
}
return 0;
}
扫一扫
909
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
