ACM 1013-1017

自用笔记

HDOJ-ACM 1013-1017解答及思路

1013

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
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	char a[1000];
	int b[1000];
	while(cin>>a&&a[0]!='0')
	{
		int len=strlen(a);
		int sum=0;
		for(int i=0;i<len;i++)
		{
			b[i]=a[i]-'0';
			sum+=b[i];
		}
		while(sum>9)
			sum=sum/1000+sum%1000/100+sum%100/10+sum%10;
		cout<<sum<<endl;
	}		
	return 0;
}

思路

用字符数组接收转换成整形数组，位数之和大于9进入循环。

注意事项

需要用数组接受字符，运用大数操作的原理。

1014

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

满足表达式seed(x+1) = [seed(x) + STEP] % MOD，seed（0）=0，如果在seed中能输出0到mod-1中所有的数字则成功，否则失败。

参考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
#include<stdio.h>
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
	int step,mod,flag=1;
	bool a[100050];
	while(cin>>step>>mod)
	{
		int seed=0;
		for(int i=0;i<mod;i++)
			a[i]=false;
		do
		{
			seed=(seed+step)%mod;
			a[seed]=true;
		}while(seed!=0);
		for(int i=0;i<mod;i++)
			if(a[i]==false)
				flag=0;
		if(flag)
			cout<<setw(10)<<step<<setw(10)<<mod<<"    "<<"Good Choice"<<endl<<endl;
		else
			cout<<setw(10)<<step<<setw(10)<<mod<<"    "<<"Bad Choice"<<endl<<endl;
	}
	return 0;
}

C++参考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
#include<stdio.h>
#include<iostream>
#include<iomanip>
#define min(a,b) a<b?a:b
using namespace std;
int prime(int a,int b)
{
	int c=min(a,b);
	for(int i=2;i<=c;i++)
	{
		if((a%i==0)&&(b%i==0))
			return 0;
		else
			continue;
	}
	return 1;
}
int main()
{
	int step,mod;
	while(cin>>step>>mod)
	{
		int flag=prime(step,mod);
		if(flag)
			cout<<setw(10)<<step<<setw(10)<<mod<<"    "<<"Good Choice"<<endl<<endl;
		else
			cout<<setw(10)<<step<<setw(10)<<mod<<"    "<<"Bad Choice"<<endl<<endl;
	}
	return 0;
}

思路

AC代码（1）：先定义一个bool型数组并且按照mod的长度全部定义为false，接着当seed不为0的时候进入循环按照表达式计算，每计算一次，数组中第seed位的数值
变为true，如果退出循环后数组中有一个flase则输出badchoice，不然输出good choice。
AC代码（2）：该方法很简便而且很巧，只要step和mod互质，则结果为good choice，否则，seed数组的值一定是相邻的两个数字相差它们的最小公约数的值，为
bad choice。

注意事项

注意输出格式，printf中输出%10d，cout中设置setw（10），在没有发现规律二的情况下用第一种方法解题也可。

1015

Problem Description

Output

Sample Output

题目要求

输入1个小于1200万的数字作为target，再输入一个不能重复的大写英文字符串，在字符串中找出按照字典数顺序的5个字符满足v - w^2 + x^3 - y^4 + z^5 = target,
若满足输出5个字符，若不存在输出no solution。若存在多个，输出字典序最大的。

参考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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int N;
char str[15],b[28]={"0ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
bool cmp(int a,int b)
{
	return a>b;
}
void find()
{
	int a[15],len;
	len=strlen(str);
	for(int i=0;i<len;i++)
		a[i]=str[i]-'A'+1;
	sort(a,a+len,cmp);
	for(int i=0;i<len;i++)
		for(int j=0;j<len;j++)
		{
			if(i==j)
				continue;
			for(int p=0;p<len;p++)
			{
				if(p==i||p==j)
					continue;
				for(int q=0;q<len;q++)
				{
					if(q==i||q==j||q==p)
						continue;
					for(int k=0;k<len;k++)
					{
						if(k==i||k==j||k==q||k==q)
							continue;
						if(a[i] - a[j]*a[j] + a[p]*a[p]*a[p] - a[q]*a[q]*a[q]*a[q] + a[k]*a[k]*a[k]*a[k]*a[k] == N)
						{
							cout<<b[a[i]]<<b[a[j]]<<b[a[p]]<<b[a[q]]<<b[a[k]]<<endl;
							return;
						}
					}
				}
			}
		}
	cout<<"no solution"<<endl;
}
int main()
{
	while(cin>>N>>str)
	{
		if(N==0&&strcmp(str,"END")==0)
			break;
		find();
	}
	return 0;
}

思路

建立一个数组顺序存放A-Z所有大写字母，并且要注意第一位空出来（我直接补了一个数字0），这样才能把A-Z与1-26对应起来。搜索的时候要把输入的字符串变为对
应代表的数字存放在一个数组中并按照降序排列，再从第一位开始套用5个for循环，如果字母对应的数字相同的话continue，直到进入最后一个循环的时候判断表达
式是否成立，若成立输出字符，不成立输出no solution。字符输出的时候要用到之前存放大写字母的数组，每个字母都在数组中对应代表数字的位置。找到第一个满
足的直接return结束函数，此时就是字典序最大的。

注意事项

数组的输入输出以及整型变字符型和字符型转整型很重要，要牢记。

1016

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
bool b[20];
int a[20],n;
int prime(int num)
{
	for(int i=2;i<=sqrt((double)num);i++)
	{
		if(num%i==0)
			return 0;
	}
	return 1;
}
void DFS(int num)
{
	if(n==num&&(prime(1+a[n-1])==1))
	{
		cout<<a[0];
		for(int i=1;i<n;i++)
		{
			cout<<" "<<a[i];
		}
		cout<<endl;
	}
	else
	{
		for(int i=2;i<=n;i++)
		{
			if((b[i]==false)&&prime(i+a[num-1])==1)
			{
				a[num]=i;
				b[i]=true;
				DFS(num+1);
				b[i]=false;
			}
		}
	}
}
int main()
{
	static int x=1;
	while(cin>>n)
	{
		for(int i=0;i<n;i++)
			b[i]=false;
		a[0]=1;
		cout<<"Case "<<x<<":"<<endl;
		x++;
		DFS(1);
		cout<<endl;
	}
	return 0;
}

思路

本题用深度搜索算法较为简单。用数组a存放输出的数据，用数组b判断某数是否在前面已经出现过，将b按照n的大小全部初始化为false，接着哪个数字出现了，就把
那个数字对应位置的元素改为true进入DFS后，先判断是否为到了最后一步，若最后一个数和第一个数依然满足和为质数，则满足条件输出。不然的话进入循环开始
从2-n依次判断和前一个数的和是否为质数，并且判断该位置是否为false，都满足的话，把该数存入a，b中对应位置变为true，再深搜下一个数，若没有满足条件回
到了开始的循环中，则b中改位置的元素改回false。

注意事项

若DFS（num+1）深搜后不满足条件返回来了，那么b[i]的值要变回false。此题的输出格式也要注意，每一行的末尾不能有空格。

1017

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

N个输入模块。每个模块中输入n和m2个数字，在1-n中寻找整数对（a，b），其中0<a<b<n,输出满足表达式(a^2+b^2 +m)/(ab)的个数

参考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
#incldue<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int N,n,m;
	cin>>N;
	for(int p=1;p<=N;p++)
	{
		int flag=1;
		while(cin>>n>>m && !(n==0&&m==0))
		{
			int a,b,count=0;
			for(int i=1;i<n;i++)
			{
				a=i;
				for(int j=a+1;j<n;j++)
				{
					b=j;
					if((a*a+b*b+m)%(a*b)==0)
						count++;
				}
			}
			cout<<"Case "<<flag++<<": "<<count<<endl;
		}
		if(p!=N)
			cout<<endl;
	}
	return 0;
}

思路

利用2个for循环分别找出a和b。

注意事项

此题的输出格式非常重要，题目给出的输出格式是错的。正确的是N和第一个输入模块中没有空行，最后一行也没有空行，只有在模块之间才有空行。

本文标题:ACM 1013-1017

文章作者:Hippopmonkey

发布时间:2016-08-30, 20:09:27

最后更新:2016-08-30, 20:22:36

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

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

文章目录
  1. 1. HDOJ-ACM 1013-1017解答及思路
    1. 1.1. 1013
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. 1014
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码(一)
      3. 1.2.3. C++参考AC代码（二）
      4. 1.2.4. 思路
      5. 1.2.5. 注意事项
    3. 1.3. 1015
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. 1016
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
    5. 1.5. 1017
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
      4. 1.5.4. 注意事项
|