K-wolf Number

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5787

Description

Alice thinks an integer x is a K-wolf number, if every K adjacent digits in decimal representation of x is pairwised different.
Given (L,R,K), please count how many K-wolf numbers in range of [L,R].

Input

The input contains multiple test cases. There are about 10 test cases.

Each test case contains three integers L, R and K.

1≤L≤R≤1e18
2≤K≤5

Output

For each test case output a line contains an integer.

Sample Input

1 1 2
20 100 5

Sample Output

1
72

Source

2016 Multi-University Training Contest 5

题意：

找出区间[L,R]中有多少个数满足任意相邻的K位均不不相同.

题解：

数位DP：分别对l-1.r求出从0开始一共有多少个数满足条件.
dp[i][j]：处理到还剩下i个数时左边相邻k个数是j(j代表一串数)的情况种数.
用map , LL> dp[maxn]来表示dp数组，vector存储左边相邻的k个数.
依次枚举每一位可能放置的数字并进行递归处理.

在递归时要标记一下之前放置的那些数能否保证小于上限，如果可以当前位可以放置0-9任意数.

注意处理前导零和非前导零的情况：这里用-1代表前导零，如果枚举到当前位为0时，要先看上一位是否为-1，如果是-1则当前位要更新为-1(也是前导零).

记忆化：用map-dp记录下当前的计算结果. 注意：仅当当前数能确定比上限小时才能记录dp值.
(反例：比如样例的20和100，先处理100得到dp[2][-1,-1,-1]=91, 若记录下当前dp，在处理19时，则会直接返回91.)

之前一直TLE是因为每次处理数据时都把dp初始化了一遍，而实际上对于所有数据dp都可以共用，只需要初始化一次即可.

看到一份用五维dp数组记录的代码仅用了300ms，而上述用map-vector的记录方式用了2000ms.

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define LL long long
#define mid(a,b) ((a+b)>>1)
#define eps 1e-8
#define maxn 55000
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

int k;
int num[20];
map<vector<int>, LL> dp[20];

bool is_ok(const vector<int>& cur) {
    int state = 0;
    for(int i=0; i<k; i++) {
        if(cur[i] == -1) continue;
        if(state & (1<<cur[i])) return false;
        else state |= (1<<cur[i]);
    }
    return true;
}

LL dfs(int len, vector<int> cur, bool is_small) {
    if(len == 0) return 1LL;

    if(is_small && dp[len].count(cur)) return dp[len][cur];

    int limits = is_small? 9:num[len];
    vector<int> next; next.clear();
    int sz = cur.size();
    for(int i=1; i<sz; i++) {
        next.push_back(cur[i]);
    }

    LL ret = 0;
    for(int i=0; i<=limits; i++) {
        if(i) next.push_back(i);
        else {
            if(next[k-2] == -1) next.push_back(-1);
            else next.push_back(0);
        }
        if(is_ok(next)) {
            ret += dfs(len-1, next, !(!is_small&&i==limits));
        }
        next.pop_back();
    }

    if(is_small) dp[len][cur] = ret;
    return ret;
}

LL solve(LL x) {
    int cnt = 0;
    vector<int> cur; cur.clear();
    while(x) {
        num[++cnt] = x % 10;
        x /= 10;
    }
    for(int i=0; i<k; i++)
        cur.push_back(-1);
    return dfs(cnt, cur, 0);
}

int main(int argc, char const *argv[])
{
    //IN;

    LL l,r;
    for(int i=0; i<20; i++) dp[i].clear();

    while(scanf("%I64d %I64d %d", &l,&r,&k) != EOF)
    {
        //for(int i=0; i<20; i++) dp[i].clear();
        printf("%I64d\n", solve(r) - solve(l-1));
    }

    return 0;
}

秒客网

HDU 5787 K-wolf Number （数位DP）