UVa 725 Division (枚举)

题意： 输入正整数n，按从小到大的顺序输出所有形如abcde/fghij = n的表达式，其中a～j恰好为数字0～9的一个排列（可以有前导0），2≤n≤79。

分析： 最暴力的方法莫过于采用数组存储0~9然后next_permutation枚举排列再带入表达式看是否满足等式，但是这样的复杂度就是O(10!)了，时间复杂度超高。所以采取另外一种枚举方法，先枚举分母fghij，再根据分母算出分子，然后检测分母分子出现的字数是否有重复即可。那这样的复杂度是多少呢？复杂度主要就在枚举分母上了，枚举分母的方法就是采用一个for(int Flood=1234; Flood<100000; Flood++); ，枚举量大大减少。

O(10!)

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
    int n;
    ] = {,,,,,,,,,};
    ;
    while(~scanf("%d", &n) && n){
        if(blank++) puts("");
        bool Have = false;
        do{
            ]* + digit[]* + digit[]* + digit[]* + digit[];
            ]* + digit[]* + digit[]* + digit[]* + digit[];
            ],digit[],digit[],digit[],digit[],digit[],digit[],digit[],digit[],digit[],n);Have=true;}
        }));
        if(!Have) printf("There are no solutions for %d.\n", n);
    }
    ;
}

O(AC)

#include<bits/stdc++.h>
using namespace std;
bool check(int Ceil, int Flood)
{
    ];
    ; i<; i++) digit[i] = false;
    ) digit[] = true;
    while(Ceil){
        ;
        if(digit[remainder]) return false;
        else digit[remainder] = true;
        Ceil/=;
    }
    ){
        ]) return false;
        ] = true;
    }
    while(Flood){
        ;
        if(digit[remainder]) return false;
        else digit[remainder] = true;
        Flood/=;
    }
    return true;
}
int main(void)
{
    int n;
    ;
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    while(~scanf("%d", &n) && n){
        if(blank++) puts("");
        bool Have = false;
        ; Flood<; Flood++){
            int Ceil = Flood * n;
            ) continue;
            else{
                if(check(Ceil, Flood)){
                    Have = true;
                    ) putchar(');
                    printf("%d / ", Ceil);
                    ) putchar(');
                    printf("%d = %d\n", Flood, n);
                }
            }
        }
        if(!Have) printf("There are no solutions for %d.\n", n);
    }
    ;
}

巴特西

UVa 725 Division (枚举)

最新文章

热门文章