ZUST- 程序设计算法竞赛基础【1】题解报告
3.6 题解报告
1001 最小公倍数
题目
Problem Description
给定两个正整数，计算这两个数的最小公倍数。
Input
输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.
Output
对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。
Sample Input
10 14
Sample Output
70
题解
求最小公倍数算法：
最小公倍数=两整数的乘积÷最大公约数
求最大公约数算法：
1.辗转相除法
有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
2.相减法
有两整数a和b：
① 若a>b，则a=a-b
② 若a<b，则b=b-a
③ 若a=b，则a（或b）即为两数的最大公约数
④ 若a≠b，则再回去执行①
3.穷举法
有两整数a和b：
① i=1
② 若a，b能同时被i整除，则t＝i
③ i++
④ 若 i <= a(或b)，则再回去执行②
⑤ 若 i > a(或b)，则t即为最大公约数，结束
改进：
① i= a(或b)
② 若a，b能同时被i整除，则i即为最大公约数，
结束
③ i--，再回去执行②
有两整数a和b：
① i=1
② 若a，b能同时被i整除，则t＝i
③ i++
④ 若 i <= a(或b)，则再回去执行②
⑤ 若 i > a(或b)，则t即为最大公约数，结束
改进：
① i= a(或b)
② 若a，b能同时被i整除，则i即为最大公约数，
结束
③ i--，再回去执行②
---------------------
作者：iwm_next
来源：****
原文：https://blog.****.net/iwm_next/article/details/7450424
代码
#include<stdio.h>
int main()
{
int n1,n2,i,j,temp=0;
while(scanf("%d %d",&n1,&n2)!=EOF)
{
i=n1>n2?n1:n2;
j=n1<n2?n1:n2;
do{
temp=j;
j=i%j;
i=temp;
} while(j!=0);
printf("%d\n",n1/i*n2);
}
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的位数
代码
#include<stdio.h>
int main(){
int a,b,i,sum=1;
while(scanf("%d %d",&a,&b)!=EOF){
sum=1;
if(a!=0&&b!=0){
a=a%100;
for(i=0;i<b;i++)sum=a*sum%1000;
printf("%d\n",sum);
}
}
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.
题解
这道题与第二题相似，由于在最后一位也可以直接找规律，快速幂求模
以下是快速幂的原理介绍：
详细的可以点击下面链接
https://blog.****.net/lsgqjh/article/details/45076513
代码
#include<stdio.h>
long long mode(long long a, long long b, long long c)
{
long long sum = 1;
a = a % c;
while (b > 0)
{
if (b % 2 == 1)
sum = (sum * a) % c;
b /= 2;
a = (a * a) % c;
}
return sum;
}
int main()
{
int t;long long x,n;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
x=mode(n,n,10);
printf("%d\n",x);
}
}
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
题解
这道题就是小学奥数题的演变 蜗牛爬井问题
我采用的是，特殊化第一天上爬，然后合并第一天休息及第二天上爬时间运算，以此类推。
不过要注意，第一天可能就爬完的问题
代码
#include<stdio.h>
int main()
{
int n,u,d,t;
while(scanf("%d%d%d",&n,&u,&d)!=EOF && n){
t=1;
n-=u;
if(n<=0) printf("%d\n",t);
else{
do{
n=n+d-u;
t+=2;
}while(n>0);
printf("%d\n",t);
}
}
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
题解
就是一道简单的四则运算，需要在除法输出小数
简单分析一下，就是需要自己输入运算符号，还有就是除法的时候小数点需要保留两位，这里没有考虑除数为零就可以通过了,并且也没有考虑当字符不是运算符的情况。
代码
#include<stdio.h>
int main()
{
int n,a,b;char c;double x;
scanf("%d",&n);
while(n--)
{
getchar();
scanf("%c%d%d",&c,&a,&b);
if(c=='+')printf("%d\n",a+b);
else if(c=='-')printf("%d\n",a-b);
else if(c=='*')printf("%d\n",a*b);
else
{
x=(a+0.00000001)/b;
if(a%b==0)printf("%d\n",a/b);
else printf("%.2lf\n",x);
}
}
}
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
题解
方法一：如果先求f(n),再判断是否能整除3，行不通，因为当n在150左右时，f(n)已经无法用64位整数保存了。f(n)实在太大了。所有，此法不可行。
方法二：我想此类题目结果一般有规律，然后就将前100个结果打印出来。发现当(i-2)%4==0时，输出yes,其余都是no。
方法三：同样是找规律的暴力解法，n%8= =2 || n%8==6，输出yes,其余都是no。
代码
#include <stdio.h>
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
if(n%8==2 || n%8==6)
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
题解
和上一题一样，暴力解法：找到规律，发现最大 49 一组
代码
#include<iostream>
using namespacestd;
int f[49];
int main(){
int i,j,k,l;
while(cin>>i>>j>>k&&i!=0){
f[1] = 1;
f[2] = 1;
for(l=3; l<49; l++) f[l]=(i*f[l-1]+j*f[l-2])%7;
cout<<f[k%49]<<endl;
}
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 2 13 -644
Sample Output
213 92 3
题解
不知道怎么解释，看一下别人大佬的叙述吧！
本题乍一看就是普通的排序题。实际上估算完时间复杂度O(n*logn)后，发现其已经在千万级别的边缘，也就是说在判题较为严格的OJ上将会TLE。故这里不能暴力sort，而应该使用hash的思想用cnt数组存储输入，这种算法的时间复杂度是线性的。
代码
#include<stdio.h>
#include<stdlib.h>
#define N 1000001
int a[N],m;
void Qsort(int low,int high){
int k,i;
k=a[low];
int left=low;
int right=high;
if(left>right)
return ;
while(left!=right){
while(a[right]<k&&left<right)
right--;
if(left<right){
a[left]=a[right];
left++;
}
while(a[left]>k&&left<right)
left++;
if(left<right){
a[right]=a[left];
right--;
}
}
a[left]=k;
if(m<=left+1)Qsort(low,left-1);
else {
Qsort(low,left-1);
Qsort(left+1,high);
}
}
int main()
{
int i,j,n;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=0;i<n;i++)scanf("%d",&a[i]);
Qsort(0,n-1);
for(i=0;i<m;i++){
printf("%d",a[i]);
if(i!=m-1)
printf(" ");
}
printf("\n");
}
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
Please use function scanf
题解
其实写完这道题，我都觉得自己再也不想吃糖了，不过，不吃糖是不可能的，我甚至还奖励了自己一杯，珍珠奶茶！
emmm 回归正题
其实就是普通的数学问题啦！
一旦有一种糖果的数量是总数量的一半多，不就不能了吗？
不过下面那个是别人的代码，因为我的不知道为啥时间久一点点，氮素，我还是想把它贴上来了
#include<stdio.h>
long long m[1000000];
int main()
{
int t;
long long i,j,n;
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%lld",&n);
long long sum=0;
for(j=0;j<n;j++){
scanf("%lld",&m[j]);
sum+=m[j];
}
int pd=0;
for(j=0;j<n;j++)
{
if(m[j]>sum-m[j]+1)
{
pd=1;
break;
}
}
if(!pd)printf("Yes\n");
else printf("No\n");
}
return 0;
}
代码
#include <stdio.h>
int main()
{
int t, n, mi, max, i;
long long sum;
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
题解
这道题就是认真读一下题目啦！超级简单的算和而已，别忘记 \n 肯定一下就 AC 的啦！
代码
#include<stdio.h>
int main(){
long long i,sum;
while(scanf("%lld",&i)!=EOF){
sum=0;
while(i>0){
sum+=i;
i--;
}
printf("%lld\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
题解
也是个hin明显的题目，就是一个判断欲停的楼层和当前楼层的一个大小关系，大时上升，小时下降，对时间进行累加求和即可
代码
#include<Stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n!=0)
{
int i,N[n+1],t;
N[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;
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
题解
真的是春天来了，连题目都春意蓬勃了，嘻嘻嘻！
不过，如果暴力搞 ，毫无疑问超时
所以换个思绪，换位思考 ，题意是要我们求输入的数n的因子之和，那么我们不如换换位，换换对象 ，看所有的因子各会出现在哪个数里面
不过，下面的代码，我也是百度之后才 AC 滴！
代码
#include<stdio.h>
__int64 a[500000+5];
int main()
{
int i,j,n,cas;
for(i=0;i<=500000;i++) a[i]=1;
for(i=2;i<=250000;i++)
{
for(j=i+i;j<=500000;j+=i)
a[j]+=i;
}
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
printf("%I64d\n",a[n]);
}
return 0;
}