题目链接

1083. Windy数

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

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

输入格式

共一行，包含两个整数 \(A\) 和 \(B\)。

输出格式

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

数据范围

\(1 \le A \le B \le 2 \times 10^9\)

输入样例1：

1 10

输出样例1：

9

输入样例2：

25 50

输出样例2：

20

解题思路

数位dp

• 状态表示：\(f[i][j]\) 表示 \(i\) 位，且最后一位为 \(j\)，且相邻两个数之间差至少为 \(1\) 的整数个数

• 状态计算：\(f[i][j]+=f[i-1][k]\)，其中 \(|j-k| \geq 2\)

则可以利用 \(f[i][j]\) 求出前 \(i\) 位满足条件的整数个数 \(s[i]\)，本题等价于求解前缀和 \(1\sim x\) 内满足条件的整数个数，求出 \(x\) 的位数 \(n\)，则对于 \(1\sim n-1\) 的位数贡献为 \(s[n-1]\)，现在只用讨论位数为 \(n\) 且不大于 \(x\) 的整数个数，类似于 1081. 度的数量，每一位每一位讨论，对于第一位需要特判，因为第一位不能为 \(0\)，而且第一位没有前面数的限制，对于小于当前位 \(A[i]\) 的数 \(j\)，同时利用 \(f[i][j]\) 数组，\(f[i][j]\) 表示的以 \(j\) 结尾的 \(i\) 位的方案数，则可以将该整数翻转，即以 \(j\) 首位的 \(i\) 位的整数的方案数，即第一位如果是 \(j\) 的贡献为 \(f[n][j]\)，对于其他位，判断是否相邻差至少为 \(2\)，如果满足条件，则枚举的 \(j\) 的贡献为 \(f[n-i+1][j]\)，另外如果该数本身就满足条件，则还需要加上该数的贡献

• 时间复杂度：\(O(10\times logw)\)

代码

// Problem: Windy数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1085/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int a,b;
int f[15][10],s[15],A[15],n;
void init()
{
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=10;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];
	for(int i=1;i<=10;i++)
		for(int j=1;j<=9;j++)s[i]+=f[i][j];
	for(int i=1;i<=10;i++)s[i]+=s[i-1];
}
int get(int x)
{
	if(x==0)return 0;
	n=0;
	do
	{
		A[++n]=x%10;
		x/=10;
	}while(x);
	reverse(A+1,A+1+n);
	int res=s[n-1];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<A[i];j++)
		{
			if(i==1)
			{
				if(j)
					res+=f[n][j];
			}
			else
			{
				if(abs(j-A[i-1])>=2)res+=f[n-i+1][j];
			}
		}
		if(i>1&&abs(A[i]-A[i-1])<2)break;
		if(i==n)res++;
	}
	return res;
}
int main()
{
    init();
    scanf("%d%d",&a,&b);
    printf("%d",get(b)-get(a-1));
    return 0;
}