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

BZOJ 1833 ZJOI 2010 count 數字計數 數位DP

編輯:C++入門知識

BZOJ 1833 ZJOI 2010 count 數字計數 數位DP


題目大意:問0~9這10個數字在[l,r]中出現過多少次。

 

思路:數位DP。以前只是聽說過,並沒有寫過,寫了才發現好鬧心啊。。

預處理一個數組,f[i][j][k]表示長度為i,開頭為j,數字k出現的次數。

對於一個數kXXXXXX,我們先處理1~999999,然後處理1000000~kXXXXXX

前面的東西很規則,可以直接調用f數組來解決。

對於後面不太規則的東西,按位處理。總之就是亂搞,我也不太懂說不明白。。。

 

CODE:
 

#include 
#include 
#include 
#include 
using namespace std;

long long f[15][10][10],power[15];
long long a[10],b[10];

void Work(long long x,long long arr[])
{
	long long temp = x;
	int len = 0;
	static int digit[15];
	memset(digit,0,sizeof(digit));
	while(x)	digit[++len] = x % 10,x /= 10;
	x = temp;www.Bkjia.com
	for(int i = 1; i < len; ++i)
		for(int j = 1; j <= 9; ++j)
			for(int k = 0; k <= 9; ++k)
				arr[k] += f[i][j][k];
	for(int i = len; i; --i) {
		for(int j = 0; j < digit[i]; ++j) {
			if(!j && i == len)	continue;
			for(int k = 0; k <= 9; ++k)
				arr[k] += f[i][j][k];
		}
		arr[digit[i]] += x % power[i] + 1;
	}
}

int main()
{
	power[1] = 1;
	for(int i = 2; i <= 12; ++i)
		power[i] = power[i - 1] * 10;
	for(int i = 0; i <= 9; ++i)
		f[1][i][i] = 1;
	for(int i = 2; i <= 12; ++i)
		for(int j = 0; j <= 9; ++j)
			for(int k = 0; k <= 9; ++k) {
				for(int z = 0; z <= 9; ++z)
					f[i][k][z] += f[i - 1][j][z];
				f[i][k][k] += power[i - 1];
			}
	long long l,r;
	scanf("%lld%lld",&l,&r);
	Work(r,a),Work(l - 1,b);
	for(int i = 0 ; i <= 9; ++i)
		printf("%lld%c",a[i] - b[i]," \n"[i == 9]);
	return 0;
}


 

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