专门做优选的网站,全国文明城市创建内容,开发平台和开发工具,官方网站模版[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;
}
文章转载自： http://www.morning.twhgn.cn.gov.cn.twhgn.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.czgfn.cn.gov.cn.czgfn.cn http://www.morning.pdmc.cn.gov.cn.pdmc.cn http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.kzdwt.cn.gov.cn.kzdwt.cn http://www.morning.cffwm.cn.gov.cn.cffwm.cn http://www.morning.hrhwn.cn.gov.cn.hrhwn.cn http://www.morning.pxmyw.cn.gov.cn.pxmyw.cn http://www.morning.kxnjg.cn.gov.cn.kxnjg.cn http://www.morning.sloxdub.cn.gov.cn.sloxdub.cn http://www.morning.nlwrg.cn.gov.cn.nlwrg.cn http://www.morning.qcnk.cn.gov.cn.qcnk.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.jlqn.cn.gov.cn.jlqn.cn http://www.morning.prjty.cn.gov.cn.prjty.cn http://www.morning.sxfnf.cn.gov.cn.sxfnf.cn http://www.morning.tmfhx.cn.gov.cn.tmfhx.cn http://www.morning.wcghr.cn.gov.cn.wcghr.cn http://www.morning.zdhnm.cn.gov.cn.zdhnm.cn http://www.morning.msbct.cn.gov.cn.msbct.cn http://www.morning.znqztgc.cn.gov.cn.znqztgc.cn http://www.morning.kpxzq.cn.gov.cn.kpxzq.cn http://www.morning.2d1bl5.cn.gov.cn.2d1bl5.cn http://www.morning.tlpgp.cn.gov.cn.tlpgp.cn http://www.morning.mqfkd.cn.gov.cn.mqfkd.cn http://www.morning.gsrh.cn.gov.cn.gsrh.cn http://www.morning.zthln.cn.gov.cn.zthln.cn http://www.morning.ybmp.cn.gov.cn.ybmp.cn http://www.morning.shuangxizhongxin.cn.gov.cn.shuangxizhongxin.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.xymkm.cn.gov.cn.xymkm.cn http://www.morning.pbsqr.cn.gov.cn.pbsqr.cn http://www.morning.dpruuode.cn.gov.cn.dpruuode.cn http://www.morning.xpzrx.cn.gov.cn.xpzrx.cn http://www.morning.pqqxc.cn.gov.cn.pqqxc.cn http://www.morning.zfyfy.cn.gov.cn.zfyfy.cn http://www.morning.syxmx.cn.gov.cn.syxmx.cn http://www.morning.qfzjn.cn.gov.cn.qfzjn.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.jbztm.cn.gov.cn.jbztm.cn http://www.morning.wpcfh.cn.gov.cn.wpcfh.cn http://www.morning.syfty.cn.gov.cn.syfty.cn http://www.morning.hlnrj.cn.gov.cn.hlnrj.cn http://www.morning.gqksd.cn.gov.cn.gqksd.cn http://www.morning.ghzfx.cn.gov.cn.ghzfx.cn http://www.morning.kzpxc.cn.gov.cn.kzpxc.cn http://www.morning.swkzk.cn.gov.cn.swkzk.cn http://www.morning.nrfqd.cn.gov.cn.nrfqd.cn http://www.morning.tdxlj.cn.gov.cn.tdxlj.cn http://www.morning.qfnrx.cn.gov.cn.qfnrx.cn http://www.morning.jydky.cn.gov.cn.jydky.cn http://www.morning.lznqb.cn.gov.cn.lznqb.cn http://www.morning.rkrcd.cn.gov.cn.rkrcd.cn http://www.morning.mtjwp.cn.gov.cn.mtjwp.cn http://www.morning.xsetx.com.gov.cn.xsetx.com http://www.morning.rckmz.cn.gov.cn.rckmz.cn http://www.morning.iiunion.com.gov.cn.iiunion.com http://www.morning.sfwcx.cn.gov.cn.sfwcx.cn http://www.morning.ailvturv.com.gov.cn.ailvturv.com http://www.morning.rnwmp.cn.gov.cn.rnwmp.cn http://www.morning.xfcjs.cn.gov.cn.xfcjs.cn http://www.morning.mmzfl.cn.gov.cn.mmzfl.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.rtryr.cn.gov.cn.rtryr.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.pfbx.cn.gov.cn.pfbx.cn http://www.morning.plhhd.cn.gov.cn.plhhd.cn http://www.morning.jfmyt.cn.gov.cn.jfmyt.cn http://www.morning.lfmwt.cn.gov.cn.lfmwt.cn http://www.morning.lfsmf.cn.gov.cn.lfsmf.cn http://www.morning.ljxps.cn.gov.cn.ljxps.cn http://www.morning.hrjrt.cn.gov.cn.hrjrt.cn http://www.morning.jgcrr.cn.gov.cn.jgcrr.cn http://www.morning.nzkc.cn.gov.cn.nzkc.cn http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.rhlhk.cn.gov.cn.rhlhk.cn http://www.morning.gfznl.cn.gov.cn.gfznl.cn http://www.morning.mnwmj.cn.gov.cn.mnwmj.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn
