【BZOJ 1833】[ZJOI2010] count 数字计数

Qizy 动态规划, 数位DP, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1833

仍然是数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 20;

LL f[MAXN][MAXN][MAXN],ans[MAXN],p[MAXN];

inline void prework(){
	p[0] = 1; p[1] = 10; 
	for (int i=2;i<=12;i++) p[i] = p[i-1]*10;
	for (int i=0;i<=9;i++) f[1][i][i] = 1;
	for (int k=2;k<=12;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				for (int h=0;h<=9;h++) {
					f[k][i][h] += f[k-1][j][h];
				}
			}
			f[k][i][i] += p[k-1];
		}
	}
}

inline void cal(LL w, int t){
	if (!w) return;
	else {
		int tot = 0, arr[20]; LL tmp = w;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=tot-1;i;i--) for (int j=1;j<=9;j++) 
			for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
		for (int i=tot;i;i--) {
			for (int j=(i==tot?1:0);j<=arr[i]-(i==1?0:1);j++) 
				for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
			if (i>1) ans[arr[i]] += (tmp % p[i-1] + 1)*t;
		}
	}
}

int main(){
	prework();
	LL a,b; cin>>a>>b;
	cal(b,1); 
	cal(a-1,-1);
	for (int i=0;i<9;i++) printf("%lld ", ans[i]);
	printf("%lld",ans[9]);
	return 0;
}

194 thoughts to “【BZOJ 1833】[ZJOI2010] count 数字计数”

  20. I have learn several good stuff here. Certainly worth bookmarking for
    revisiting. I surprise how much attempt you place to
    create the sort of fantastic informative site.

    Reply

  22. Hello, I do think your website could be having web browser compatibility issues.
    When I look at your site in Safari, it looks fine however, when opening in Internet Explorer,
    it has some overlapping issues. I merely wanted to give you a quick heads up!
    Apart from that, fantastic website!

    Reply

  42. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored
    material stylish. nonetheless, you command get bought an shakiness over that
    you wish be delivering the following. unwell unquestionably come further formerly again since
    exactly the same nearly a lot often inside case you shield this hike.

    Reply

  45. Hmm is anyone else experiencing problems with the images on this blog loading?
    I’m trying to figure out if its a problem on my end or if it’s the blog.
    Any suggestions would be greatly appreciated.

    Reply

  50. I’m not sure where you are getting your info, but good topic.

    I needs to spend a while finding out much more or understanding more.
    Thank you for fantastic information I used to be in search of this information for my mission.

    Reply

  52. Hi my loved one! I want to say that this article is amazing,
    great written and come with approximately all important infos.
    I would like to peer extra posts like this .

    Reply

  59. The subsequent time I learn a blog, I hope that it doesnt disappoint me as a lot as this one. I mean, I know it was my choice to learn, but I truly thought youd have one thing fascinating to say. All I hear is a bunch of whining about one thing that you may repair should you werent too busy in search of attention.

    Reply

  63. My brother recommended I may like this blog.
    He used to be entirely right. This publish actually made my day.
    You cann’t consider simply how much time I had spent
    for this info! Thanks!

    Reply

  80. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

    Reply

  85. This design is spectacular! You obviously know how to keep a reader entertained.

    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
    I really loved what you had to say, and more than that,
    how you presented it. Too cool!

    Reply

  95. Howdy I am so delighted I found your weblog, I really found you by accident, while I was
    researching on Bing for something else, Nonetheless I am here now
    and would just like to say kudos for a tremendous post and
    a all round thrilling blog (I also love the theme/design), I don’t have time to read through it all at the minute but I have bookmarked it and also
    added your RSS feeds, so when I have time I will be back to read
    a great deal more, Please do keep up the great work.

    Reply

  97. Hello would you mind letting me know which hosting
    company you’re working with? I’ve loaded your blog in 3 different browsers and I must say this
    blog loads a lot quicker then most. Can you suggest a good hosting provider at a fair price?
    Thank you, I appreciate it!

    Reply

  119. Currently it looks like Movable Type is the best blogging platform out
    there right now. (from what I’ve read) Is that what you’re using on your blog?

    Reply

  125. Your style is very unique compared to other folks I have read stuff from.
    Thank you for posting when you have the opportunity, Guess
    I will just book mark this page.

    Reply

  126. First of all I want to say awesome blog! I had a
    quick question in which I’d like to ask if you do
    not mind. I was curious to know how you center yourself and clear your mind before
    writing. I’ve had a tough time clearing my mind in getting my thoughts out.
    I do take pleasure in writing but it just seems like the
    first 10 to 15 minutes are usually lost just trying to figure out how
    to begin. Any recommendations or hints? Many thanks!

    Reply

  153. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
    You clearly know what youre talking about, why
    waste your intelligence on just posting videos to your site when you could
    be giving us something enlightening to read?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *