注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1833][ZJOI2010]count 数字计数  

2014-12-29 21:16:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1833: [ZJOI2010]count 数字计数

大裸题,但是好久没写都不会写了……搞了好久QAQ

注意这题最后一个数字之后不要输出空格,否则会PE!!

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 20;
int n,m,data[N];
ll scan(){ll i=0;cin >> i;return i;}
struct Ans{Ans(){memset(d,0,sizeof(d));}ll d[11];};
Ans operator+(const Ans &a,const Ans &b){Ans c;for(int i=0;i<=10;i++)c.d[i]=a.d[i]+b.d[i];return c;}
Ans f[N][10][2];
Ans solve(ll n){
int i,j,k;Ans re;
if(!n)return re;
memset(f,0,sizeof(f));data[0] = 0;
while(n)data[++data[0]]=n%10,n/=10;
for(i=1;i*2<=data[0];i++)swap(data[i],data[data[0]-i+1]);
for(i=1;i<=data[0];i++){
//0
for(j=0;j<10;j++){
if(j==1)f[i-1][0][0].d[10]+=1;
if(i==1 && (j >= data[i] || j==0))continue;
else if(i==1 && j <data[i])f[i][j][0].d[10] = 1;
else{
for(k=0;k<10;k++)
f[i][j][0] = f[i][j][0] + f[i-1][k][0];
if(j<data[i])f[i][j][0] = f[i][j][0] + f[i-1][data[i-1]][1];
}
f[i][j][0].d[j] += f[i][j][0].d[10];
if(i==data[0])re = re+f[i][j][0];
}
//f[i][0][0].d[10]+=1;
//1
if(i>1)f[i][data[i]][1] = f[i][data[i]][1] + f[i-1][data[i-1]][1];
else f[i][data[i]][1].d[10]=1;
f[i][data[i]][1].d[data[i]] += f[i][data[i]][1].d[10];
if(i==data[0])re = re+f[i][data[i]][1];
}
//printf("%d\n",f[2][0][0].d[0]);
return re;
}
int main(){
int i,j;
ll a,b;
a = scan();b = scan();
Ans tmp[2];
tmp[1] = solve(b);
tmp[0] = solve(a-1);
for(i=0;i<10;i++){
cout << tmp[1].d[i]-tmp[0].d[i];
if(i<9)cout << ' ';
}
return 0;
}

题解:
数位Dp
f[i][j][]表示第i位是j的答案,最后一位表示是否有上限的限制,0是没有,1是有
每个状态存一个数组d[11]
前面0~9分别表示该数字出现的次数,d[10]存的是前面的方案个数,每次枚举j之后要f[i][j][].d[j]+=d[10]
这次是写的基本没怎么写过的递推,边界和前导零的处理各种蛋疼,但是写完了之后代码还是很短的
  评论这张
 
阅读(424)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017