程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3286 How many 0's?(數位dp)

POJ 3286 How many 0's?(數位dp)

編輯:C++入門知識

POJ 3286 How many 0's?(數位dp)


題意

輸入n,m,求n~m范圍內的所有數字中,0出現的總數是多少。

思路

用2034做個例子。
枚舉0在個十百千位上出現的次數
個:個位為0時,後面不需要考慮,只需考慮前面,因為0比4小,所以前面即使取到最大也不會過限,所以前面可以是1~203(因為當前位是0,所以前面不能是0)。一共203種。
十:十位為0時,前面取1~20,後面取0~9。一共123*10種。
百:百位為0時,因為0與當前位上限0相等,所以前面取1時,後面可以取0~99,前面取2時,後面只能取0~34。一共1*100+35種。
千位顯然不能為0,所以總數為0。
把上述思想轉化為代碼即可。

代碼

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

const int N = 10009;
#define LL long long
LL p[20];

void init()
{
    p[0] = 1;
    for(int i=1; i<18; i++)
        p[i] = p[i-1]*10;
}

LL solve(LL x)
{
    if(x == -1)
        return -1;
    LL ans = 0;
    for(int i=1; ; i++)
    {
        LL l = x/p[i];
        LL r = x%p[i-1];
        LL now = x%p[i]/p[i-1];
        if(now > 0)
            ans += l*p[i-1];
        else
            ans += (l-1)*p[i-1] + r+1;
        if(p[i] > x)
            break;
    }
    return ans;
}

int main()
{
    LL n, m;
    init();
    while(cin>>n>>m && (n!=-1 || m!=-1))
        printf("%lld\n", solve(m) - solve(n-1));
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved