luoguP2657 [SCOI2009] windy 数

luoguP2657 [SCOI2009] windy 数
- 简述题意：
- Solution:

luoguP2657 [SCOI2009] windy 数

简述题意：

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 $windy$ 数。$windy$ 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 $windy$ 数？

数据范围：$1 \le a \le b \le 2 \times 10^9$

Solution:

先设一个 $f[i][j]$ , 表示枚举到第 $i$ 位，最高位是 $j$ ，在 $[j000\cdots , j999\cdots]$ 范围内的 $windy$ 数的数量

初始状态： $f[1][i] = 1 (0 \le i \le 9) $ , 因为表示的是个数，每个f[1][i]又只能代表一个数，所以赋初值为 $1$

转移方程：

\[f[i][j] = \sum_{\mid k - j \mid \ge 2}^{} f[i - 1][k]
\]

求 $ans_{l,r}$ 时的策略：

设 $len$ 为 $r$ 的位数，$s[len]$ 中存 $r$ 的每一位

1、对于所有长度小于 $len$ 的 $f$ ， $ans += \sum_{1 \le j \le 9}^{1 \le i \le len - 1} f[i][j]$

2、对于长度等于 $len$ 且最高位小于 $s_{len}$ 的 $f$ , $ans +=\sum_{1 \le j < a_{len}} f[len][j]$

3、对于剩下的 $len - 1$ 位，我们继续执行 $2$ 操作，不过 $j \in [0, s_i)$ （因为最高位已经不为零了）

/*

Work by: Suzt_ilymics

Knowledge: 数位DP

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define LL long long

using namespace std;

LL read(){

	LL s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();	}

	while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();

	return s * w;

} 

LL l, r, ans = 0;

LL f[22][22], g[22];

LL quick_pow(LL x, LL p){

	LL res = 1;

	for( ; p; p >>= 1){

		if(p & 1) res = res * x;

		x = x * x;

	}

	return res;

}

void init(){//初始化

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

	for(int i = 2; i <= 19; ++i){

		for(int j = 0; j <= 9; ++j){

			for(int k = 0; k <= 9; ++k){

				if(abs(k - j) >= 2)

				f[i][j] = (f[i][j] + f[i - 1][k]);

			}

//			cout<<f[i][j]<<" ";

		}

//		cout<<"\n";

	}

}

LL solve(LL x){//求出ans_1 —— (x - 1)

//	cout<<"lkp ak ioi"<<endl;

	LL ans = 0, sum = 0;

	LL s[20], len = 0;

	for( ; x; x = x / 10) s[++len] = x % 10;

	for(int i = 1; i <= len - 1; ++i) {

		for(int j = 1; j <= 9; ++j){

			ans += f[i][j];

		}

	}

	for(int i = 1; i < s[len]; ++i){

		ans += f[len][i];

	}

	for(int i = len - 1; i >= 1; --i){

		for(int j = 0; j < s[i]; ++j){

			if(abs(j - s[i + 1]) >= 2) ans += f[i][j];

		}

		if(abs(s[i + 1] - s[i]) < 2) break;

	}

	return ans;

}

int main()

{

	l = read(), r = read();

	init();

	printf("%lld", solve(r + 1) - solve(l));

	return 0;

}

巴特西

luoguP2657 [SCOI2009] windy 数