哎,果然全TLE，哪位大佬知道咋改

AC_710GD @ 2024-01-11 21:55:14

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c, sum1, sum2, sum3, gcd1, gcd2, gcd, ans1, ans2, ans3, d1, d2, d3, e1, e2, e3, f1, f2, f3;
    bool flag = 0;
    scanf("%d%d%d", &a, &b, &c);
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            for (int k = 1; k <= 9; k++) {
                for (int d = 1; d <= 9; d++) {
                    for (int e = 1; e <= 9; e++) {
                        for (int f = 1; f <= 9; f++) {
                            for (int g = 1; g <= 9; g++) {
                                for (int h = 1; h <= 9; h++) {
                                    for (int l = 1; l <= 9; l++) {
                                        sum1 = i * 100 + j * 10 + k;
                                        sum2 = d * 100 + e * 10 + f;
                                        sum3 = g * 100 + h * 10 + l;
                                        gcd1 = __gcd(sum1, sum2);
                                        gcd2 = __gcd(sum2, sum3);
                                        gcd = __gcd(gcd1, gcd2);
                                        ans1 = sum1 / gcd;
                                        ans2 = sum2 / gcd;
                                        ans3 = sum3 / gcd;
                                        d1 = sum1 % 10;
                                        d2 = sum1 / 10 % 10;
                                        d3 = sum1 / 100;
                                        e1 = sum2 % 10;
                                        e2 = sum2 / 10 % 10;
                                        e3 = sum2 / 100;
                                        f1 = sum3 % 10;
                                        f2 = sum3 / 10 % 10;
                                        f3 = sum3 / 100;
                                        if (ans1 == a && ans2 == b && ans3 == c && sum1 < sum2 && sum2 < sum3 && d1!=d2 && d1!=d3 && d1!=e1 && d1!=e2 && d1!=e3 && d1!=f1 && d1!=f2 && d1!=f3 && d2!=d3 && d2!=e1 && d2!=e2 && d2!=e3 && d2!=f1 && d2!=f2 && d2!=f3 && d3!=e1 && d3!=e2 && d3!=e3 && d3!=f1 && d3!=f2 && d3!=f3 && e1!=e2 && e1!=e3 && e1!=f1 && e1!=f2 && e1!=f3 && e2!=e3 && e2!=f1 && e2!=f2 && e2!=f3 && e3!=f1 && e3!=f2 && e3!=f3 && f1!=f2 && f1!=f3 && f2!=f3) {
                                            printf("%d %d %d\n", sum1, sum2, sum3);
                                            //printf("%d %d %d\n", ans1, ans2, ans3);
                                            flag = 1;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if (!flag) {
        printf("No!!!");
    }
    return 0;
}

by AC_710GD @ 2024-01-11 22:03:25

@RockyChen ??? 咋了嘛

by Zjy_AK_IOI @ 2024-01-11 22:04:17

@AC_710GD 9的9次幂当然TLE

by 半只蒟蒻 @ 2024-01-11 22:05:04

@AC_710GD 理论上也是能过的，但是可能要写剪枝

比如说，每次都选前面没选的数，或者在拼出前两个数的时候先判一次比例关系

by AC_710GD @ 2024-01-11 22:05:48

为啥题解

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
bool visit[10]={0};//visit数组，用来记录该数字是否被访问过
bool flag=0;//是否有结果
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    for(int i1=1;i1<=9;i1++)//循环
    {
        visit[i1]=1;//标记
        for(int i2=1;i2<=9;i2++)
        {
            if(visit[i2])continue;//判重
            visit[i2]=1;
            for(int i3=1;i3<=9;i3++)
            {
                if(visit[i3])continue;
                visit[i3]=1;
                for(int i4=1;i4<=9;i4++)
                {
                   if(visit[i4])continue;
                   visit[i4]=1;
                       for(int i5=1;i5<=9;i5++)
                    {
                        if(visit[i5])continue;
                        visit[i5]=1;
                        for(int i6=1;i6<=9;i6++)
                        {
                            if(visit[i6])continue;
                            visit[i6]=1;
                            for(int i7=1;i7<=9;i7++)
                            {
                                if(visit[i7])continue;
                                visit[i7]=1;
                                for(int i8=1;i8<=9;i8++)
                                {
                                    if(visit[i8])continue;
                                    visit[i8]=1;
                                    for(int i9=1;i9<=9;i9++)
                                    {
                                        if(visit[i9])continue;
                                        int n1=i1*100+i2*10+i3;
                                        int n2=i4*100+i5*10+i6;
                                        int n3=i7*100+i8*10+i9;
                                        if(double(n1)/n2==double(a)/b&&double(n2)/n3==double(b)/c)//满足题目条件
                                          {
                                               flag=1;
                                             cout<<i1<<i2<<i3<<" "<<i4<<i5<<i6<<" "<<i7<<i8<<i9<<endl;    
                                          }
                                    }
                                    visit[i8]=0;
                                }
                                visit[i7]=0;
                            }
                            visit[i6]=0;
                        }
                        visit[i5]=0;
                    }    
                    visit[i4]=0;
                }
                visit[i3]=0;
            }
            visit[i2]=0;
        }
        visit[i1]=0;//回溯
    }
    if(!flag)cout<<"No!!!";//无解
    return 0;
}

这篇能过

by a1co0av5ce5az1cz0ap_ @ 2024-01-11 22:07:45

@AC_710GD 因为题解判了vis，实际上只有 9 的阶乘

by 半只蒟蒻 @ 2024-01-11 22:08:07

@Zjy_AK_IOI 只是9的9次方怎么会tle

但是lz的code里面套了gcd，所以O(\log n) 但是 9^9 的常数，就 T 了呗

by 半只蒟蒻 @ 2024-01-11 22:08:54

@AC_710GD 他用 vst 标记了之前有没有选过这个数字啊，所以不会跑满 9^9 次枚举

by AC_710GD @ 2024-01-11 22:09:11

@半只蒟蒻

偶，nb

by AC_710GD @ 2024-01-11 22:09:38

知道咋做啦！！！

by 半只蒟蒻 @ 2024-01-11 22:09:40

其实不需要用 gcd 来判合法的，用比例关系乘一下就好了