[蓝桥杯2018决赛]最大乘积(附解题思路)

超、凢脫俗 2022-12-20 13:59 17阅读 0赞

## **\[蓝桥杯2018决赛\]最大乘积** ##

> 时间限制: 1 Sec 内存限制: 256 MB 提交: 158 解决: 81

题目描述  
把 1~9 这9个数字分成两组，中间插入乘号，  
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。  
比如：  
984672 \* 351 = 345619872  
98751 \* 3462 = 341875962  
9 \* 87146325 = 784316925  
…  
符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？  
输出  
输出一个整数表示答案

## 题解 ##

思路看注释

> 全排列+暴力

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    int a[] = {
        1,2,3,4,5,6,7,8,9};
    
    ll ans = 0;//记录答案
    
    bool is(ll x){
         //判断是不是符合乘积只包含1~9这9个数字，而且每个数字只出现1次
        if(x > 1e10) return false;
        int b[10] = {
        0};
        int k = 0;
        while(x){
        
            b[k++] = x%10;
            x/=10;
        }
        int c[10] = {
        0};
        for(int i = 0; i < k; i++){
        
            c[b[i]] ++;
        }
        for(int i = 1; i < 10; i++){
        
            if(c[i] != 1) {
        
                return false;
            }
        }
        return true;
    }
    
    void work()
    {
        
        for(int i = 1; i <= 8; i++){
         //暴力枚举乘号位置
            ll sum1 = 0,sum2 = 0;
            for(int j = 0; j < i; j++){
        
                sum1 *= 10;
                sum1 += a[j];
            }
            for(int j = i; j < 9; j++){
        
                sum2 *= 10;
                sum2 += a[j];
            }
            ll sum = sum1*sum2;
            if(ans > sum) continue;
            if(is(sum)) ans = max(ans,sum);
        }
    }
    
    int main()
    {
        
        do{
        
            work();
        }while(next_permutation(a,a+9));//全排列
        cout << ans << endl;
    }