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

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注