E 简洁的数
简洁的数
https://ac.nowcoder.com/acm/contest/17162/E
E 简洁的数
- 题意:给定区间,求区间内不超过个数位在间的数有多少个
- 区间,将区间转换为求解,但是因为这里,所以这样转换不太方便。注意到判断单个数是否合法比较容易,就可以转换为,并且单独判定是否合法。
- 对于判定区间中有多少合法的数,我们去从高到低去枚举数位,并判定合法情况计数
- 将按数位从低到高分解,并且存入中,其中代表第位的数位,代表第位时,有个非的数的数字的个数
- 从高到低去枚举数位,设当前枚举的位为,为了确保枚举的数小于,我们需要知道枚举的位上的数字是否等于,若不等于,则位的数可以取,否则取
- 对于没有任何限制的数,我们将其记忆化使用。反之直接枚举
#include <bits/stdc++.h> using namespace std; #define int unsigned long long int dp[30][5], num[30];//记忆化,存储数位 //num[i]代表数字的第i位 int dfs(int now, int lim, int cnt) {//从高到低位枚举 if(cnt > 3) return 0;//合法性判断 if(!now) return 1;//此数合法 if(!lim && dp[now][cnt]) return dp[now][cnt]; int Ceil = lim ? num[now] : 9;//确定上界 int ans = 0; for(int i = 0; i <= Ceil; ++i) { ans += dfs(now - 1, lim && (i == num[now]), cnt + (i != 0)); }if(!lim) dp[now][cnt] = ans;//记忆化 return ans; } int solve(string x) { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= x.size(); ++i) num[i] = x[x.size() - i] - '0'; return dfs(x.size(), 1, 0); } signed main() { string a, b; while(cin >> a >> b) { int flag = 1, cnt = 0; for(int i = 0; i < a.size(); ++i) { if(a[i] != '0') ++cnt; if(cnt > 3) flag = 0; }//单独判定a是否可行 cout << solve(b) - solve(a) + flag << endl; } return 0; }