526互联

AtCoder Regular Contest 130 C Digit Sum Minimization

发布时间 2023-05-20 11:50:56作者: zltzlt

洛谷传送门

AtCoder 传送门

分类讨论，但是写起来挺答辩的。

首先发现我们要使进位尽量多。

特判怎么重排都没有进位的情况（\(a_i + b_i < 10\)）。然后枚举个位选的两个数字，并且要求它们和 \(\ge 10\)。

  • 如果当前位两个位都有数字，那么从小到大枚举数位的和 \(\in [9, 18]\)；如果有数字加起来等于枚举的和就直接进入下一位。注意要优先选非 \(9\) 的数，这样留给后面只有一位有数字的进位就更多。如果当前位不可能产生进位了，那么就直接摆烂，随便选。
  • 如果当前位只有一位有数字，优先选 \(9\)，然后再选其他的（其实不需要）。

然后就做完了。

code 
// Problem: C - Digit Sum Minimization
// Contest: AtCoder - AtCoder Regular Contest 130
// URL: https://atcoder.jp/contests/arc130/tasks/arc130_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;

int n, m, ca[15], cb[15], cc[15], cd[15];
char a[maxn], b[maxn], c[maxn], s[maxn], t[maxn], ss[maxn], tt[maxn];

void solve() {
	scanf("%s%s", a + 1, b + 1);
	n = strlen(a + 1);
	m = strlen(b + 1);
	bool flag = 0;
	if (n < m) {
		swap(n, m);
		swap(a, b);
		flag = 1;
	}
	if (m < n) {
		for (int i = 1; i <= n - m; ++i) {
			c[i] = '0';
		}
		for (int i = n - m + 1, j = 1; i <= n; ++i) {
			c[i] = b[j++];
		}
		for (int i = 1; i <= n; ++i) {
			b[i] = c[i];
		}
	}
	// printf("%s %s\n", a + 1, b + 1);
	for (int i = 1; i <= n; ++i) {
		++ca[a[i] - '0'];
	}
	for (int i = 1; i <= n; ++i) {
		++cb[b[i] - '0'];
	}
	bool flg = 1;
	for (int i = 1; i <= 9; ++i) {
		for (int j = 1; j <= 9; ++j) {
			if (i + j >= 10 && ca[i] && cb[j]) {
				flg = 0;
				break;
			}
		}
		if (!flg) {
			break;
		}
	}
	if (flg) {
		memcpy(ss, a, sizeof(a));
		memcpy(tt, b, sizeof(b));
		if (flag) {
			for (int i = n - m + 1; i <= n; ++i) {
				putchar(tt[i]);
			}
			putchar('\n');
			for (int i = 1; i <= n; ++i) {
				putchar(ss[i]);
			}
		} else {
			for (int i = 1; i <= n; ++i) {
				putchar(ss[i]);
			}
			putchar('\n');
			for (int i = n - m + 1; i <= n; ++i) {
				putchar(tt[i]);
			}
		}
		return;
	}
	for (int i = 0; i <= 10; ++i) {
		cc[i] = ca[i];
		cd[i] = cb[i];
	}
	int mxk = -1;
	for (s[n] = '1'; s[n] <= '9'; ++s[n]) {
		for (t[n] = '1'; t[n] <= '9'; ++t[n]) {
			for (int i = 0; i <= 10; ++i) {
				ca[i] = cc[i];
				cb[i] = cd[i];
			}
			if (!ca[s[n] - '0'] || !cb[t[n] - '0']) {
				continue;
			}
			--ca[s[n] - '0'];
			--cb[t[n] - '0'];
			int xx = s[n] - '0', yy = t[n] - '0';
			if (xx + yy < 10) {
				continue;
			}
			int k = 1;
			for (int i = n - 1; i; --i) {
				if (b[i] == '0') {
					if (ca[9]) {
						--ca[9];
						s[i] = '9';
						++k;
					} else {
						for (int x = 1; x <= 9; ++x) {
							if (ca[x]) {
								--ca[x];
								s[i] = '0' + x;
								break;
							}
						}
					}
					continue;
				}
				bool fl = 0;
				for (int o = 9; o <= 18; ++o) {
					for (int p = 1; p < o; ++p) {
						int q = o - p;
						if (1 <= p && p < 9 && 1 <= q && q < 9) {
							if (ca[p] && cb[q]) {
								s[i] = '0' + p;
								t[i] = '0' + q;
								--ca[p];
								--cb[q];
								fl = 1;
								break;
							} else if (cb[p] && ca[q]) {
								--cb[p];
								--ca[q];
								s[i] = '0' + q;
								t[i] = '0' + p;
								fl = 1;
								break;
							}
						}
					}
					if (fl) {
						++k;
						break;
					}
					for (int p = 1; p < o; ++p) {
						int q = o - p;
						if ((p == 9 && 1 <= q && q <= 9) || (q == 9 && 1 <= p && p <= 9)) {
							if (ca[p] && cb[q]) {
								s[i] = '0' + p;
								t[i] = '0' + q;
								--ca[p];
								--cb[q];
								fl = 1;
								break;
							} else if (cb[p] && ca[q]) {
								--cb[p];
								--ca[q];
								s[i] = '0' + q;
								t[i] = '0' + p;
								fl = 1;
								break;
							}
						}
					}
					if (fl) {
						++k;
						break;
					}
				}
				if (!fl) {
					for (int o = 2; o < 9; ++o) {
						for (int p = 1; p < o; ++p) {
							int q = o - p;
							if (1 <= p && p <= 9 && 1 <= q && q <= 9) {
								if (ca[p] && cb[q]) {
									s[i] = '0' + p;
									t[i] = '0' + q;
									--ca[p];
									--cb[q];
									fl = 1;
									break;
								} else if (cb[p] && ca[q]) {
									--cb[p];
									--ca[q];
									s[i] = '0' + q;
									t[i] = '0' + p;
									fl = 1;
									break;
								}
							}
						}
						if (fl) {
							break;
						}
					}
				}
			}
			if (k > mxk) {
				mxk = k;
				memcpy(ss, s, sizeof(s));
				memcpy(tt, t, sizeof(t));
			}
		}
	}
	if (flag) {
		for (int i = n - m + 1; i <= n; ++i) {
			putchar(tt[i]);
		}
		putchar('\n');
		for (int i = 1; i <= n; ++i) {
			putchar(ss[i]);
		}
	} else {
		for (int i = 1; i <= n; ++i) {
			putchar(ss[i]);
		}
		putchar('\n');
		for (int i = n - m + 1; i <= n; ++i) {
			putchar(tt[i]);
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}