专门做优选的网站,wordpress建站详细教程视频,第一次装wordpress,建站的注意事项[SCOI2009] windy 数
题目背景
windy 定义了一种 windy 数。
题目描述
不含前导零且相邻两个数字之差至少为 2 2 2 的正整数被称为 windy 数。windy 想知道#xff0c;在 a a a 和 b b b 之间#xff0c;包括 a a a 和 b b b #xff0c;总共有多少个 windy 数在 a a a 和 b b b 之间包括 a a a 和 b b b 总共有多少个 windy 数
输入格式
输入只有一行两个整数分别表示 a a a 和 b b b。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
1 10样例输出 #1
9样例 #2
样例输入 #2
25 50样例输出 #2
20数据规模与约定
对于全部的测试点保证 1 ≤ a ≤ b ≤ 2 × 1 0 9 1 \leq a \leq b \leq 2 \times 10^9 1≤a≤b≤2×109。
原题
洛谷P2657——传送门
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;const int mod 2e9 6; // 本题无用仅是因为懒得删int dp[20][20], a[20]; // dp记录[pos][pre_num]状态下的满足条件的个数a[]记录数字串
int dfs(int pos, int pre_num, bool bound, bool st) // pos为此时的位置pre_num为上一位的数字bound表示前面每一位是否都是上界st表示是否前面全是0
{if (pos 0) // 枚举完每一位时返回return 1;if (!bound dp[pos][pre_num] ! -1) // 不是位于上界就可以利用前面dfs已经求出的答案-1表示前面已经求出该答案return dp[pos][pre_num];int max_num; // 可枚举的该位的数的上界if (bound)max_num a[pos];elsemax_num 9;int res 0; // 统计此时的答案for (int i 0; i max_num; i){if (abs(i - pre_num) 2){if (st i 0) // 如果前面全是0并且该位也是0那么pre_num依旧设置为-6表示后面接任意数字都不受“相邻两个数字之差至少为2”这个限制res (res dfs(pos - 1, -6, bound (i a[pos]), 1)) % mod;elseres (res dfs(pos - 1, i, bound (i a[pos]), 0)) % mod;}}if (!bound !st) // 没在边界时记录下该状态对应的答案dp[pos][pre_num] res;return res;
}
int solve(int x)
{memset(dp, -1, sizeof(dp)); // 将dp数组初始化为-1表示对应状态的答案目前还未计算出int len 0; // 数字长度while (x){a[len] x % 10;x / 10;}return dfs(len, -6, 1, 1); // pre_num设置为-6表示后面接任意数字都不受“相邻两个数字之差至少为2”这个限制
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int a, b;cin a b;cout solve(b) - solve(a - 1); // ans[a,b]即为ans[0,b]-ans[0,a-1]return 0;
}
