求优化(#_#)

P1618 三连击(升级版)

justinjia @ 2020-10-15 17:57:23

#include"stdio.h"
int main(void){
    int a,b,c;
    bool flag=0;
    scanf("%d%d%d",&a,&b,&c);
    for(int i=1;i<=9;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                for(int l=1;l<=9;l++)
                    for(int m=0;m<=9;m++)
                        for(int n=0;n<=9;n++)
                            for(int o=1;o<=9;o++)
                                for(int p=0;p<=9;p++)
                                    for(int q=0;q<=9;q++)//九重循环(极其恐怖)
                                        if(i!=j&&i!=k&&i!=l&&i!=m&&i!=n&&i!=o&&i!=p&&i!=q
                                         &&j!=k&&j!=l&&j!=m&&j!=n&&j!=o&&j!=p&&j!=q
                                         &&k!=l&&k!=m&&k!=n&&k!=o&&k!=p&&k!=q
                                         &&l!=m&&l!=n&&l!=o&&l!=p&&l!=q
                                         &&m!=n&&m!=o&&m!=p&&m!=q
                                         &&n!=o&&n!=p&&n!=q
                                         &&o!=p&&o!=q
                                         &&p!=q/*也很恐怖*/
                                         &&double((i*100+j*10+k)/a)==double((l*100+m*10+n)/b)&&double((i*100+j*10+k)/a)==double((o*100+p*10+q)/c)){
                                            printf("%d %d %d\n",i*100+j*10+k,l*100+m*10+n,o*100+p*10+q);
                                            flag=1;
                                         }
    if(!flag)
        printf("No!!!");
    return 0;
}

by justinjia @ 2020-10-15 17:58:22

运行了6秒多。。。。。。


by justinjia @ 2020-10-15 17:59:16

开O2后5.92s。。。。。。


by 如雨 @ 2020-10-15 18:12:33

九层循环……


by 如雨 @ 2020-10-15 18:15:03

时间复杂度O(729000000)


by justinjia @ 2020-10-15 18:32:14

按理说我只需要去掉一层循环就可以跑进1秒了


by 如雨 @ 2020-10-15 18:35:34

应该吧


by fresh_boy @ 2020-10-15 18:51:44

@justinjia 你为什么不直接枚举三位数,而要枚举三位数的每一位数?而且只需要枚举了第一个数,后面两个也就确定了。

这题也就经典高考水平的题了


by justinjia @ 2020-10-15 18:55:53

@唱歌的向日葵 直接枚举三位数不是一样的吗?


by fresh_boy @ 2020-10-15 18:57:56

@justinjia 没什么区别,主要是后面:枚举了第一个数,后面两个也就确定了。 后面两个数不用枚举了


by justinjia @ 2020-10-16 17:15:34

@唱歌的向日葵 我没听懂(@_@)。。。。。。


|