题解

可以注意到用位数少的一定不优，因为其向外拓展的方式更多导致不能用的数也越多。所以我们肯定先选择位数最多的，然后考虑剩下的还有哪些可以选。假设

r

的位数为

k

，考虑

[\max(10^{k-1},l),r]

都可以选。现在我们要处理位数更少的情况。考虑

r

的最高位，如果大于 1 那么说明长度为

k-1

的所有串已经全部被包含就不管了，否则就需要管。考虑

r

对长度为

k-1

的串的限制一定是一段前缀，于是找到右端点即可。

代码

CPP

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;
}

题解：AT_agc057_a [AGC057A] Antichain of Integer Strings

文章操作

题解

代码

相关推荐

评论

题解：AT_agc057_a [AGC057A] Antichain of Integer Strings