2019暑假集训 windy数

题目描述

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

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

输入

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

输出

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

样例输入

样例输入 1

1 10

样例输入 2

25 50

样例输出

样例输出 1

9

样例输出 2

20

提示

20%的数据，满足1<=A<=B<=1e6；
100%的数据，满足1<=A<=B<=2e9。

又是一道裸的数位dp，但是应当注意，为了区分前导0和中间0的区别，我们将前导0看作11，

这样可以防止前导0后面不能放置1（因为差小于2），这样即可判断每一个0前面是否为前导0，若是，则该位为前导0

上代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define olinr return

#define _ 0

#define love_nmr 0;

using namespace std;

int digit[],dp[][],idx,a,b;

int DP(int pos,int statu,int limit)

{

    if(!pos)return ;

    if(!limit&&~dp[pos][statu])return dp[pos][statu];

    int res=;

    int end=limit?digit[pos]:;

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

    {

        if(abs(statu-i)<)continue;//差为2

        if(statu==&&i==)res+=DP(pos-,,limit&&i==end);//前导0

        else res+=DP(pos-,i,limit&&i==end);

    }

    if(!limit)dp[pos][statu]=res;

    return res;

}

int solve(int num)

{

    memset(dp,-,sizeof dp);

    memset(digit,,sizeof digit);

    idx=;

    int temp=num;

    while(temp>)

    {

        digit[++idx]=temp%;

        temp/=;

    }

    return DP(idx,,);

}

int main()

{

    scanf("%d%d",&a,&b);

    printf("%d",solve(b)-solve(a-));

    olinr ~~(^_^)*love_nmr

}

巴特西

2019暑假集训 windy数

最新文章

热门文章