欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

luogu-P1618 三连击(升级版)【STL next_permutation()】【看题解啊】【二刷呀】

程序员文章站 2022-07-16 12:26:31
...

一开始 :丧心病狂的枚举:待优化

#include <bits/stdc++.h>
using namespace std;
#define what(x) cout << #x << " is " << x << endl;

int main()
{
    //ifstream cin("testdata.in");
    vector<bool> f(10, false);
    int A, B, C;
    cin >> A >> B >> C;
    bool found = false;
    for (int i = 1; i < 10; ++i)
    {
        f[i] = true;
        for (int a = 1; a < 10; ++a) {
            if (f[a]) continue;
            f[a] = true;
            for (int b = 1; b < 10; ++b) {
                if (f[b]) continue;
                f[b] = true;
                for (int c = 1; c < 10; ++c) {
                    if (f[c]) continue;
                    f[c] = true;
                    for (int d = 1; d < 10; ++d) {
                        if (f[d]) continue;
                        f[d] = true;
                        for (int e = 1; e < 10; ++e) {
                            if (f[e]) continue;
                            f[e] = true;
                            for (int g = 1; g < 10; ++g) {
                                if (f[g]) continue;
                                f[g] = true;
                                for (int h = 1; h < 10; ++h) {
                                    if (f[h]) continue;
                                    f[h] = true;
                                    for (int j = 1; j < 10; ++j) {
                                        if (f[j]) continue;
                                        double t1 = (i*100+a*10+b);
                                        double t2 = (c*100+d*10+e);
                                        double t3 = (g*100+h*10+j);

                                        if (fabs(t1/A - t2/B) < 1e-8 && fabs(t2/B - t3/C) < 1e-8) {
                                            //what(t1/A); what(t2/B); what(t3/C);
                                            found = true;
                                            cout << t1 << " " << t2 << " " << t3 << endl;
                                        }

                                    }
                                    f[h] = false;
                                }
                                f[g] = false;
                            }
                            f[e] = false;
                        }
                        f[d] = false;
                    }
                    f[c] = false;
                }
                f[b] = false;
            }
            f[a] = false;
        }
        f[i] = false;
    }
    if (!found) cout << "No!!!" << endl;
    return 0;
}

看题解 :STL大法好

#include<bits/stdc++.h>
using namespace std;
#define what(x) cout << #x << " is " << x << endl;
#define LL long long
//P1618 三连击(升级版)
int main()
{
    int A, B, C;
    cin >> A >> B >> C;

    int t = __gcd(A, __gcd(B, C)); // 化简
    A /= t;
    B /= t;
    C /= t;
    t = A * B * C; // 避免除法
    A = t/A;
    B = t/B;
    C = t/C;
    vector<int> iv;
    for (int i = 1; i < 10; ++i) {
        iv.push_back(i);
    }

    bool found = false;
    do {
        if ( (iv[0]*100 + iv[1]*10 + iv[2]) * A == (iv[3]*100 + iv[4]*10 + iv[5]) * B
            && (iv[3]*100 + iv[4]*10 + iv[5]) * B == (iv[6]*100 + iv[7]*10 + iv[8]) * C )
            {
                found = true;
                cout << iv[0] << iv[1] << iv[2] << " " << iv[3] << iv[4] << iv[5] << " " << iv[6] << iv[7] << iv[8] << endl;
            }
    } while (next_permutation(iv.begin(), iv.end()));
    if (!found) cout << "No!!!" << endl;
    return 0;
}

提交记录

luogu-P1618 三连击(升级版)【STL next_permutation()】【看题解啊】【二刷呀】