洛谷P2188 小Z的 k 紧凑数

P2188 小Z的 k 紧凑数

题目描述

小 Z 在草稿纸上列出了很多数，他觉得相邻两位数字差的绝对值不超过 k 的整数特别奇特，称其为 k 紧凑数。

现在小 Z 想知道 [l，r] 内有多少个 k 紧凑数，希望你帮帮他。

输入输出格式

输入格式：

第一行包含三个整数 l，r，k。

输出格式：

第一行包含一个整数，表示 [l，r] 内 k 紧凑数的个数。

输入输出样例

输入样例#1：

1 13 1

输出样例#1：

12

说明

【数据规模】

对于 30% 的数据，r − l ≤ 10^5；

对于另外 30% 的数据，l = 1，r 为 10 的倍数；

对于 100% 的数据，1 ≤ l ≤ r ≤ 10^18，0 ≤ k ≤ 8。

#include<iostream>

#include<cstdio>

using namespace std;

long long l,r;

int k,len,bin[],b[];

long long dfs(int pos,int pre,int limit,int lead){

    if(pos==len+)return ;

    int end=limit?bin[pos]:;

    long long ans=;

    if(pos==){

        for(int i=;i<=end;i++)

            ans+=dfs(pos+,i,limit&&i==end,lead&&i==);

    }

    else if(lead){

        for(int i=;i<=end;i++)

            ans+=dfs(pos+,i,limit&&i==end,lead&&i==);

    }

    else{

        for(int i=max(,pre-k);i<=min(pre+k,end);i++)

            ans+=dfs(pos+,i,limit&&i==end,lead&&i==);

    }

    return ans;

}

long long work(long long x){

    len=;

    while(x){

        b[++len]=x%;

        x/=;

    }

    for(int i=,j=len;i<=len;i++,j--)bin[i]=b[j];

    return dfs(,,,);

}

int main(){

    freopen("Cola.txt","r",stdin);

    scanf("%d%d%d",&l,&r,&k);

    cout<<work(r)-work(l-);

}

30分 暴力枚举数的每一位

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cstdlib>

#define int long long

using namespace std;

int f[][],x,y,m,bin[];

int dp(int x){

    if(x==)return ;

    bin[]=;while(x)bin[++bin[]]=x%,x/=;

    if(bin[]==)return bin[]+;

    int ans=;

    for(int i=;i<bin[];i++)

        for(int j=;j<;j++)ans+=f[i][j];

    for(int i=;i<bin[bin[]];i++)ans+=f[bin[]][i];

    for(int i=bin[]-;i;i--){

        if(i<bin[]-&&abs(bin[i+]-bin[i+])>m)return ans;

        for(int j=;j<bin[i];j++)if(abs(j-bin[i+])<=m)ans+=f[i][j];

    }

    if(abs(bin[]-bin[])<=m)ans++;return ans;

}

signed main(){

    freopen("Cola.txt","r",stdin);

    cin>>x>>y>>m;

    for(int i=;i<;i++)f[][i]=;

    for(int i=;i<=;i++)

        for(int j=;j<;j++)

            for(int k=;k<;k++)if(abs(j-k)<=m)f[i][j]+=f[i-][k];

    cout<<dp(y)-dp(x-);

    return ;

}

100分 数位dp