自动搬运

查看原文

来自洛谷，原作者为

	Helenty 江风引雨 / 恣睢浇灭少年抱有的幻想 / 断弦声里 / 无计唤停没有结果的爆搜 / 此去经年 / 是否还能放下封存的回忆

搬运于2025-08-24 22:52:44，当前版本为作者最后更新于2024-12-16 18:17:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

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

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

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

• 如果 $C$ 的数字小于枚举数字，就取 $2$ 位，然后判断是否能整除。
• 如果 $C$ 的数字大于等于枚举数字，就取 $1$ 位，然后判断是否能整除。

因为 $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