AtCoder ABC221C. Select Mul(灰色)
原题链接
简单
算法1
(枚举全排列) $O(k!k^2)$
- 拆开 $N$ 的每一位并把它们存入数组
a
中
- 把数组 $a$ 进行从小到大排序
- 枚举数组 $a$ 的全排列,对于当前排列,我们可以枚举两数的分界线
- 注意:若分界线对应的数为 $0$ 直接跳过即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
int main() {
int n;
cin >> n;
vector<int> a;
while (n) {
a.push_back(n % 10);
n /= 10;
}
sort(a.begin(), a.end());
int k = a.size();
int ans = 0;
do {
rep(i, k) {
if (a[i] == 0) continue;
int l = 0, r = 0;
rep(j, i) l = l * 10 + a[j];
for (int j = i; j < k; ++j) r = r * 10 + a[j];
ans = max(ans, l * r);
}
} while (next_permutation(a.begin(), a.end()));
cout << ans << '\n';
return 0;
}
算法2
(bit全探索)
- 这题用字符串来处理会比较方便
- 我们可以用
bit全探索
(二进制枚举)来枚举第一个数的每一位分别取 $N$ 中的哪些值,$N$ 中剩下的位当作另一个数,而为了防止出现前导 0
的情况以及使得两数乘积最大,可以将二者每一位上的数字分别从大到小排序
Python 代码
s = input()
n = len(s)
ans = 0
for bit in range(1, 1 << n - 1):
a = [s[i] for i in range(n) if bit >> i & 1]
b = [s[i] for i in range(n) if not bit >> i & 1]
a.sort(reverse=True)
b.sort(reverse=True)
A = int("".join(a))
B = int("".join(b))
ans = max(ans, A * B)
print(ans)