仅分享G题神秘解法

0~100用暴力秒

别的区间先看l和r位数一不一样

不一样的话把l调到r位数最小值-1（eg. r=188 时把l调为99）

若调完之后刚好差1（99&100）直接输出l

若调完差2及以上，把l++

再进行判断若调完之后刚好差1（100&101）直接输出r

其他情况，从高位到低位比较r和调完的l

若某一位差1及以上且r的后续不全为9

r的这一位-1 后续位调为9

在18:01分成功AC

我是J1N，为你分享精心制作的史

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 INF = 1e9;
int weishu(i64 n) {
	int cnt = 0;
	while (n) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
i64 pow10(int n) {
	i64 res = 1;
	while (n--) {
		res *= 10;
	}
	return res;
}
i64 numrev(i64 n) {
	int tmp[17];
	int cnt = 0;
	while (n) {
		tmp[++cnt] = n % 10;
		n /= 10;
	}
	i64 summ = 0;
	for (int i = 1; i <= cnt; i++) {
		summ += tmp[i] * pow10(cnt - i);
	}
	return summ;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		i64 l, r;
		cin >> l >> r;
		i64 res = 0;
		if (r <= 100) {
			i64 maxx = -1e9;
			for (int i = l; i <= r; i++) {
				maxx = max(maxx, numrev(i));
			}
			res = numrev(maxx);
		} else {
			int len = weishu(r);
			if (weishu(l) < len) {
				l = pow10(weishu(r) -1) - 1;
			}
			//	cout << l << endl;
			string rstr = to_string(r);
			string lstr = to_string(l);
			while (rstr.size() != lstr.size())
				lstr = '0' + lstr;
			//	cout << rstr << endl;
			//	cout << lstr << endl;
			if (weishu(r) == weishu(l)) {
				if (r == l + 1 && r % 10 == 0)
					res = l;
				else if (r == l + 1 && l % 10 == 0)
					res =  r;
				else if (r - l < 10 && rstr[len - 2] == lstr[len - 2])
					res =  r;
				else {
					for (int i = 0; i < len; i++) {
						if (rstr[i] == lstr[i])
							continue;
						else {
							int all9 = 1;
							for (int k = i + 1; k < len; k++) {
								if (rstr[k] != '9') {
									all9 = 0;
									break;
								}
							}
							if (!all9) {
								rstr[i]--;
								for (int k = i + 1; k < len; k++)
									rstr[k] = '9';
								res = stoll(rstr);
								break;
							} else {
								res = r;
								break;
							}
						}
					}
				}
			} else if (r == l + 1) {
				res = l;
			} else {
				l = pow10(weishu(r) -1);
				string lstr = to_string(l);
				if (r == l + 1 && r % 10 == 0)
					res =  l;
				else if (r == l + 1 && l % 10 == 0)
					res =  r;
				else if (r - l < 10 && rstr[len - 2] == lstr[len - 2])
					res =  r;
				else {
					for (int i = 0; i < len; i++) {
						if (rstr[i] == lstr[i])
							continue;
						else {
							int all9 = 1;
							for (int k = i + 1; k < len; k++) {
								if (rstr[k] != '9') {
									all9 = 0;
									break;
								}
							}
							if (!all9) {
								rstr[i]--;
								for (int k = i + 1; k < len; k++)
									rstr[k] = '9';
								res = stoll(rstr);
								break;
							} else {
								res = r;
								break;
							}
						}
					}
				}
			}
		}

		cout << numrev(res) << endl;
	}
}
//1
//888 239758107329
/*for (i64 i = l; i <= r; i++) {
	i64 tmp = numrev(i);
	if (tmp > maxx)
		maxx = tmp;
}*/