K-wolf Number
Total Submission(s): 384 Accepted Submission(s): 136
Problem 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.
Output
For each test case output a line contains an integer.
Sample Input
1 1 2
20 100 5
Sample Output
1
72
Author
ZSTU
Source
2016 Multi-University Training Contest 5
题目大意:
给出区间[L,R],询问区间内K-wolf number的个数。
K-wolf number:如果数字X中任意的连续K个个位数都是两两互不相同的
那么X就是K-wolf number
譬如 121是2-wolf number
但不是3-wolf number 因为连续的三个个位数121中出现了两个1
数位DP,比较模板的。
不太好处理的是连续K位不同。
自我感觉处理方法绝佳~~(自恋一番
数位DP里的那些套路的东西就不说了。
在dfs中加了个参数hs,表示搜到当前位置,出去前导零后的位数。
另一个参数pre表示搜到当前位置往前k位内的数字。在其最高位添加1
作为阻隔。防止出现0001这种
譬如 搜索1001时 k = 2 如果不加阻隔的话
id pre
0 0
1 1
2 10
3 (1)00
4 (0)01
但实际上00会变成0
因此加上隔断 就变成了
id pre
0 1
1 11
2 110
3 1(1)00
4 1(0)01
判断当前数字是否出现就
while(pre/10) if(x != pre%10) return false; else pre /= 10;
这种
代码如下:
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const double eps = 1e-8;
int bit[23];
LL dp[23][20100];
int mod,k;
bool cal(int c,int x)
{
while(c/10)
{
if(c%10 == x) return false;
c /= 10;
}
return true;
}
//h--高位判断 pos--当前访问位置 hs--除前导0后数位 pre--k位内数字状态
LL dfs(bool h,int pos,int hs,int pre)
{
if(pos == -1) return 1;
//没想好好的k位溢出方式,O(9)的while 还好吧。。
while(pre-mod/10 >= mod/10) pre -= mod/10;
//printf("%d %d %d %d\n",h,pos,pre,hs);
if(h == 0 && dp[pos][pre] != -1) return dp[pos][pre];
int en = h? bit[pos]: 9;
int st;
LL ans = 0;
for(st = 0; st <= en; ++st)
{
if(!cal(pre,st)) continue;
if(hs == 0 && (st == 0)) ans += dfs(h&&(st == en),pos-1,hs,pre);
else ans += dfs(h&&(st == en),pos-1,hs+1,pre*10+st);
}
if(!h) dp[pos][pre] = ans;
return ans;
}
LL solve(LL x)
{
if(!x) return 1;
int len = 0;
while(x)
{
bit[len++] = x%10;
x /= 10;
}
memset(dp,-1,sizeof(dp));
return dfs(1,len-1,0,1);
}
int main()
{
//fread("");
//fwrite("");
LL l,r;
while(~scanf("%lld%lld%d",&l,&r,&k))
{
mod = 1;
for(int i = 0; i < k; ++i)
{
mod *= 10;
}
printf("%lld\n",solve(r)-solve(l-1));
}
return 0;
}