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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2656][Zjoi2012]数列(sequence)  

2014-12-27 16:54:26|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2656: [Zjoi2012]数列(sequence)

Orz神犇眼里   记忆化==暴力
高精度都写不对了QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 500+10;
int n,m,data[N],last[N];
const int LEN = 10000;
char tstr[N];
struct Big{
Big(int x=0){if(x==0){d[0]=1;d[1]=0;return;}for(d[0]=0;x;x/=LEN)d[++d[0]] = x%LEN;}
int d[N];
void init(){
scanf("%s",tstr+1);int len = strlen(tstr+1);
d[0]=0;int tmp;
for(int i=0;i<len;i++){
if(i % 4==0)d[++d[0]]=0,tmp=1;
d[d[0]]=d[d[0]]+tmp*(tstr[len-i]-'0');
tmp*=10;
}
}
void print(){printf("%d",d[d[0]]);for(int i=d[0]-1;i;i--)printf("%04d",d[i]);}
}s,A,B;
Big operator + (const Big &a,const Big &b){
Big c;
c.d[0] = max(a.d[0],b.d[0])+1;
for(int i=1;i<=c.d[0];i++)c.d[i] = 0;
for(int i=1;i<=c.d[0]-1;i++){
c.d[i] += a.d[i]+b.d[i];
if(c.d[i]>=LEN){
c.d[i+1]=c.d[i]/LEN;
c.d[i]%=LEN;
}
}
while(c.d[c.d[0]]==0 && c.d[0]>1)c.d[0]--;
return c;
}
int scan(){int i=0;scanf("%d",&i);return i;}
typedef Big BIG;
BIG f[N][2];
void div2(BIG &a){
for(int i=a.d[0];i;i--){
if(i>1 && (a.d[i]&1))a.d[i-1]+=LEN;
a.d[i]/=2;
}
while(a.d[a.d[0]]==0 && a.d[0]>1)a.d[0]--;
}
void getda(BIG &a){
data[0]=0;
while(!(a.d[0]==1 && a.d[1]==0)){
data[++data[0]] = (a.d[1]&1);
div2(a);
}
for(int i=1;i*2<=data[0];i++)swap(data[i],data[data[0]-i+1]);
}
int main(){
int i,j;
int nn = scan();
while(nn--){
s.init();
//s.print();printf("\n");
getda(s);
//for(i=1;i<=data[0];i++)printf("%d ",data[i]);printf("\n");

for(i=1;i<=data[0];i++)
if(data[i]==0)last[i]=0;
else last[i] = last[i-1]+1;
//for(i=1;i<=data[0];i++)printf("%d ",last[i]);printf("\n");
f[1][0] = BIG(0);
f[1][1] = BIG(1);
//f[1][1].print();printf("\n");
last[data[0]+1]=0;

//DP
for(i=2;i<=data[0]+1;i++){
f[i][0] = f[i-1][data[i-1]];
if(i-1-last[i-1]==0)f[i][1] = Big(1)+f[i-1][data[i-1]];
else f[i][1] = f[i-1-last[i-1]][1]+f[i-1][data[i-1]];
//f[i][0].print();printf(" ");f[i][1].print();printf("\n");
}
f[data[0]+1][0].print();printf("\n");
}
return 0;
}

题解:
DP
看到式子和2有关,所以转成二进制。
随便看几个数之后发现任意一个你需要的f(x)的x都一定是n二进制表示的某个前缀加上0/1
所以状态f[i][j]表示第i位是j(注意这里不是加上j),前i-1位和n的相同。
因为二进制数10111+1=11000所以需要预处理一个数组last来快速的得到进位的情况。
1 0 1 0 1 1 1 0 [n]
1 0 1 0 1 2 3 0 [last]
那么转移方程就是
f[i][0] = f[i-1][a[i-1]]
if ((i-1)-last[i-1]>0f[i][1] = f[(i-1)-last[i-1]][1]
else f[i][1] = f[i-1][a[i-1]]+1
a[i]是n二进制表示的第i位
其中(i-1)-last[i-1]如果为0就说明当前的数是1111这样,加1之后就会进位,变成f(10000)=f(1)=1
同时也说明直接记忆化搜索的复杂度是logn的,但是实际上是100*logn,因为高精度要进行逐位比较大小
  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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