https://www.acwing.com/problem/content/1085/
\(此题需要注意的是要去前导零, 前面2道题可以直接把不足n位的数看成补上前导零的数, 这样做处理起来很方便, 但是此题不行.\)
\(本题如果也把不足n位的数看成补上前导零去算, last的更新会出现问题导致循环提前break,\\ 比如0157本来是windy数, 但是0和1是不满足绝对值>2的, 循坏会在此处break掉,导致结果算少了.\)
所以如何处理这个问题?
- \(先只看n位, 在依次把1到n-1位的windy数加上.\)
- \(注意预处理的数组是不用管前导零的\).
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
inline int lowbit(int x) { return x & (-x); }
#define ll long long
#define pb push_back
#define PII pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
const int N = 11;
int f[N][10];
void init() {
for (int i = 0; i <= 9; ++i) f[1][i] = 1;
for (int i = 2; i < N; ++i)
for (int j = 0; j <= 9; ++j)
for (int k = 0; k <= 9; ++k)
if (abs(j - k) >= 2)
f[i][j] += f[i - 1][k];
}
int dp(int n) {
if (!n) return 0;
vector<int> num;
while (n) num.pb(n % 10), n /= 10;
n = num.size();
int res = 0, last = -2;
// 处理n位的情况
for (int i = n - 1; i >= 0; --i) {
int x = num[i];
for (int j = i == n - 1; j < x; ++j)
if (abs(j - last) >= 2) res += f[i + 1][j];
if (abs(x - last) < 2) break;
last = x;
if (!i) ++res;
}
// 处理1到n - 1位的情况
for (int i = 1; i < n; ++i)
for (int j = 1; j <= 9; ++j)
res += f[i][j];
return res;
}
int main() {
IO;
init();
int l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << '\n';
}
© 著作权归作者所有
举报
发表评论
0/200