欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P1008 三连击

程序员文章站 2024-02-01 19:02:22
...

本文参考过 https://www.cnblogs.com/Tristan-Adams/p/9628122.html
PS:有些太简单的题目就跳过了,只写有启发的。
这是一个典型的 Generator&Discriminator 的暴力枚举。
数据生成就是那个循环,结果检查就是checkboard的使用。
思路:三个不重复数字的最小数是123,最大是987,由于三倍要小于等于987,则最小数的范围是123到987/3。
我们枚举所有可能的数字,然后计算其二倍、三倍,取其各个数位,用checkboard的对应值作为标志位,检查是不是都用过了。
原先的思路是去生成三个数字各不相同的数字,再去检查是不是2倍,3倍,后来发现难度太大了。所以直觉算法并不可靠。
答案是:

192 384 576
219 438 657
273 546 819
327 654 981

代码:

#include <stdio.h>
int main(int argc, char const *argv[])
{
	int num,num_2x,num_3x,checkboard[10],j;//checkboard用于标识1-9中哪些数字被用过了,没用时重置为0,用过后置为1
	for(num=123;num<=329;num++)//三个不相同的数字最小组成123,最大组成987/3=329
	{
		for(j=1;j<10;j++)
			checkboard[j]=0;
		num_2x=2*num;
		num_3x=3*num;
		checkboard[num%10]=1;
		checkboard[num/10%10]=1;
		checkboard[num/100]=1;
		checkboard[num_2x%10]=1;
		checkboard[num_2x/10%10]=1;
		checkboard[num_2x/100]=1;
		checkboard[num_3x%10]=1;
		checkboard[num_3x/10%10]=1;
		checkboard[num_3x/100]=1;
		for(j=1;j<10;j++)
			if(checkboard[j]==0)
				break;//如果有一个值为0,说明数字没用全,说明有重复使用的数字,不再检查
		if(j==10)//如果正常检查完,j应该为10
			printf("%d %d %d\n",num,num_2x,num_3x);
	}
	return 0;
}