P9888 题解

· · 题解

思路

难点在于我们在枚举 C 时无法确定该取一位数字还是两位数字。

但我们知道，两个长度为 1 的数字相乘，其最小值是 0 ，最大值是 81 ，即乘积的长度不超过 2 。其次，若乘积的长度是 2 ，则乘积的十位数字小于两个数字的任意一个；如果乘积的长度是 1 ，则乘积大于等于两个数字的任意一个。

所以我们在枚举数字时，只需要判断一下 C 的数字和我们枚举的数字的大小就可知道该取 1 位还是该取 2 位：

因为 A 和 B 的长度是已知的，所以我们可以先枚举，然后利用 C 的前半部分和枚举 B 对应 1 个或 0 个 B，然后再利用枚举的 B 去推导剩余的 A。如果推导成功就得出了答案，而且因为推导的过程是由大到小的，所以第一个满足要求的答案就是最小的答案。

CODE

#include <bits/stdc++.h>
#define maxn 200005
#define _for(i, a) for(int i = 0; i < (a); ++i)
#define _rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define scl(x) scanf("%lld", &x)
#define sc(x) scanf("%d", &x)
using namespace std;

int T, n, m;
int a[maxn], b[maxn];
char c[maxn];

bool getb() {
    int len = strlen(c), pos = 0;
    _for(i, m) {
        if (pos == len) return 0;                   //C不够用了
        int x = c[pos++] - '0';
        if (pos < len && x && x < a[0]) x = x * 10 + c[pos++] - '0';
        if (x % a[0] || x / a[0] > 9) return 0;     //除不尽或者商是两位数
        b[i] = x / a[0];
    }
    _rep(i, 1, n - 1) {
        _for(j, m) {
            if (pos == len) return 0;               //C不够用了
            int x = c[pos++] - '0';
            if (pos < len && x && x < b[j]) x = x * 10 + c[pos++] - '0';
            if (x && (b[j] == 0 || j && a[i] == 0)) return 0;   //a和b都为0但c不为0
            if (x == 0) {
                if (j && a[i] && b[j]) return 0;    //c为0但a和b都不为0；j不为0代表a已经被赋值
                if (!j) a[i] = 0;
            }
            else {
                if (x % b[j] || j && x / b[j] != a[i] || x / b[j] > 9) return 0;    //除不尽或者商是两位数
                a[i] = x / b[j];
            }
        }
    }
    return pos == len;
}

bool sol() {
    sc(n), sc(m);
    scanf("%s", c);
    int x = c[0] - '0';
    _rep(i, 1, 9) {     //利用a[0]找出b
        if (x % i == 0) {
            a[0] = i;
            if (getb()) return 1;
        }
    }
    x = x * 10 + c[1] - '0';
    _rep(i, 1, 9) {     //利用b找出a
        if (x % i == 0) {
            a[0] = i;
            if (getb()) return 1;
        }
    }
    return 0;
}

int main() {
    while (cin >> T) {
        _for(i, T) {
            if (sol()) {
                _for(j, n) printf("%d", a[j]);
                printf(" ");
                _for(j, m) printf("%d", b[j]);
                printf("\n");
            }
            else printf("Impossible\n");
        }
    }
    return 0;
}

后记

record