微商城网站建设方案,网站建设存在困难,江苏省建设工程交易中心网站,wordpress文章微信公众号推送题意 区间[A,B]上#xff0c;总共有多少个不含前导零且相邻两个数字之差至少为2的正整数#xff1f; 思路 状态设计非常简单#xff0c;只需要pos、limit和一个前驱数pre就可以了#xff0c;每次枚举当前位时判断是否与上一位相差2即可。一个需要注意的地方是第一位不用比较…题意 区间[A,B]上总共有多少个不含前导零且相邻两个数字之差至少为2的正整数 思路 状态设计非常简单只需要pos、limit和一个前驱数pre就可以了每次枚举当前位时判断是否与上一位相差2即可。一个需要注意的地方是第一位不用比较所以我们还需要一个flag标志记录当前pos位是不是第一位。 代码 [cpp] #include iostream #include cstdio #include cmath #include algorithm #include string #include cstring #include vector #include set #include stack #include queue #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, m) for (int i begin; i beginm; i ) using namespace std; typedef long long LL; typedef vector int VI; typedef set int SETI; typedef queue int QI; typedef stack int SI; const int oo 0x7fffffff; int dp[12][10][2]; VI num; int dfs(int pos, int pre, bool flag, int limit){ if (pos -1) return 1; if (!limit ~dp[pos][pre][flag]) return dp[pos][pre][flag]; int end limit?num[pos]:9, res 0; for (int i 0; i end; i ){ if (flag || abs(i - pre) 2){ res dfs(pos-1, i, flag(i 0),limit(iend)); } } return limit?res:dp[pos][pre][flag] res; } int cal(int x){ num.clear(); while(x){ num.push_back(x%10); x / 10; } return dfs(num.size()-1, 0, 1, 1); } int main(){ int a,b; MEM(dp, -1); while(scanf(%d %d, a, b) ! EOF){ printf(%d\n, cal(b)-cal(a-1)); } return 0; } [/cpp]转载于:https://www.cnblogs.com/AbandonZHANG/p/4114315.html
