G题 | Digital Folding

解题思路：

分类讨论：

• 1.l=r:显然结果是l或r的折叠数。

• 2.l!=r:

• • 若r是形如100...0这样最高位是1,其余全为0的数： 最优结果应该是r-1的折叠数，位数比r少1，全部由9构成。
• • 否则： 此时可以保证最终的答案的位数和r一致，若此时r是k位数，l的位数比r小，可以把l改成首位末位均为1，中间有k-2个0的数，把问题转化成l和r位数一致的情况。此时可以贪心，尽可能多的让最低位为9构造折叠前的数字。为了保证构造数字的合法性，从最高位开始前往后遍历l，r，若l，r当前位相等，则待折叠数字当前位和l，r当前位一致，若出现不满足的情况，即发现l当前位小于r当前位，则可以让待折叠数当前位为r当前位为1，后面全部填充9（如果此时r后面每一位都是9，则待折叠数当前位为r当前位，后面全部填充9）。

示例代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
	string l, r;
	cin >> l >> r;

	if (l == r) {
		reverse(r.begin(), r.end());
		cout << stoll(r) << endl;
		return;
	}

	string t = r;
	reverse(t.begin(), t.end());
	if (stoll(t) == 1) {
		cout << stoll(r) -1 << endl;
		return;
	}

	if (l.size() < r.size()) {
		l = string(r.size(), '0');
		l.front() = '1';
		l.back() = '1';
	}

	string ans = string(r.size(), '9');
	for (int i = 0; i < r.size(); i++) {
		ans[i] = r[i];
		if (l[i] != r[i]) {
			if (ans > r) {
				ans[i] = r[i] - 1;
				break;
			}
		}
	}

	reverse(ans.begin(), ans.end());
	cout << ans << endl;
}

signed main() {
	int T = 1;
	cin >> T;
	while (T--)
		solve();

	return 0;
}