题解：AT_agc057_a [AGC057A] Antichain of Integer Strings

Rotating_Lines · 2025-11-20 21:31:00 · 题解

题解

可以注意到用位数少的一定不优，因为其向外拓展的方式更多导致不能用的数也越多。所以我们肯定先选择位数最多的，然后考虑剩下的还有哪些可以选。假设 r 的位数为 k，考虑 [\max(10^{k-1},l),r] 都可以选。现在我们要处理位数更少的情况。考虑 r 的最高位，如果大于 1 那么说明长度为 k-1 的所有串已经全部被包含就不管了，否则就需要管。考虑 r 对长度为 k-1 的串的限制一定是一段前缀，于是找到右端点即可。

代码

signed main(){
    for(int T = rd(); T--; pc('\n')){
        int l = rd(), r = rd();
        int x = 1; while(x * 10 <= r)x *= 10;
        if(x <= l)wt(r - l + 1);
        else{
            int s = r - x + 1; x /= 10;
            if(x * 20 > r)s += x * 10 - max(max(x, l - 1), max(r / 10, r - (x * 10))) - 1;
            wt(s);
        }
    }
    return 0;
}