优美数

Description

如果一个数中只有少于三个数字是非零的，那么我们称这个数为优美数，我们定义这个优美数的优美程度为这个数所有数字相加的和。 例如优美数有4，200000，10203，其中4的优美度是4，200000的优美度是2，10203的优美度是6. 数字4231，102306，7277420000，就不是啰。

 

现在问在【L，R】中，有多少个优美度为x的优美数。

Input

 T组数据，T<=5e4. 第一行为组数T。 接下来T行，每组输入L，R，x。1<=L <= R <= 3e18;

 

Output

 每行输出一个对应的答案

 

Sample Input

4 1 1000 1 1024 1024 7 65536 65536 15 1 1000000000 20

Sample Output

4 1 0 3024

HINT

C++版本一

#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std;typedef long long ll;const int maxn = 3e6+9;int tot = 0;vector<ll>mp[30];int cnt(ll x){int res = 0;while(x>0){res += x%10;x/=10;}return res;}set<int>sss;void dfs(ll x,int cur,int num){if(cur>19||num > 3)return;if(num<=3){int tmp = cnt(x);mp[tmp].pb(x);// tot++;sss.insert(tmp);// if(cnt(x) == 50)cout<<x<<endl;}for(int i=0;i<=9; i++){if(i==0)dfs(x*10ll, cur+1,num);else dfs(x*10ll + i, cur+1,num+1);}}int find1(ll x,int id){int le = 0,ri = mp[id].size() - 1;int res = ri+1;while(le <= ri){int mid = (le + ri)>>1;if(mp[id][mid] < x){le = mid+1;}else{res = mid; ri = mid - 1;}}return res;}int find2(ll x,int id){int le = 0,ri = mp[id].size() - 1;int res = 0;while(le <= ri){int mid = (le + ri)>>1;if(mp[id][mid] > x){ri = mid - 1;}else {res = mid;le = mid + 1;}}return res;} int main(){// freopen("data.in","r", stdin);// freopen("output.out","w",stdout);for(int i=1; i<=9; i++)dfs(i,1,1);//tot = 720423for(int k : sss){//27次sort(mp[k].begin(),mp[k].end());}int t;scanf("%d", &t);while(t--){ll l,r;int x;scanf("%lld%lld%d", &l, &r, &x);if(x >= 28){puts("0");}else if(l<r){int t1 = find1(l,x);int t2 = find2(r,x);printf("%d\n",t2 - t1 + 1);}else if(l==r){int t1 = lower_bound(mp[x].begin(),mp[x].end(),l) - mp[x].begin();if(t1<mp[x].size() && mp[x][t1] == l)puts("1");else puts("0");}}return 0; }

C++版本二

#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std; #define se second #define fi first #define ll long long #define Pii pair<int,int> #define Pli pair<ll,int> #define ull unsigned long long #define pb push_back const int N=1e4+10; const int INF=0x3f3f3f3f; const int mod=1e9+7; using namespace std; int a[30]; ll dp[20][30][4][30]; int k; ll dfs(int pos,int now,int num,bool limit){if(num > 3) return 0;if(pos==-1) return now == k;if(!limit && dp[pos][now][num][k]!=-1) return dp[pos][now][num][k];int up=limit?a[pos]:9;ll ans=0;for(int i=0;i<=up&&now+i<=k;++i){ans+=dfs(pos-1,now+i,num+(i!=0),limit&&i==a[pos]);}if(!limit) dp[pos][now][num][k]=ans;return ans; } ll solve(ll x){int pos=0;if(x==0)return 0;while(x){a[pos++]=x%10;x/=10;}return dfs(pos-1,0,0,1); } int main(){ // freopen("data1.in", "r", stdin); // freopen("ac.out", "w", stdout);memset(dp,-1,sizeof(dp));int T;scanf("%d",&T);while(T--){ll l,r;scanf("%I64d%I64d%d",&l,&r,&k);if(k>27)printf("0\n");else printf("%I64d\n",solve(r)-solve(l-1));}return 0; }

 

总结

以上是生活随笔为你收集整理的优美数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。