UVA 1103 How Many O's?

题目链接：UVA-11038

题意为给定n和m，求n和m之间（包含）的所有数包含的0的个数。

思路是，用cal(x)表示小于等于x的数包含的0的个数。则答案为cal(n)-cal(m-1)。

再把求cal(x)转化为求\(\sum_i 在第i位为0的小于x的数的个数 \)。

要求在第i位为0的数的个数，我们只需要，把x的第i位设为0，然后分别i位左右两侧统计个数即可。

代码如下：

 #include"cstdio"

 #include"iostream"

 #include"cstring"

 #include"algorithm"

 #include"cstdlib"

 #include"vector"

 #include"set"

 #include"map"

 #include"cmath"

 using namespace std;

 typedef long long LL;

 const LL MAXN=;

 LL cal(LL x)

 {

     LL ans=;

     LL rgt=;

     LL ten=;

     while(x>=)

     {

         LL p=x%;

         x/=;

         if(p!=)

             ans+=x*ten;

         else

             ans+=(x-)*ten + (rgt+);

         rgt=rgt+ten*p;

         ten*=;

     }

     return ans;

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in.txt","r",stdin);

     // freopen("out.txt","w",stdout);

 #endif

     LL n,m;

     while(scanf("%lld%lld",&m,&n)== && (n!=- || m!=-))

     {

         if(m==) printf("%lld\n",cal(n));

         else printf("%lld\n",cal(n)-cal(m-));

     }

     return ;

 }

巴特西

UVA 1103 How Many O's?

最新文章

热门文章