题目描述
windy 定义了一种 windy 数. 不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数. windy 想知道,
在 A 和 B 之间, 包括 A 和 B, 总共有多少个 windy 数?
输入输出格式
输入格式:
包含两个整数, A B.
输出格式:
一个整数
输入输出样例
输入样例 #1: 复制 1 10
输出样例 #1: 复制
9
输入样例 #2: 复制 25 50
输出样例 #2: 复制
20
说明
100% 的数据, 满足 1 <= A <= B <= 2000000000 .
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstdlib>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<map>
- #include<set>
- #include<vector>
- #include<queue>
- #include<bitset>
- #include<ctime>
- #include<time.h>
- #include<deque>
- #include<stack>
- #include<functional>
- #include<sstream>
- //#include<cctype>
- //#pragma GCC optimize(2)
- using namespace std;
- #define maxn 100005
- #define inf 0x7fffffff
- //#define INF 1e18
- #define rdint(x) scanf("%d",&x)
- #define rdllt(x) scanf("%lld",&x)
- #define rdult(x) scanf("%lu",&x)
- #define rdlf(x) scanf("%lf",&x)
- #define rdstr(x) scanf("%s",x)
- #define mclr(x,a) memset((x),a,sizeof(x))
- typedef long long ll;
- typedef unsigned long long ull;
- typedef unsigned int U;
- #define ms(x) memset((x),0,sizeof(x))
- const long long int mod = 100000007;
- #define Mod 1000000000
- #define sq(x) (x)*(x)
- #define eps 1e-5
- typedef pair<int, int> pii;
- #define pi acos(-1.0)
- //const int N = 1005;
- #define REP(i,n) for(int i=0;i<(n);i++)
- typedef pair<int, int> pii;
- inline int rd() {
- int x = 0;
- char c = getchar();
- bool f = false;
- while (!isdigit(c)) {
- if (c == '-') f = true;
- c = getchar();
- }
- while (isdigit(c)) {
- x = (x <<1) + (x << 3) + (c ^ 48);
- c = getchar();
- }
- return f ? -x : x;
- }
- ll gcd(ll a, ll b) {
- return b == 0 ? a : gcd(b, a%b);
- }
- int sqr(int x) { return x * x; }
- /*ll ans;
- ll exgcd(ll a, ll b, ll &x, ll &y) {
- if (!b) {
- x = 1; y = 0; return a;
- }
- ans = exgcd(b, a%b, x, y);
- ll t = x; x = y; y = t - a / b * y;
- return ans;
- }
- */
- ll dp[20][20], ans;
- int a[maxn];
- int len;
- ll l, r;
- ll dfs(int pos, int pre, int lead, int limit) {
- if (pos> len)return 1;
- if (!limit&&dp[pos][pre] != -1)return dp[pos][pre];
- ll res = 0;
- int up = limit ? a[len - pos + 1] : 9;
- for (int i = 0; i <= up; i++) {
- if (abs(i - pre) < 2)continue;
- if (lead&&i == 0)res += dfs(pos + 1, -2, 1, limit&&i == up);
- else res += dfs(pos + 1, i, 0, limit&i == up);
- }
- if (!limit && !lead)dp[pos][pre] = res;
- return res;
- }
- ll sol(ll x) {
- len = 0;
- while (x)a[++len] = x % 10, x /= 10;
- mclr(dp, -1);
- return dfs(1, -2, 1, 1);
- }
- int main()
- {
- // iOS::sync_with_stdio(0);
- rdllt(l); rdllt(r);
- cout << (ll)sol(r) - (ll)sol(l - 1) << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2947259.html