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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3679]数字之积  

2014-09-07 19:04:22|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
神题from鸟哥(faebdc)
一开始无限蛋疼不会做
然后liangjs给了个提示就会了(其实相当于给题解了
我还是太弱
代码比较丑陋凑合着看吧- -、
按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<ctime>
using namespace std;
typedef long long LL;
LL scan(){
char cc=' ';LL re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
struct state{
int n[5],i,type;
state(){}
state(const int num[],int ii,int t):i(ii),type(t){for(int j=1;j<=4;j++)n[j] = num[j];}
};
queue <state>dui;
int yz[10][5];
int k,pri[7] = {0,2,3,5,7};
// 2 3 5 7 i
LL f[35][21][15][15][20][2],L,R;
short v[35][21][15][15][20][2];
LL make(LL n){
LL sub =0,x=n;
for(LL i=1;x;i=i*10,x/=10)
if(x%10==0)sub = i;
else if(i==sub*10&&x%10==1&&x>1)sub = i;//1111
sub*=10;//2101
if(sub)n = n/sub*sub-1;
return n;
}
short list[20];
void mlist(LL n){
for(list[0]=0;n;n/=10)
list[++list[0]] = n%10;
for(int i=1;i*2<=list[0];i++) swap(list[i],list[list[0]-i+1]);
}
LL *get (state a){
return &f[a.n[1]][a.n[2]][a.n[3]][a.n[4]][a.i][a.type];}
short *getv(state a){return &v[a.n[1]][a.n[2]][a.n[3]][a.n[4]][a.i][a.type];}
void push(){}
LL pow(int x,int k){if(k==0)return 1;return pow(x,k-1)*x;}
LL calc(state a){
LL re = 1;
for(int i=1;i<=4;i++){
if(a.n[i] > 35) printf("error");
re = re*pow(pri[i],a.n[i]);
}
return re;
}
LL getans(LL n){
if(!n)return 0;
LL ans=0,a;n=make(n);
mlist(n);
if(f[0][0][0][0][1][1]){
memset(f,0,sizeof(f));
memset(v,0,sizeof(v));
}
int lin[5]={},zero[5]={};
int last = 0;
dui.push(state(zero,1,1));
if(list[0] > 1)dui.push(state(zero,2,2));
f[0][0][0][0][1][1] = 1;
//for(int i=2;i<=list[0];i++)f[0][0][0][0][i][0] = 1;
while(!dui.empty()){
state now = dui.front(),next;dui.pop();
//if(last!=now.i&&now.i+1<=list[0])dui.push(state(zero,now.i+1,0));
LL *nowf=NULL,*nextf;short *nextv;
if(now.type!=2)nowf = get(now);
if(now.i>list[0])
{ans+=*nowf;continue;}
if(now.type==1){//limited
//limited
next = now;next.type=1;
for(int j=1;j<=4;j++)next.n[j]+=yz[list[now.i]][j];
if((a=calc(next)) <= k){
next.i++;
nextv = getv(next);
nextf = get(next);
*nextf += *nowf;
if(!*nextv)dui.push(next),*nextv=1;
}
//no limit
for(int i=1;i<list[now.i];i++){
next = now;next.type=0;
for(int j=1;j<=4;j++)next.n[j]+=yz[i][j];
if((a=calc(next)) <= k){
next.i++;
nextv = getv(next);
nextf = get(next);
*nextf += *nowf;
if(!*nextv)dui.push(next),*nextv=1;
}
}
}else if(now.type==2){//zero
for(int i=1;i<=9;i++){
next = now;next.type=0;
for(int j=1;j<=4;j++)next.n[j]+=yz[i][j];
if((a=calc(next)) <= k){
next.i++;
nextv = getv(next);
nextf = get(next);
*nextf += 1;
if(!*nextv)dui.push(next),*nextv=1;
}
}
now.i++;
if(now.i<=list[0])dui.push(now);
}else{
for(int i=1;i<=9;i++){
next = now;next.type=0;
for(int j=1;j<=4;j++)next.n[j]+=yz[i][j];
if((a=calc(next)) <= k){
next.i++;
nextv = getv(next);
nextf = get(next);
*nextf += *nowf;
if(!*nextv)dui.push(next),*nextv=1;
}
}
}

}
return ans;
}
void makeyz(){
int a;
for(int i=a=2;i<=9;i++,a=i)
for(int j=1;j<=4;j++)
while(a&&a%pri[j]==0)a/=pri[j],yz[i][j]++;
}
int main(){
//freopen("input.txt","r",stdin);
makeyz();
k=scan();L=scan();R=scan();
LL ans1,ans2;
ans1 = getans(R-1);
ans2 = getans(L-1);
printf("%lld",ans1-ans2);
return 0;
}

题解:
数位DP
最暴力的做法:f[i][j]表示当前乘积为i,第j位 显然MLE+TLE
然后发现每次转移的数都是1-9而且是乘法,分解质因数发现只有2,3,5,7四个
于是记录每个质因数的个数
则f[p_1][p_2][p_3][p_4][i]为状态
询问是[l,r)
所以算出[1,l-1][1,r-1]的答案做差即为最终答案
在实际写的时候因为要考虑上界这个蛋疼问题,所以多加一维来表示有无当前上界的限制
细节:
注意处理0的情况(把i变为j,j<=i,j不含0且最大),我因为这个wa了半天
--------------------------------------------------------------------------------------
啊其实一开始暴力的做法也可以写,因为有好多状态是无效的,所以干脆只把有效状态暴力找出来然后离散化
时间复杂度多加一个log,但是相对记录每个质因数的做法常数小,不知道能不能过- -|
  评论这张
 
阅读(79)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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