P10024 题解

· · 题解

题目传送门

题目大意

给你一个区间 [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;
}