[SCOI2009] windy 数

题目背景

windy 定义了一种 windy 数。

题目描述

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 $a$ 和 $b$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1 10

样例输出 #1

9

样例 #2

样例输入 #2

25 50

样例输出 #2

20

提示

数据规模与约定

对于全部的测试点，保证 $1\le a\le b\le 2\times 10^9$。

我们要学会画这个图

#include<bits/stdc++.h>
using namespace std;const int N = 12;int f[N][10];
int a[N];// 前置处理
void init() {for (int i = 0; i < 10; i++) f[1][i] = 1;for (int i = 2; i < 12; i++) {for (int j = 0; j < 10; j++) {for (int k = 0; k < 10; k++) {if (abs(j - k) >= 2) f[i][j] += f[i - 1][k];   // 只有符合的才会加上来}}}//cout << "输出f" << endl;}int dp(int x) {if (!x) return 0;int cnt = 0;while (x){a[++cnt] = x % 10, x /= 10;}int res = 0, last = -2;for (int i = cnt; i > 0; i--) {  // 从高位进行处理int now = a[i];for (int j = (i == cnt); j < now; j++) // 最高位要从1开始{if (abs(j - last) >= 2) res += f[i][j];}if (abs(now - last) < 2) break; // 如果不满足定义，就break,就没有分支了last = now;if (i == 1) res++;}// 如果答案有前导零for (int i = 1; i < cnt; i++) {for (int j = 1; j <= 9; j++) {res += f[i][j];}}return res;
}int main() {init();int l, r;cin >> l >> r;cout << dp(r) - dp(l - 1);return 0;
}

[ZJOI2010] 数字计数

题目描述

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

仅包含一行两个整数 $a,b$，含义如上所述。

输出格式

包含一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。

样例 #1

样例输入 #1

1 99

样例输出 #1

9 20 20 20 20 20 20 20 20 20

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $a\le b\le 10^6$；
• 对于 $100\%$ 的数据，保证 $1\le a\le b\le 10^{12}$。

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r, dp[N], mi[N];
ll ans1[N], ans2[N];
int a[N];void solve(ll n, ll *ans) {ll tmp = n;int len = 0;while (n) a[++len] = n % 10, n /= 10;for (int i = len; i >= 1; --i) {for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;ans[0] -= mi[i - 1];}
}int main() {scanf("%lld%lld", &l, &r);mi[0] = 1ll;for (int i = 1; i <= 13; ++i) {dp[i] = dp[i - 1] * 10 + mi[i - 1];mi[i] = 10ll * mi[i - 1];}solve(r, ans1), solve(l - 1, ans2);for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);return 0;
}

度的数量