UVA 1640（DFS）

时间：2023-03-08 20:52:14

UVA 1640（DFS）

题意：给你a,b两个数 问你a b区间中0 9出现的次数

其实就是求1-n中0-9出现的次数 ans[n]   答案就是ans[b]-ans[a-1]

怎么求的话看代码吧

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<string.h>

 #include<set>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<map>

 #include<cmath>

 typedef long long ll;

 typedef unsigned long long LL;

 using namespace std;

 const double PI=acos(-1.0);

 const double eps=0.0000000001;

 const int N=+;

 const ll mod=1e9+;

 const int INF=0x3f3f3f3f;

 int a[N];

 int b[N];

 int ans[N];

 void DFS(int n,int m){

     int x=n/;

     int y=n%;

     for(int i=;i<=;i++)ans[i]=ans[i]+x*m;

     for(int i=;i<=y;i++)ans[i]=ans[i]+m;

     if(x==)return;

     DFS(x-,m*);

     while(x){

         int t=x%;

         ans[t]=ans[t]+m*(y+);

         x=x/;

     }

 }

 int main(){

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

         if(n==&&m==)break;

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(ans,,sizeof(ans));

         int t1=;

         int t2=;

         if(n>m)swap(n,m);

         DFS(n-,);

         for(int i=;i<=;i++)a[i]=ans[i];

         memset(ans,,sizeof(ans));

         DFS(m,);

         for(int i=;i<=;i++)b[i]=ans[i];

         for(int i=;i<=;i++)cout<<b[i]-a[i]<<" ";

         cout<<b[]-a[]<<endl;

     }

 }

相关文章