老司机的奇怪noip模拟T2-huangyueying

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

2. 黄月英
（huangyueying.cpp/c/pas ）
【问题描述】
xpp 每天研究天文学研究哲学，对于人生又有一些我们完全无法理解的思考。
在某天无聊学术之后， xpp 打开了 http://web.sanguosha.com，准备用他心爱的黄月英
虐人。进入了八人身份局，作为一位主公，xpp 果断选了黄月英，用黄月英挑 7 人。
xpp 为什么喜欢黄月英这个武将呢？因为集智是个很牛逼的技能。
集智——每当你使用一张非延时类锦囊（在它结算之前）你可以立即摸一张牌。
可见集智这个技能如果用得好那么牌是摸不完的。于是 xpp 把 7 个人全部轻松干掉。
虽然 xpp 的集智永远都能摸锦囊，但是他想到了这样一个问题：由于黄月英是一个富有
智慧的人，所以 xpp 也要想一个富有智慧的问题，具体说来，他对牌上的数字产生了兴趣，
于是他想知道，牌上每个数字出现过多少次。
当然，要算牌上的数字太简单了。所以 xpp 要扩大范围。
xpp 正在考虑这样一个问题：从一个数字 a 到另一个数字 b 之间，从 0 到 9 的每个数字
出现过多少次。
xpp 智商过于强大，不屑于想此等低端问题，然后你就要把这道题做出来。
【输入】
输入文件名为 huangyueying.in。
共一行，每行两个整数，分别为 a，b。
【输出】
输出文件名为 huangyueying.out。
输出共一行，包含 10 个整数，分别代表从 0 到 9 的数字各出现过多少次。
【输入输出样例】
huangyueying.in

24 69

huangyueying.out

4 4 10 14 15 15 15 5 5 5
【数据范围】
对于 30%的数据，a≤b≤1000000。
对于 100%的数据，a≤b≤10^12。

————————————————题解

一道极为水的数位dp，但我一直没调出来

原先统计的时候没有统计前缀0，单纯算每个数，觉得去前导0太麻烦，然后就再也调不通了，后来看题解发现其实去的话也不是那么麻烦……然后就过了

【老司机的数据十分坑】

就是我们算4997，我们加上000-999（搞掉前缀0），加上1000-1999，加上2000-2999，加上3000-3999，加上998个4，然后我们再搞下一位……第一位4我们可以扔掉不管

正确性写个暴力对拍就知道了

#include <iostream>
#include <string.h>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>
#define ivorysi
#define mo 10007
#define siji(i,x,y) for(int i=(x);i<=(y);i++)
#define gongzi(j,x,y) for(int j=(x);j>=(y);j--)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);i++)
#define sigongzi(j,x,y) for(int j=(x);j>(y);j--)
#define ivory(i,x) for(int i=head[x];i;i=edge[i].next)
#define pii pair<int,int>
#define fi first
#define se second
#define inf 10000000
using namespace std;
typedef long long ll;
ll dp[][][];//dp(i,j,k)i位数，j开头，k的个数
ll num[]={//为啥我sb到打了这个表
,
,
,
,
,
,
,
,
,
1000000000LL,
10000000000LL,
100000000000LL
};
void init() {
siji(i,,) {
dp[][i][i]=;
}
siji(i,,) {
siji(j,,) {
siji(k,,) {
siji(h,,) {
dp[i][j][k]+=dp[i-][h][k];
}
}
dp[i][j][j]+=num[i-];
}
}
siji(i,,) {
siji(j,,) {
siji(k,,) {
dp[i][j][k]+=dp[i][j-][k];
}
}
}
}
ll a,b;
ll ansa[],ansb[];
void query(ll c,ll *arr) {
if(c==-) return ;
ll tmp=c;
int len=,x[];
while(tmp) {
x[++len]=tmp%;
tmp/=;
}
gongzi(i,len,) {
if(x[i]!=) {
siji(k,,){
arr[k]+=dp[i-][][k];
}
if(i==len) siji(k,,i-) arr[]-=num[k];
/*
假如我们做的是000-999
我们要搞掉000-009两次0
搞掉010-099一次0
这要合起来我们搞一遍000-099一次0（100个0）
搞000-009一次0（10个0）
*/
if(i!=len)arr[]+=num[i-];
}
xiaosiji(p,,x[i]) {
siji(k,,) {
arr[k]+=dp[i-][][k];
}
arr[p]+=num[i-];
}
arr[x[i]]+=c%num[i-]+;//加上这一位后面数
}
siji(i,,x[]) ++arr[i];
}
int main() {
#ifdef ivorysi
freopen("huangyueying.in","r",stdin);
freopen("huangyueying.out","w",stdout);
#else
freopen("f1.in","r",stdin);
#endif
scanf("%I64d%I64d",&a,&b);
init();
query(a-,ansa);
query(b,ansb);
siji(i,,) {
printf("%I64d%c",ansb[i]-ansa[i]," \n"[i==]);
}
return ;
}