ACM 1018-1022

自用笔记

HDOJ-ACM 1018-1022解答及思路

1018

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给出一个小于100万的数字，求出它的阶乘的位数

参考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
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
int sum(int n)
{
	double sum=0;
	for(int i=0;i<n;i++)
		sum+=log10((double)i+1);
	return sum;
}
int main()
{
	int N;
	while(cin>>N)
	{
		for(int i=0;i<N;i++)
		{
			int n,d;
			cin>>n;
			d=(int)sum(n)+1;
			cout<<d<<endl;
		}
	}
	return 0;
}

思路

推导出一个正整数a的位数，如下:



接下来



注意事项

在写代码前先理清思路，在不能轻易算出100万这样的大数阶乘的情况下，从一般规律入手往往会得到简化。

1019

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

输出n个数字的最小公倍数

参考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
#include<stdio.h>
#include<iostream>
using namespace std;
long long GCD(long long a,long long b)
{
	int ex,c;
	if(a<b)
	{
		ex=a, a=b, b=ex;
	}
	while(b!=0)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int main()
{
	int N,M,gcd;
	long long a,t;
	cin>>N;
	while(N--)
	{
		cin>>M;
		t=1;
		for(int j=1;j<=M;j++)
		{
			cin>>a;
			gcd=GCD(t,a);
			t=(t*a)/gcd;
		}
		cout<<t<<endl;
	}
	return 0;
}

思路

先写出2个函数判断出2个数的最大公因数和最小公倍数，最小公倍数=两数之积/最大公因数。接着输入数据，每输入2个数字就立刻判断出它的最小公倍数，接着把它
和下一个数字比较，循环得出最后的最小公倍数。

注意事项

此题很容易超时和wrong answer。判断最大公因数的时候采用辗转相除法，可大大减少运算时间。而此题输入的数据均要采用long long型，使用int和long型都会提
示wrong answer。

1020

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

要求把字符串实现合并同类项。

参考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<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int N,n;
	char a[10001];
	cin>>N;
	while(N--)
	{
		int i=0,count=1;
		cin>>a;
		n=strlen(a);
		while(i<n)
		{
			if(a[i]==a[i+1])
			{
				count++;
				i++;
			}
			else
			{
				if(count==1)
				{
					cout<<a[i];
					i++;
					count=1;
				}
				if(count>1)
				{
					cout<<count<<a[i];
					i++;
					count=1;
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

思路

判断每一位的字符和下一个字符是否相等。若相等count++，接着进入循环判断下一个位置。若不相等则输出该字符和出现的次数，注意要讨论下次数为1不输出1即
可，count要再初始化为1进行下一轮判断。

注意事项

注意下一轮的判断count要赋值为1即可。

1021

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

类似于斐波拉契数列。前2项和7和11，求第n项是否能被3整除。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int n,a[1000000];
	while(cin>>n)
	{
		a[0]=7%3;
		a[1]=11%3;
		for(int i=2;i<=n;i++)
			a[i]=(a[i-1]+a[i-2])%3;
		if(a[n]==0)
			cout<<"yes"<<endl;
		else
			cout<<"no"<<endl;
	}
	return 0;
}

思路

公式：（a+b）%m=（a%m+b%m）%m。所以叠加的时候只需要加上每项除以3的余数即可。

注意事项

此题很容易超时或者超内存。尽量避免使用递归调用，运用上述公式可大大减少计算量。

1022

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

模拟栈的原理。有最多9辆火车进站，给出进站顺序和出战顺序，判断是否可行。

参考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
#include<stdio.h>
#include<iostream>
using namespace std;
int n;  
char input[15],output[15];  
int main()  
{  
    while(cin>>n>>input>>output)
    {  
        int stack[15],top=0;  
        int flag[15];  
        int i=0,A=0,B=0,ok=1;  
        while(B<=n)  
        {  
            if(input[A]==output[B]) {A++;B++;flag[i++]=1;flag[i++]=0;}   
            else if(top&&stack[top]==output[B]) {flag[i++]=0;top--;B++;}//出栈   
            else if(A<=n) {stack[++top]=input[A++];flag[i++]=1;} //进栈  
            else {ok=0;break;}  
			/*cout<<stack[top]<<" "<<top<<" "<<A<<" "<<flag[i-1]<<" "<<i<<" "<<B<<endl;*/
        }  
        if(ok)  
        {  
            cout<<"Yes."<<endl;
			for(int j=0;j<i-2;j++)  
            {  
				if(flag[j])
					cout<<"in"<<endl;
				else
					cout<<"out"<<endl;
            }  
        }
		else
			cout<<"No."<<endl;
        printf("FINISH\n");  
    }  
	return 0;
}

思路

　　此题极为重要，大多数人是第一次进行模拟栈。以下附给出解除第19行注释输出后的运行结果




　　该图可以清楚的看出6次循环每一步带来的变化。
　　用数组stack来模拟栈数据的存放，ok判断结果yes或no，flag用来判断若为yes后in和out的输出，top代表栈顶。while循环体的具体执行步骤是：第一步判断进入和
离开的数字是否相等，若相等，该火车直接进站后出战即可，A，B自加1，flag连续2个元素赋值为1和0，代表了in后out。不满足第一步则进行第二步判断出栈，若
栈顶没有到底部并且栈顶的元素和离开的元素相等，那么该元素离栈，flag该位置定义为0，B自增。前两步都不满足则进行第三步判断进栈，若A小于等于元素的个数。
则进栈，A自加。flag该位置定义为1。若前三步都不满足，则进行第四步，ok定义为0并且结束循环。最后若ok=1输出yes并按照flag的顺序，若为0输出out，若为1输
出in。

注意事项

　　该题的top初值必须赋为0而不能是-1，赋为0后实际存储的位置下标是用stack[1]开始的，这样在最后判断是够到达栈底不会因为top=-1而数组越界。而A和B都必须判断
为小于等于n而不能是小于n。while的循环体如果执行到最后是yes则会多执行一次。如图所示实际执行了6次循环体而不是5次，因为第6次进入的时候input[A]和ouput[B]
必然相等，因为都没被初始化过，B自增后不再满足while循环后退出，不会影响最后结果。并且当最后的结果为no时，会多执行进栈的那一步，会把没有初始化的元素赋
给stack，但也并不影响结果，因为下一个循环会因为均不满足前三次而直接执行第4步退出循环。所以修改代码若将小于等于号为小于号则得不到正确结果，多执行一步
可以满足该循环在yes和no的两种情况下都可以输出正确结果。若输出的结果为yes，因为多执行了1次第一步，所以i的元素多加了2，所以在最后输出flag元素的时候必
须写成j<i-2而不是j<i。该图stack存放的数据是49和50是因为把字符数据赋给了整型数组。最后输出格式也要留意。

本文标题:ACM 1018-1022

文章作者:Hippopmonkey

发布时间:2016-08-30, 20:23:23

最后更新:2016-08-30, 20:38:12

原始链接:http://xuboming8.github.io/2016/08/30/ACM-1018-1022/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. HDOJ-ACM 1018-1022解答及思路
    1. 1.1. 1018
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. 1019
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. 1020
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. 1021
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
    5. 1.5. 1022
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
      4. 1.5.4. 注意事项
|