526互联

Codeforces Round 879 (Div. 2) B. Maximum Strength

发布时间 2023-10-20 06:16:41作者: zsxuan

定义正整数 \(C = \overline{c_1c_2 \cdots c_k} = c_1 \cdot 10^{k-1} + c_2 \cdot 10^{k - 2} + \cdots + c_1\) 。

假设有两个正整数 \(X = \overline{x_1x_2 \cdots x_n}, Y = \overline{y_1y_2 \cdots y_n}\) 。则 \(X, Y\) 的强度为 \(|x_1 - y_1| + |x_2 - y_2| + \cdots + |x_n - y_n|\) 。不足的高位用前导零补足。

给两个正整数 \(L, R\) \(1 \leq L \leq R \leq 10^{100}\) 。寻找 \(L \leq l \leq r \leq R\) ，使得 \(l, r\) 得到最大强度。询问这个强度是多少。

不难想到，在 \(L\) 中找到尽可能左的一个 \(x\)

  • \(l_{1 \sim x - 1} = L_{1 \sim x - 1}\) ，\(l_{x} = L_{x} + 1\) ， \(l_{x + 1 \sim n} = \{ 9 \}\) 。
  • \(r_{1 \sim x} = R_{1 \sim x}\) ， \(r_{x + 1 \sim n} = \{ 0 \}\) 。

于是 \(ans = R_x - L_x + (n - x + 1) \cdot 9\) 。

由于需要构造比 \(L\) 大，于是尽可能左的 \(x\) 在 \(L\) 与 \(R\) 前缀的第一个不同位置，可以恰好保证数位不越界。

未找到 \(x\) 则代表上下边界重合，\(ans = 0\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
	std::string L, R; std::cin >> L >> R;
	std::string ldz = "";
	for (int i = 0; i < R.length() - L.length(); i++) ldz += '0';
	L = ldz + L;
	int n = L.length();
	for (int i = 0; i < n; i++) if (L[i] != R[i]) {
		std::cout << (R[i] - '0') - (L[i] - '0') + 9 * (n - 1 - i) << "\n";
		return;
	}
	std::cout << 0 << "\n";
}
		                
int main() { 
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}