程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1833 [ZJOI2010]count 數字計數(數位dp)

BZOJ 1833 [ZJOI2010]count 數字計數(數位dp)

編輯:C++入門知識

BZOJ 1833 [ZJOI2010]count 數字計數(數位dp)


題意

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

思路

和 POJ 3286 How many 0’s? (數位dp)的思路基本是一樣的,只是略有區別。
0和1~9要分開處理,是因為前綴0的問題。因為當某一位取0時,前面部分的數是不能為0的,而取1~9是可以前面為0的。

代碼

<code class="hljs perl">#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include<map>

using namespace std;

#define LL long long
LL p[20];
LL ans[10] = {};

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

void solve(LL x, int f)
{
    if(x == -1)
    {
        ans[0]++;
        return;
    }
    for(int k=1; k<10; k++)
    {
        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 > k)
                ans[k] += (l+1)*p[i-1]*f;
            else if(now == k)
                ans[k] += (l*p[i-1]+r+1)*f;
            else
                ans[k] += l*p[i-1]*f;
            if(p[i] > x)
                break;
        }
    }
    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[0] += l*p[i-1]*f;
        else
            ans[0] += ((l-1)*p[i-1]+r+1)*f;
        if(p[i] > x)
            break;
    }
}

int main()
{
    LL n, m;
    init();
    cin>>n>>m;
    solve(m, 1);
    solve(n-1, -1);
    for(int i=0; i<9; i++)
        printf("%lld ", ans[i]);
    printf("%lld\n", ans[9]);
    return 0;
}</map></cmath></vector></cstdlib></cstdio></cstring></algorithm></iostream></code>

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