P10024 「HCOI-R1」报名人数 题解

cff_0102 · 2023-12-24 22:23:00 · 题解

假设 [i,j] 之间没有进位，可以看到只有个位变化了，对照题面中的序列可以看出只有 \dots2 到 \dots3 需要的总短竖线数量一样。所以如果最后得出的 [i,j] 之间没有进位，输出不可能大于 2。

若 [i,j] 之间有进位，也就是从 \dots9 到 \dots0（或者从 \dots99 到 \dots00，等等），可以看到此时个位需要的短竖线数量不会变化，那么最后进到的那一位短竖线数量也不能变，那就只有 \dots29 到 \dots30（或者 \dots299 到 \dots300，等等）符合要求。所以此时输出也不可能大于 2。

因此，输出只能是 1 或 2。

若 [l,r] 中存在一个数 x\equiv3\times10^k(\bmod10^{k+1})（k 为整数），且 x-1 也在 [l,r] 中，则输出 2，否则输出 1。

那么怎么实现上面所说的要求呢？

首先，如果 r-l\ge10，直接输出 2，因为这样一定能找到一个 x\equiv3(\bmod10)，且 x-1 也在范围内。

接着枚举 k，如果 3\times10^k 和 3\times10^k-1 在 [l\bmod10^{k+1},r\bmod10^{k+1}] 中的话（如果 l\bmod10^{k+1}>r\bmod10^{k+1} 还得让 l\bmod10^{k+1} 变成 l\bmod10^{k+1}-10^{k+1}），就输出 2，否则输出 1。

赛时觉得 C++ 要开 long long 麻烦，就用了 Python。

l, r = input().split()
l = int(l)
r = int(r)

t = 1

if r - l >= 10:
    print(2)
    t = 0

for i in range(0, 18):
    x = 3 * (10 ** i)
    a = l % (10 ** (i+1))
    b = r % (10 ** (i+1))
    if a > b:
        a -= 10 ** (i+1)
    if a <= x-1 and b >= x:
        print(2)
        t = 0
        break

if t:
    print(1)