kl1083_显示器dpi是什么意思

全栈程序员站长

发布于 2022-09-22 11:16:27

3550

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

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

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

输入格式共一行，包含两个整数 A 和 B。

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

数据范围 1≤A≤B≤2×109

输入样例1：
1 10
输出样例1：
9
输入样例2：
25 50
输出样例2：
20

#include<bits/stdc++.h>
using namespace std;
const int N = 11;
int f[N][10];
void init(){ 
   
    for(int i = 0;i < 10;i ++)f[1][i] = 1;
    for(int i = 2;i < N;i ++){ 
   
        for(int j = 0;j < 10;j ++){ 
   
            for(int k = 0;k < 10;k ++){ 
   
                if(abs(j - k) >= 2)f[i][j] += f[i - 1][k];
            }
        }
    }
}
int dp(int a){ 
   
    if(!a)return 0;
    vector<int>nums;
    while(a)nums.push_back(a % 10),a /= 10;
    int res = 0,last = -2;
    for(int i = nums.size() - 1;i >= 0;i --){ 
   
        int x = nums[i];
        int l = (i == nums.size() - 1 ? 1 : 0);
        for(int j = l;j < x;j ++){ 
   
            if(abs(last - j) >= 2)res += f[i + 1][j];
        }
        if(i != nums.size() - 1 && abs(last - x) < 2)break;
        last = x;
        if(!i)res ++;
    }
    for(int i = nums.size() - 1;i >= 1;i --){ 
   
        for(int j = 1;j < 10;j ++)res += f[i][j];
    }
    
    return res;
}
int main(){ 
   
    init();
    int l,r;
    cin>>l>>r;
    cout<<(dp(r) - dp(l - 1))<<endl;
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168582.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https