随手练——洛谷-P1008 / P1618 三连击（暴力搜索）

1.普通版

第一眼看到这个题，我脑海里就是，“我们是不是在哪里见过~”，去年大一刚学C语言的时候写过一个类似的题目，写了九重循环。。。。就像这样（在洛谷题解里看到一位兄台写的。。。。超长警告，慎重点开）

#include <stdio.h>

#include <cstdlib>

int main()

{

    int i[];

    for (i[] = ; i[] <= ; i[]++)

    {

        for (i[] = ; i[] <= ; i[]++)

        {

            int p1=;

            if (i[] == i[]) p1 = ;

            if (p1 != ) {

                for (i[] = ; i[] <= ; i[]++)

                {

                    int p2=;

                    for (int j2 = ; j2 < ; j2++) if (i[] == i[j2]) p2 = ;

                    if (p2 != ) {

                        for (i[] = ; i[] <= ; i[]++)

                        {

                            int p3=;

                            for (int j3 = ; j3 < ; j3++) if (i[] == i[j3]) p3 = ;

                            if (p3 != ) {

                                for (i[] = ; i[] <= ; i[]++)

                                {

                                    int p4=;

                                    for (int j4 = ; j4 < ; j4++) if (i[] == i[j4]) p4 = ;

                                    if (p4 != ) {

                                        for (i[] = ; i[] <= ; i[]++)

                                        {

                                            int p5=;

                                            for (int j5 = ; j5 < ; j5++) if (i[] == i[j5]) p5 = ;

                                            if (p5 != ) {

                                                for (i[] = ; i[] <= ; i[]++)

                                                {

                                                    int p6=;

                                                    for (int j6 = ; j6 < ; j6++) if (i[] == i[j6]) p6 = ;

                                                    if (p6 != ) {

                                                        for (i[] = ; i[] <= ; i[]++)

                                                        {

                                                            int p7=;

                                                            for (int j7 = ; j7 < ; j7++) if (i[] == i[j7]) p7 = ;

                                                            if (p7 != ) {

                                                                for (i[] = ; i[] <= ; i[]++)

                                                                {

                                                                    int p8=;

                                                                    for (int j8 = ; j8 < ; j8++) if (i[] == i[j8]) p8 = ;

                                                                    if (p8 != ) {

                                                                        //printf("%d %d %d %d %d %d %d %d %d\n", i[0], i[1], i[2], i[3], i[4], i[5], i[6], i[7], i[8]);

                                                                        int a =  * i[] +  * i[] + i[];

                                                                        int b =  * i[] +  * i[] + i[];

                                                                        int c =  * i[] +  * i[] + i[];

                                                                        double d1 = double(a) / b;

                                                                        double d2 = double(c) / b;

                                                                        if (d1 == 0.5 && d2 == 1.5)

                                                                        {

                                                                            printf("%d %d %d\n", a, b, c);

                                                                            //system("pause");

                                                                        }

                                                                    }

                                                                }

                                                            }

                                                        }

                                                    }

                                                }

                                            }

                                        }

                                    }

                                }

                            }

                        }

                    }

                }

            }

        }

    }

    system("pause");

    return ;

}

假设这三个数是 x : y : z = 1 : 2 : 3，那么z最大可以为987，那么x最大到329（其实比329还要小几个数，因为数字重复了，懒得去抠了），那就好办了，x 从123循环到329，判重就完事了。

#include <iostream>

#include <string.h>

using namespace std;

int a[];

//判重，且不能带0

int IsRepeat(int x) {

    memset(a, , sizeof(int) * );

    while (x) {

        int t = ++a[x % ];

        if (t ==  || a[] == )

            return ;

        x /= ;

    }

    return ;

}

int IsRepeat2(int x,int y,int z) {

    memset(a, , sizeof(int) * );

    while (x) {

        a[x % ]++; a[y % ]++; a[z % ]++;

        if (a[] > ) return ;

        x /= ; y /= ; z /= ;

    }

    for (int i = ; i < ; i++)

        if (a[i] > ) return ;

    return ;

}

int main() {

    //x,y,z 1:2:3,z最大可以为987，那么1最大到329

    for (int x = ; x <= ; x++) {

        if (IsRepeat(x)) {

            continue;

        }

        //如果x不重复，y,z 也不会重复

        int y = x * ; int z = x * ;

        if (!IsRepeat2(x, y, z)) {

            cout << x << " " << y << " " << z << endl;

        }

    }

    return ;

}

2.升级版

就是把原来的比例从1:2:3，变成了A:B:C。

思路还是差不多，中间continue判断，写的好像有点乱，但是确实不能少。

#include <iostream>

using namespace std;

bool IsRepeat(int x) {

    int a[] = {  };

    while (x) {

        int t = a[x % ]++;

        if (t ==  || a[] == )

            return true;

        x /= ;

    }

    return false;

}

bool IsRepeat3(int x, int y, int z) {

    int a[] = {  };

    while (x) {

        a[x % ]++; a[y % ]++; a[z % ]++;

        if (a[] > ) return true;

        x /= ; y /= ; z /= ;

    }

    for (int i = ; i < ; i++)

        if (a[i] > ) return true;

    return false;

}

int main() {

    int A, B, C, flag = ;

    cin >> A >> B >> C;

    for (int i = ; i < ; i++) {

        int j, k;

        if (IsRepeat(i))continue;

        if (i * B % A == ) j = i * B / A;

        else continue;

        if (j > )continue;

        if (j*C%B == ) {

            k = j * C / B;

            if (k >  || IsRepeat3(i, j, k))continue;

                flag = ;

            cout << i << " " << j << " " << k << endl;

        }

    }

    if (!flag)cout << "No!!!" << endl;

    return ;

}

巴特西

随手练——洛谷-P1008 / P1618 三连击（暴力搜索）

1.普通版

2.升级版

最新文章

热门文章