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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3780]数字统计  

2014-11-30 12:01:02|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3780: 数字统计

被Claris神犇邀请来写。。
写了一上午,感觉很有问题地过了。。
【BZOJ码长最长】成就达成
居然因为ans=0的时候没输出WA了一次。。
在头疼的情况下写了一上午- -
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 200+10;
int n,m,r;
short data[N],fina[N][2],out[N];
const int LEN = 10000;
const int MLEN = 25;
struct Big{
int d[MLEN];
Big(){memset(d,0,sizeof(d));d[0]=1;}
Big(int i){if(!i){*this=Big();return;}memset(d,0,sizeof(d));d[0]=0;for(;i;i/=LEN)d[++d[0]]=i%LEN;}
void print(){printf("%d",d[d[0]]);for(int i=d[0]-1;i>=1;i--)printf("%04d",d[i]);}
};
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;
c.d[1]=0;
for(int i=1;i<=c.d[0];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;
}else c.d[i+1]=0;
}
while(c.d[0] >1&&c.d[c.d[0]]==0)c.d[0]--;
return c;
}
Big operator - (const Big &a, const Big &b){
Big c;
c.d[0] = max(a.d[0], b.d[0]);
for(int i=1;i<=c.d[0];i++){
c.d[i] += a.d[i] - b.d[i];
if(c.d[i] < 0){
c.d[i] += LEN;
c.d[i+1]--;
}
}
while(c.d[0] >1&&c.d[c.d[0]]==0)c.d[0]--;
return c;
}
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[0] >1&&a.d[a.d[0]]==0)a.d[0]--;
}
typedef Big BIG;
//typedef long long BIG;
BIG f[N][2],pf[N][2],ans[2];
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("in.txt","r",stdin);
Big a,b;
int i,j;char cc;
int nn = scan();
m = 200;
//premake
f[1][0] = 1;
f[1][1] = 1;
pf[1][0] = 1;pf[1][1] = 0;
//pf[1][0].print();
for(i=2;i<=m;i++){
//0
f[i][0] = f[i-1][1];
f[i][1] = f[i-1][0];
pf[i][0] = f[i][0];
pf[i][1] = f[i][1];
//1
f[i][0] = f[i][0] + f[i-1][0];
f[i][0] = f[i][0] + f[i-1][1];
}
//query ask
while(nn--){
m = scan();r = scan();
int top;
ans[0]=ans[1]=0;
//left edge
top=0;
for(i=m;i;i--){
scanf(" %c",&cc);
data[i] = (cc=='1');
if(!top)top=i;
}
top=m;
fina[top][0]=0;fina[top][1]=1;
for(i=top-1;i>=1;i--)
if(data[i+1]){//1
fina[i][0]=fina[i+1][0];
fina[i][1]=fina[i+1][0];
}else{//0
fina[i][0]=fina[i+1][1];
fina[i][1]=fina[i+1][0];
}
for(i=top;i>=1;i--){
if(data[i] == 1){
if(fina[i][0]==r){
ans[0] = ans[0] + pf[i][0];
}
if(fina[i][1]==r){
ans[0] = ans[0] + pf[i][1];
}
}
//ans[0] = ans[0] + pf[i][r];
}
//printf("%d\n",ans[0]);
//break;
//right edge
top=0;
for(i=m;i;i--){
scanf(" %c",&cc);
data[i] = (cc=='1');
if(!top)top=i;
}
top=m;
fina[top][0]=0;fina[top][1]=1;
for(i=top-1;i>=1;i--)
if(data[i+1]){//1
fina[i][0]=fina[i+1][0];
fina[i][1]=fina[i+1][0];
}else{//0
fina[i][0]=fina[i+1][1];
fina[i][1]=fina[i+1][0];
}
for(i=top;i>=1;i--){
if(data[i] == 1){
if(fina[i][0]==r){
ans[1] = ans[1] + pf[i][0];
}
if(fina[i][1]==r){
ans[1] = ans[1] + pf[i][1];
}
}
//ans[1] = ans[1] + pf[i][r];
}
if(fina[1][data[1]] == r)ans[1]=ans[1]+1;
ans[0] = ans[1] - ans[0];
//printf("%d\n",ans[0]);
//ans[0].print();printf("\n");
//output
out[0]=0;
while(!(ans[0].d[0]==1 && ans[0].d[1]==0)){
out[++out[0]]=(ans[0].d[1]&1);
//printf("%d",ans[0].d[1]&1);
div2(ans[0]);
}
if(!out[0])out[0]++,out[1]=0;
for(i=out[0];i;i--)printf("%d",out[i]);
printf("\n");
}
return 0;
}

题解:
非常明显的数位DP。
但是正常的DP大多数人应该都是写的从高位到低位DP
这题要从低到高DP,比较反人类。。
怎么做呢?
对于一个二进制数101011100
我们可以把它分成几层统计答案
<100000000
<101000000
<101010000
<101011000
<101011100
=101011100
这样也就是说从某个位置i开始划分,前面的部分固定了(第i位强制选0),后面的没有限制,可以随便dp
我的写法有点蛋疼。。首先预处理出一个pf[i][j],表示后i位随便选的情况下最后合并起来答案是j的方案数
然后每个数据还要处理一个fina[i][j]表示i位之前的位数固定的情况下,后i位合并起来答案是j的情况下最后得到的答案
最后乱搞一下统计答案,注意边界的情况
我写的比较混乱,凑合着看吧= =、
  评论这张
 
阅读(52)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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