超时了

P1008 [NOIP1998 普及组] 三连击

@[zhaoanqiEtayo](/user/1027350) 你的时间复杂度约为 $O(9^9)\approx387420489\approx4\times10^8$ ,一般来说是会超时的。 正解方法就是枚举第一个三位数,计算出后两个三位数,然后分解出每一位,判断是否有重复。时间复杂度最小约 $O(136)$ ,完全在时间限制内。 当然,你也可以在本地运行后,用程序输出答案或上传文件,因为本题可以直接提交答案。
by zqh123b @ 2023-07-05 16:06:04


@[zhaoanqiEtayo](/user/1027350) 您的代码有以下的问题: 1. 变量`j`,`k`,`l`的计算先于`a`至`i`的赋值 2. 没有检测`a`与`c`的相等,以及其他类似情况 建议参考以下[题解](https://www.luogu.com.cn/blog/user76149/solution-p1008)
by a4001234567 @ 2023-07-05 16:11:52


```c #include<stdio.h> #include<stdlib.h> int main() { int a,b,c,d,e,f,g,h,i,j,k,l; for(a=1;a<=9;a++) { for(b=1;b<=9;b++) { for(c=1;c<=9;c++) { j=100*a+10*b+c; } } } k=2*j; l=3*j; d=k/100; e=k/10%10; f=k/10; g=l/100; h=l/10%10; i=l/10; if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&e!=f&&e!=g&&e!=h&&e!=i&&f!=g&&f!=h&&f!=i&&g!=h&&g!=i&&h!=i) { printf("%d %d %d\n",j,k,l); } return 0; } ``` 这样对吗?@[zqh123b](/user/587615)
by zhaoanqiEtayo @ 2023-07-05 16:45:58


@[zhaoanqiEtayo](/user/1027350) 不用这么麻烦啊(ˉ▽ˉ;)...
by zqh123b @ 2023-07-05 16:47:25


[可以参考一下](https://www.luogu.com.cn/blog/user18441/solution-p1008)
by zqh123b @ 2023-07-05 16:49:02


[如果能看懂的话这个小众方法也行](https://www.luogu.com.cn/blog/0-----0/solution-p1008)
by zqh123b @ 2023-07-05 16:50:45


@[zqh123b](/user/587615) 可是这个为什么错了呢?
by zhaoanqiEtayo @ 2023-07-05 16:57:36


@[zhaoanqiEtayo](/user/1027350) 对于这份代码: ```cpp #include<stdio.h> #include<stdlib.h> int main() { int a,b,c,d,e,f,g,h,i,j,k,l; for(a=1;a<=9;a++) { for(b=1;b<=9;b++) { for(c=1;c<=9;c++) { j=100*a+10*b+c; } } } k=2*j; l=3*j; d=k/100; e=k/10%10; f=k/10; g=l/100; h=l/10%10; i=l/10; if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&e!=f&&e!=g&&e!=h&&e!=i&&f!=g&&f!=h&&f!=i&&g!=h&&g!=i&&h!=i) { printf("%d %d %d\n",j,k,l); } return 0; } ``` 1. 计算和判断没有放到循环中,应改为: ```cpp #include<stdio.h> #include<stdlib.h> int main() { int a,b,c,d,e,f,g,h,i,j,k,l; for(a=1;a<=9;a++) { for(b=1;b<=9;b++) { for(c=1;c<=9;c++) { j=100*a+10*b+c; k=2*j; l=3*j; d=k/100; e=k/10%10; f=k/10; g=l/100; h=l/10%10; i=l/10; if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&e!=f&&e!=g&&e!=h&&e!=i&&f!=g&&f!=h&&f!=i&&g!=h&&g!=i&&h!=i) { printf("%d %d %d\n",j,k,l); } } } } return 0; } ``` 2. 没有考虑后两个三位数超过999的情况,应改为: ```cpp #include<stdio.h> #include<stdlib.h> int main() { int a,b,c,d,e,f,g,h,i,j,k,l; for(a=1;a<=9;a++) { for(b=1;b<=9;b++) { for(c=1;c<=9;c++) { j=100*a+10*b+c; k=2*j; l=3*j; if(l>999)continue; d=k/100; e=k/10%10; f=k/10; g=l/100; h=l/10%10; i=l/10; if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&e!=f&&e!=g&&e!=h&&e!=i&&f!=g&&f!=h&&f!=i&&g!=h&&g!=i&&h!=i) { printf("%d %d %d\n",j,k,l); } } } } return 0; } ``` 3. 注意所有数字中不能含0,应改为: ```cpp #include<stdio.h> #include<stdlib.h> int main() { int a,b,c,d,e,f,g,h,i,j,k,l; for(a=1;a<=9;a++) { for(b=1;b<=9;b++) { for(c=1;c<=9;c++) { j=100*a+10*b+c; k=2*j; l=3*j; if(l>999)continue; d=k/100; e=k/10%10; f=k/10; g=l/100; h=l/10%10; i=l/10; if(d==0||e==0||f==0||g==0||h==0||i==0)continue; if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h&&a!=i&&b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h&&b!=i&&c!=d&&c!=e&&c!=f&&c!=g&&c!=h&&c!=i&&d!=e&&d!=f&&d!=g&&d!=h&&d!=i&&e!=f&&e!=g&&e!=h&&e!=i&&f!=g&&f!=h&&f!=i&&g!=h&&g!=i&&h!=i) { printf("%d %d %d\n",j,k,l); } } } } return 0; } ``` 4. 判断重复不完整,如输出第一行为182 364 546,4和6都重复了,少了7和9,自己先检查一下,我有事。 没有问题的话就可以AC了
by zqh123b @ 2023-07-05 17:13:14


@[zhaoanqiEtayo](/user/1027350) 能看懂吗?
by zqh123b @ 2023-07-05 17:13:52


@[zqh123b](/user/587615) 可以的,谢谢啦
by zhaoanqiEtayo @ 2023-07-05 17:44:14


|