数位dp

数位dp前置条件f[i][j]////一共有i位且最高位是j的方案数

Description

如果一个自然数

Input

从文件读入数据，第一行为

Output

将结果输出

Samples

Input Copy

4 2

Output

Source

学习数位dp就知道f[i][j]////一共有i位且最高位是j的方案数

这个题就是K进制的话，就是最高位最对时K-1

这给题有一个坑就是最高位时1的话就是有k个数，就是得算上0

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void out(__int128 x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) out(x / 10);
    putchar(x % 10 +'0');
}
const int maxn=20;
ll f[maxn][maxn];////一共有i位且最高位是j的方案数
int kk,l;
void inint(){
    cin>>kk>>l;
    for(int i=0;i<=kk-1;i++){
        f[1][i]=1;
    }
    for(int i=2;i<=l;i++){
        for(int j=0;j<kk;j++){
            for(int k=0;k<kk;k++){
                if(abs(j-k)!=1){
                    f[i][j]=(f[i][j]+f[i-1][k]);
                }
            } 
        }
    }
}
int main(){
    inint();
    ll ans=0;
    if(l==1){
        cout<<kk<<endl;
        return 0;
    }
    for(int i=1;i<=kk-1;i++){
        ans=(ans+f[l][i]);
    }
    printf("%lld
",ans);
}

视频讲解：

https://www.bilibili.com/video/BV1yT4y1u7jW?from=search&seid=18102798204929854343

练习：

https://vjudge.net/contest/383125#overview

模板

#include<vector>
#include<iostream>
using namespace std;

const int N = 100;

int f[N][N];
int u[N];

//根据题目要求来预处理f[i][j]
void init() {

}
//计算[0,n]符合f(x)的个数
int dp(int n) {
    //如果L可以取到0的话，特判-1
    if (n == -1) return 0;
    //特判0
    if (n == 0) return 0 / 1;

    //用于把每位的数字提取出来
    vector<int> vt;
    while (n) vt.push_back(n % 10), n /= 10;

    //res记录返回值，last保留前缀的信息
    int res = 0, last = 0;
    for (int i = vt.size() - 1; i >= 0; i--) {
        //第一种放法
        for (int j = 0; j < vt[i]; j++) {
            if (true) res += f[][];
        }
        //第二种放法就是vt[i]本身，特判vt[i]是否和法，不合法直接退出就好
        if (false) break;
    }

    //返回答案
    return res;
}
int main() {

    //预处理需要的数据
    init();

    int l, r;
    while (cin >> l >> r) {
        //技巧一
        cout << dp(r) - dp(l - 1) << endl;
    }
    return 0;
}

//如果是732 先找
// 第一位先找1 2 3 4 5 6 然后才是这一位是7的时候在递归下一位

1.A - Amount of Degrees

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=31;
int a[maxn][maxn];
int n,m,k,b;
void inint(){
    a[0][0]=1;
    for(int i=0;i<=maxn;i++){
        a[i][0]=1; 
        for(int j=1;j<=i;j++){
            a[i][j]=a[i-1][j]+a[i-1][j-1];
        }
    }
} 
int dp(int n){
    if(n==0){
        return 0;
    }
    vector<int>nums;
    while(n){
        nums.push_back(n%b),n/=b;
    }
    int last=0;
    int res=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];    
        if(x){//左边 
            if(x>1){
                res+=a[i][k-last]+a[i][k-last-1]; 
                break; 
            }
            else if(x==1){
                res+=a[i][k-last];
                last++; 
                if(last>k){
                    break;
                }
            }
        }
        if(last>k){
            break;
        }
        if(!i&&last==k){
            res++;
        } 
    }
    return res; 
}
int main(){
    inint();
    cin>>n>>m>>k>>b; 
    cout<<dp(m)-dp(n-1)<<endl; 
}

2.B - 数字游戏

科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 $123$ ， $446$ 。现在大家决定玩一个游戏，指定一个整数闭区间 $[a, b]$ ，问这个区间内有多少个不降数。

Input

有多组测试数据。每组只含两个数字 $a, b$ ，意义如题目描述。

Output

每行给出一个测试数据的答案，即 $[a, b]$ 之间有多少不降数。

Example

样例输入

1 9
1 19

样例输出

9
18

Hint

对于全部数据， $1 \leq a \leq b \leq 2^{31} - 1$ 。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=15;
int f[maxn][maxn];//一共有i位且最高位是j的方案数 
void inint(){
    for(int i=0;i<=9;i++){
        f[1][i]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<=9;j++){
            for(int k=j;k<=9;k++){
                f[i][j]+=f[i-1][k];
            }
        }
    }
}
int dp(int n){
    if(n==0){
        return 1;
    }
    vector<int>nums;
    while(n){
        nums.push_back(n%10),n/=10;
    }
    int last=0,ans=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=last;j<x;j++){
            ans+=f[i+1][j];
        }
        if(x<last) break;
        last=x;
        if(!i){//递归到最后
            ans++;
        }
    } 
    return ans;
}
int main(){
    int l,r;
    inint(); 
    while(cin>>l>>r){  
        cout<<dp(r)-dp(l-1)<<endl;
    }
}

C - Windy 数

原题来自：SCOI 2009

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。

Windy 想知道，在 $A$ 和 $B$ 之间，包括 $A$ 和 $B$ ，总共有多少个 Windy 数？

Input

一行两个数，分别为 $A, B$ 。

Output

输出一个整数，表示答案。

Example

样例输入 1

1 10

样例输出 1

样例输入 2

25 50

样例输出 2

//如果是732 先找
// 第一位先找1 2 3 4 5 6 然后才是这一位是7的时候在递归下一位

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=15;
int f[maxn][maxn];
void inint(){
    for(int i=0;i<=9;i++){
        f[1][i]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<=9;k++){
                if(abs(j-k)>=2) 
                    f[i][j]+=f[i-1][k];
            }
        }
    }
}
int dp(int n){
    if(n==0){
        return 0;
    }
    vector<int>nums;
    while(n){
        nums.push_back(n%10),n/=10;
    }
    int last=-2,ans=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=i==nums.size()-1;j<x;j++){
            if(abs(j-last)>=2) 
                ans+=f[i+1][j];
        }
        if(abs(x-last)>=2) last=x;
        else{
            break;
        }
        if(!i){
            ans++;
        }
    }
    for(int i=1;i<nums.size();i++){
        for(int j=1;j<=9;j++){
            ans+=f[i][j];
        }
    } 
    return ans;
}
int main(){
    int l,r;
    inint(); 
    while(cin>>l>>r){  
        cout<<dp(r)-dp(l-1)<<endl;
    }
}

D - 数字游戏

由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和

$mod N$ 为 $0$ 。现在大家又要玩游戏了，指定一个整数闭区间 $[a, b]$ ，问这个区间内有多少个取模数。

Input

题目有多组测试数据。每组只含三个数字 $a, b, N$ 。

Output

对于每个测试数据输出一行，表示各位数字和 $mod N$ 为 $0$ 的数的个数。

Example

样例输入

1 19 9

样例输出

Hint

对于全部数据， $1 \leq a, b \leq 2^{31} - 1, 1 \leq N < 100$ 。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=11;
const int M=110;
int f[maxn][maxn][M];    
int l,r,p;
int mod(int x,int y){
    return (x%y+y)%y;
}
void inint(){
    memset(f,0,sizeof(f));
    for(int i=0;i<=9;i++){
        f[1][i][i%p]++;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<p;k++){
                for(int x=0;x<=9;x++){
                    f[i][j][k]+=f[i-1][x][mod(k-j,p)];
                }
            }
        }
    }
}
int dp(int x){
    if(x==0){
        return 1;
    }
    vector<int>nums;
    while(x){
        nums.push_back(x%10),x/=10;
    }
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=0;j<x;j++){
            res+=f[i+1][j][mod(-last,p)];
        }
        last+=x;
        if(!i&&last%p==0){
            res++;
        }
    }
    return res;
    
}
int main(){
    while(cin>>l>>r>>p){
        inint();
        cout<<dp(r)-dp(l-1)<<endl;
    }
}

E - 不要 62

杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如： $62315, 73418, 88914$ 都属于不吉利号码。但是， $61152$ 虽然含有 $6$ 和 $2$ ，但不是 $62$ 连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照区间号，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对 $n, m$ ，如果遇到都是 $0$ 的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Example

样例输入

1 100
0 0

样例输出

Hint

对于全部数据， $0 < n \leq m < 10^{7}$ 。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=11;
int f[maxn][maxn];
void inint(){
    for(int i=0;i<=9;i++){
        if(i!=4) 
            f[1][i]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<=9;j++){
            if(j==4){
                continue;
            }
            for(int k=0;k<=9;k++){
                if(k==4||(j==6&&k==2))
                    continue;
                f[i][j]+=f[i-1][k];
            }
        }
    }
}
int dp(int n){
    if(n==0){
        return 1;
    }
    vector<int>nums;
    while(n){
        nums.push_back(n%10),n/=10;
    }
    int last=0,ans=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        for(int j=0;j<x;j++){
            if(j==4||(last==6&&j==2)) continue; 
            ans+=f[i+1][j];
        }
        if(x==4||(last==6&&x==2)) break;
        last=x;
        if(!i){
            ans++;
        }
    } 
    return ans;
}
int main(){
    int l,r;
    inint(); 
    while(cin>>l>>r){
        if(l==0&&r==0){
            break;
        }  
        cout<<dp(r)-dp(l-1)<<endl;
    }
}

#include<vector>#include<iostream>using namespace std;
const int N = 100;
int f[N][N];int u[N];
//根据题目要求来预处理f[i][j]void init() {
}//计算[0,n]符合f(x)的个数int dp(int n) {//如果L可以取到0的话，特判-1if (n == -1) return 0;//特判0if (n == 0) return 0 / 1;
//用于把每位的数字提取出来vector<int> vt;while (n) vt.push_back(n % 10), n /= 10;
//res记录返回值，last保留前缀的信息int res = 0, last = 0;for (int i = vt.size() - 1; i >= 0; i--) {//第一种放法for (int j = 0; j < vt[i]; j++) {if (true) res += f[][];}//第二种放法就是vt[i]本身，特判vt[i]是否和法，不合法直接退出就好if (false) break;}
//返回答案return res;}int main() {
//预处理需要的数据init();
int l, r;while (cin >> l >> r) {//技巧一cout << dp(r) - dp(l - 1) << endl;}return 0;}

#pragma GCC optimize(2)#include<bits/stdc++.h>using namespace std;typedef long long ll;//不降数inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}const int maxn=15;int f[maxn][maxn];//一共有i位且最高位是j的方案数 void inint(){for(int i=0;i<=9;i++){f[1][i]=1;}for(int i=1;i<maxn;i++){for(int j=0;j<=9;j++){for(int k=j;k<=9;k++){ f[i][j]+=f[i-1][k];//处理那种递增数的个数 }}}}int shudp(int n){if(n==0){return 1;}vector<int>num;while(n){num.push_back(n%10);n/=10;}int last=0,ans=0;for(int i=num.size()-1;i>=0;i--){int x=num[i];for(int j=last;j<x;j++){ans+=f[i+1][j];}if(x<last){break;}last=x;if(i==0){//递归到最后 ans++;}}return ans; }int main(){int l,r;inint();while(cin>>l>>r){cout<<shudp(r)-shudp(l-1)<<endl;} }