洛谷 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;
}
上一篇: linux内核中的汇编语言
下一篇: Apache小技巧五则_PHP教程