自动搬运

查看原文

来自洛谷，原作者为

	zhuruirong 不拿7级勾不删 || “老师，我心态崩了”

搬运于2025-08-24 22:53:57，当前版本为作者最后更新于2023-12-25 12:24:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意

给你一个区间 $[l,r]$，要求找出长度最大的整数区间，使得对于区间内的所有数字，在电子显示屏上所使用的短竖线数量相等。

注意：短竖线包括横向的线。

题目分析

由于 $l$ 和 $r$ 的范围很大，暴力枚举显然不可取，考虑找规律。

先分两种情况讨论。

1. 对于一个整数 $x$，要是 $x+1$ 不进位，唯一一种合法情况是 $x$ 的个位是 $2$，否则不满足条件。

2. 对于一个整数 $x$，要是 $x+1$ 进位，个位上的和不变（$0$ 和 $9$ 使用的短竖线数量相同），则第一个非 $9$ 的位置上的值 $+1$ 也必须不变，唯一满足条件的的值只有 $2$，如 $29$、$299$，它们 $+1$ 后使用的短竖线数量不变。

根据上面的两种情况，可以发现答案只可能是 $1$ 和 $2$。而答案怎么判断是哪一种呢？

其实可以设一个整数 $n$，把 $l$ 的后 $n$ 位替换成 $9$，第 $n+1$ 位替换成 $2$就可以了。但是，这样求出来的值可能小于 $l$，会导致答案错误，所以说需要改进。

我们记 $x$ 为把 $l$ 的后 $n$ 位替换成 $9$，第 $n+1$ 位替换成 $2$ 的值，再记一个 $y$ 是 $x+10^{n+1}$，就可以保证 $y$ 一定大于 $l$ 了，因为替换后最多会省去 $10^{n+1}-1$。只要 $x$ 和 $y$ 有一个在 $[l,r)$ 这个区间内，答案就为 $2$，否则为 $1$。

AC代码

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

int l, r;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
	cin >> l >> r;
	int cnt1 = l, cnt2 = l + 1;
	for(int i = 0, mul = 10; cnt1 <= r; i++, mul *= 10) {
		cnt1 = l / mul * mul + mul / 10 * 3 - 1;
		cnt2 = cnt1 + mul;
		if((cnt1 >= l and cnt1 < r) or (cnt2 >= l and cnt2 < r)) {
			cout << 2 << endl;
			return 0;
		}
	}
	cout << 1 << endl;

	return 0;
}