G题 | Digital Folding

解题思路：

首先明确：位数大的数字一定比位数小的数字大；若位数相同，从最高位到最低位遍历每一位，第一个值不同的位置，值更大的数字更大。

先按 和 的位数分类讨论，这里规定 表示数字 的位数：

• 

  如果 最高位是 ，其他位全是 ，即 是最小的 位数，则答案一定为 个 。因为 是唯一一个能取到的 位数，其 “折叠数” 为 ，因此“折叠数”的位数最大为 。取满足条件的最大值即可。

  否则， 最小为以 结尾的 位数，即以 开头、以 结尾、中间夹了 个 的数字。因此“折叠数”一定可以取到 位数。因此，左边界被限制到了最小的以 结尾的 位数。此时问题被转换成了 的情况。

• 

  • 

    答案显然为 (或 ) 的“折叠数”。

  • 

    由于位数相同，“折叠数”的大小只和折叠后的高位的大小有关，因此我们可以贪心地令折叠前数字的后缀为若干个 。具体规则如下：从高到低遍历每一位，如果两个数字对应位相同，则保留这一位（因为任何修改都会导致越界）；直到遇到第一个不同的位，此时该位保留最大的那一位，同时记这一位为第 位，其后所有位都置为 。如果此时构成的数字大于右边界，则将第 位减去 。可以保证此值在 范围内，该数字的“折叠数”为最大值。（可以思考一下如何保证第 为可以减去 ，即如何保证第k位不为 ？）

示例代码：

void solve() {
	string l, r;
	cin >> l >> r;
  
	if (l.size() < r.size()) {
		string t = r;
		reverse(t.begin(), t.end());
		if (stoll(t) == 1) {
			string ans(r.size() - 1, '9');
			cout << ans << endl;
			return;
		}
		l = string(r.size(), '0');
		l.front() = '1';
		l.back() = '1';
	}

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

	string ans(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];
			break;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
}