洛谷 P1008 三连击 题解

本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

将 1, 2,...... , 9 共 9 个数分成 3 组，分别组成 3 个三位数，且使这 3 个三位数构成 1 : 2 : 3 的比例，试求出所有满足条件的 3 个三位数。

无

若干行，每行 3 个数字。按照每行第 1 个数字升序排列。

无

192 384 576
* * *
...
​
* * *
（剩余部分不予展示）

• 把9个数字分成3个三位数，用a,b,c进行存储

• 比例满足1：2：3，那么就可以确定下来3个三位数的区间：最大的三位数为987，最小的三位数为123，根据比例确定区间

• a=[123,329] b=[246,658] c=[369,987]

  1. 最开始我准备用三重循环，这是最暴力的解法，但是时间复杂度为 206×412×618=52450896，对于解这道题不太理想

  2. 后面，我想如果用第一个三位数的循环，加上对应比例，就可以减少后面两个三位数不必要的循环了，还是用暴力法

     int a,b,c;
       a=123;  b=2*a;  c=3*a;

结果在判断的地方出现了问题：既要保证每个数字都只使用一次，还要保证3个三位数各不相同，先看为什么第一次错了

//  (不正确) 
int main(){
    int a,b,c;
    for(a=123;a<=329;a++){
        b=2*a;
        c=3*a;
        if(( ((a%10)+(a/10%10)+(a/100)) != ((b%10)+(b/10%10)+(b/100)) ) && ( ((a%10)+(a/10%10)+(a/100))!=((c%10)+(c/10%10)+(c/100)) ) && ( ((a%10)+(a/10%10)+(a/100)) != ((c%10)+(c/10%10)+(c/100)) ) );
        printf("%d %d %dn",a,b,c);
    } return 0; 
} 

出现了很多数字重复的情况，因为我没有采用三个三位数每一位都进行比较的办法

#include
int main(){
    int a,b,c;
    for(a=123;a<=329;a++){
        b=2*a;
        c=3*a;
        if( (a%10)+(a/10%10)+(a/100)+(b%10)+(b/10%10)+(b/100)+(c%10)+(c/10%10)+(c/100)==(1+2+3+4+5+6+7+8+9)
            &&(a%10)*(a/10%10)*(a/100)*(b%10)*(b/10%10)*(b/100)*(c%10)*(c/10%10)*(c/100)==(1*2*3*4*5*6*7*8*9)); 
        printf("%d %d %dn",a,b,c);
    } return 0; 
}