专栏文章

题解：P13085 [SCOI2009] windy 数（加强版）

LLinkCatTree
P13085题解参与者 10已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@miozdiqt
此快照首次捕获于
2025/12/03 03:38
3 个月前
此快照最后确认于
2025/12/03 03:38
3 个月前
查看原文
来水题解了。
由于 a,ba,b 范围较大，直接搜索肯定是不行的，考虑数位 dp。为方便，以下“第 ii 位”均表示从高位开始的第 ii 位（如最高位为“第一位”）。
令 f[i][j]f[i][j] 表示 ii 位且以最高位为数字 jj 的 windy 数的个数。显然 f[i][j]f[i][j] 可以通过枚举第二位的数字得到：f[i][j]=∑k=max⁡(j−2,0)min⁡(j+2,9)f[i−1][k]\displaystyle f[i][j]=\sum_{k=\max(j-2,0)}^{\min(j+2,9)} f[i-1][k]，初始状态为 f[1][i]=1(1≤i≤9)f[1][i]=1(1 \leq i \leq 9)。
接下来考虑如何计算 aa 到 bb 之间的 windy 数的个数。我们可以把答案拆成两个部分：小于等于 bb 的 windy 数个数与小于 aa 的 windy 数个数之差。我们发现这两部分是相似的（小于 aa 即为小于等于 a−1a-1），只需要考虑如何计算小于等于某个数的 windy 数个数。
假设我们要求小于等于一个数 aa 的 windy 数个数，设其为 mm 位，其第 ii 位表示为 rir_i。首先考虑位数比 mm 小的数中有多少个 windy 数：∑i=1m−1∑j=19f[i][j]\displaystyle \sum_{i=1}^{m-1}\sum_{j=1}^9 f[i][j]。接着我们考虑有 mm 位但首位小于 r1r_1 的 windy 数：∑j=1r1−1f[m][j]\displaystyle \sum_{j=1}^{r_1-1}f[m][j]。
最后考虑 mm 位且首位为 r1r_1 的 windy 数,这时我们需要考虑第二位的取值（因为第二位不能随便取，不能使用 f[m][r1]f[m][r_1] 来计算个数）。类似上面的，枚举第二位小于 r2r_2 的（且小于等于 r1−2r_1-2）：∑j=1min⁡(r2−1,r1−2)f[m−1][j]\displaystyle \sum_{j=1}^{\min(r_2-1,r_1-2)} f[m-1][j]，然后考虑第二位为 r2r_2（如果 r1r_1 和 r2r_2 满足 windy 数的标准），枚举第三位的取值……
总的来说，如果 aa 的前 ll 位均满足 windy 数的性质（相邻两位之差大于等于 rr），那么小于等于 aa 的 windy 数个数为：
∑i=1m−1∑j=19f[i][j]+∑i=1l+1∑j=1min⁡(ri−1,ri−1−2)f[i][j]\displaystyle \sum_{i=1}^{m-1}\sum_{j=1}^9 f[i][j]+\sum_{i=1}^{l+1}\sum_{j=1}^{\min(r_i-1,r_{i-1}-2)}f[i][j]
计算 ff 的时间复杂度为 O(n2m)\mathcal{O}(n^2m)，计算小于等于某个数的 windy 数个数的时间复杂度为 O(nm)\mathcal{O}(nm)（其中 nn 为数字个数即 1010，mm 为数字位数），空间复杂度为 O(nm)\mathcal{O}(nm)。
代码如下，仅供参考：
CPP
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

ull f[20][10],power[20];
void init() {
	power[0]=1;
	for(int i=1;i<=19;i++) power[i]=power[i-1]*10;
	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(j-k)>=2)
					f[i][j]+=f[i-1][k];
	return ;
}
ull solve(ull x) {
	int w=0,y,pre;
	ull ans=0;
	while(power[w]<=x) w++;
	for(int i=1;i<w;i++)
		for(int j=1;j<=9;j++)
			ans+=f[i][j];
	y=x/power[w-1];
	for(int j=1;j<y;j++) ans+=f[w][j];
	pre=y,x%=power[w-1];
	for(int i=w-1;i>=1;i--) {
		y=x/power[i-1];
		for(int j=0;j<y;j++)
			if(abs(j-pre)>=2)
				ans+=f[i][j];
		if(abs(pre-y)<2) break;
		pre=y,x%=power[i-1];
	}
	return ans;
}

int main() {
	ull a,b;
	cin>>a>>b;
	init();
	cout<<solve(b+1)-solve(a)<<endl;
	return 0;
}

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...