标签：cnt ch last int windy dp 数位

一、算法简析

数位dp题目的特点

求某个区间 \([L,R]\) 内，满足某种性质的数的个数。

数位dp的解题技巧

技巧一

类似前缀和，转换为 \([0,R]-[0,L-1]\) 求解。分别统计两个区间内满足条件的数的个数，再作差。

技巧二

由于边界 \(R\) 的限制，首先就要保证讨论的数小于等于 \(R\)，再考虑是否满足题目要求的性质。

将边界数字 \(R\) 按数位拆分，各位数字为 \(a_i\)，共 \(n\) 位。\(R=a_na_{n-1}...a_1\)。
从高位到低位填数，对于第 \(i\) 位，边界 \(R\) 在该位为 \(a_i\)，分类讨论：

• 若填 \([0,a_i-1]\)，后面每一位可以随意填 \([0,9]\) 中的数字，都保证小于 \(R\)。
• 若填 \(a_i\)，则将该位固定为 \(a_i\)，接着讨论 \(i-1\) 位。

按照这个方法讨论数，可以保证不大于 \(R\)。

相关题目

P2657 [SCOI2009] windy 数

P2657 [SCOI2009] windy 数

题目分析

令 \(f[i][j]=\) 一共有 \(i\) 位，首位数字为 \(j\) 的windy数的个数

预统计

根据windy数的性质：不含前导零且相邻两个数字之差至少为 2 的正整数，得到转移方程

\[f[i][j]=\begin{cases} \sum_{k=0}^9{f[i-1][k]}&,~~~~i\in[2,n]~and~j\in[0,9]~and~|k-j|\ge2\\ 1&,i==1~and~j\in[0,9] \end{cases} \]

虽然windy数要求不含前导零，但在预统计时，\(j\) 可以为取 \(0\)。因为预统计是从低位向高位填数，此时首位为 \(0\)的情况，会对再高一位非零情况做出贡献。例：\(dp[5][2]\) 需要包含 \(dp[4][0]\)。因此，我们也需要统计 \(f[i][0]\) 的情况。

在根据边界 \(R\) 统计个数时，忽略前导零的情况即可。

开始统计

对于 \([0,R]\) 的windy数，我们分成两部分讨论：

• 位数为 \(n\) 的数，按上文提到的技巧二，从高位向低位讨论，注意不存在前导零。
• 位数小于 \(n\) 的数，直接累加 \(dp[i][j],~i\in[1,n-1]~and~j\in[1,9]\)。

注意，0 不是windy数。

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 12;
int A[MAX], f[MAX][MAX];

// 初始化，预统计windy数 
void init(void)
{
	for (int i = 0; i <= 9; ++i)    f[1][i] = 1;
	
	for (int i = 2; i < MAX; ++i)
		for (int j = 0; j <= 9; ++j) // 此处j可以为0，因为非首位数字可以为0 
			for (int k = 0; k <= 9; ++k)
				if (abs(k - j) >= 2)    f[i][j] += f[i - 1][k];
}

int dp(int x)
{
	if (!x)     return 0; // 不含前导0
	
	int cnt = 0;
	while (x)
	{
		A[++cnt] = x % 10;
		x /= 10;
	}
	
	int ans = 0, last = -2; // last=-2保证i=cnt,j=1时，也满足if条件 
	
	// 位数等于cnt 
	for (int i = cnt; i >= 1; --i)
	{
		int now = A[i];
		for (int j = (i == cnt); j < now; ++j) // 前导数字不为0，其它位可为0 
			if (abs(j - last) >= 2)    ans += f[i][j];
			
		if (abs(now - last) < 2)    break;
		last = now;
		if (i == 1)    ans += 1; // 特判，即x是否满足 
	}
	
	// 位数小于cnt
	for (int i = 1; i < cnt; ++i)
		for (int j = 1; j <= 9; ++j)
			ans += f[i][j]; 
	
	return ans;
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	init();
	
	int a, b;
	a = quickin(), b = quickin();
	cout << dp(b) - dp(a - 1) << endl;
	
	return 0;
}

---

完

标签：cnt,ch,last,int,windy,dp,数位
From： https://www.cnblogs.com/hoyd/p/18200724