ACM模版

描述

题解

这个题着实难住了我,虽然知道是数位 dp,但是依然是手足无措,找了 光速小子0511 的代码,看了一下,神还原题解啊,必须点赞,太崇拜了……

官方题解:

这个官方题解有一个小小的玩笑,我想机智的你仔细看一定是可以看出来的,尽管我没有看出来,我还是看到了讨论区才知道,O(∩_∩)O哈哈~制杖如我!

代码

#include <iostream>
#include <cstring>
#include <cstdio>

#define clr(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int MAXN = 1024;
const int MAXK = 20;

ll L, R, k;
ll res[MAXK][MAXK][MAXN];
int dig[MAXK];

int change(int s, int x)
{
    for (int i = 0; i < 10; i++)
    {
        if ((i > x) && (s >> i & 1))
        {
            s ^= (1 << i);
        }
    }
    return s | (1 << x);
}

// len: x 的二进制长度,cnt: 栈中数的个数,tag: 二进制维护栈中的数,flag: 标记是否为最高位
ll dfs(int len, int cnt, int tag, int flag)
{
    if (len == 0)
    {
        return cnt == k;
    }
    if (!flag && res[len][cnt][tag] != -1)
    {
        return res[len][cnt][tag];
    }

    int u = flag == 1 ? dig[len] : 9;
    ll ans = 0;
    for (int i = 0; i <= u; i++)
    {
        if (tag >> i & 1)
        {
            ans += dfs(len - 1, cnt, change(tag, i), i == u && flag);
        }
        else
        {
            ans += dfs(len - 1, cnt + 1, change(tag, i), i == u && flag);
        }
    }

    if (!flag)
    {
        res[len][cnt][tag] = ans;
    }

    return ans;
}

ll solve(ll x)
{
    int len = 0;
    while (x)
    {
        len++;
        dig[len] = x % 10;
        x /= 10;
    }

    clr(res, -1);
    return dfs(len, 0, 1, 1);
}

int main()
{
    cin >> L >> R >> k;
    cout << solve(R) - solve(L - 1) << endl;

    return 0;
}