P2110:欢总喊楼记题解

神仙做法

我看题解之后非常心塞，竟然不用数位 DP ！我们先来考虑部分解。当\(num<10\)时，答案就是\(num\)。如果\(num \geq 10\)，那么答案就是\(9+\frac{x}{10}\)。我们来看，考虑一个数\(1921\)的答案，我们可以考虑\(192-\)部分里有\(\lfloor \frac{1920}{10} \rfloor\)对首尾相同的数。然后再加上位数为一时的答案。

我们还要考虑，如果\(num\)的最高位大于最低尾，那么答案就要减一。比如，数字\(62\)就需要进行额外考虑，因为表面上第二位有\(6\)对首位相同的数字，其实不然，因为\(66>62\)，所以需要排除这个可能。

代码如下：

// P2110.cpp
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll L, R;
ll dp[20][20][20];

ll query(ll num)
{
    if (num <= 9)
        return num;
    ll sum = 9 + num / 10;
    ll inner = num % 10;
    ll highest = num;
    while (highest >= 10)
        highest /= 10;
    if (highest > inner)
        sum--;
    return sum;
}

int main()
{
    scanf("%lld%lld", &L, &R);
    printf("%lld", query(R) - query(L - 1));
    return 0;
}