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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3107][cqoi2013]二进制a+b  

2014-10-13 09:27:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3107: [cqoi2013]二进制a+b

头疼死了……
liangjs神犇说的“水题”
我想了好长时间QAQ
然后还因为没读好题的问题WA了好久

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 33;
typedef long long LL;
int n,m,A,B,C,L;
LL ans;
int scan(){int i=0;scanf("%d",&i);return i;}
int cot(int x){int re=0;for(;x;x/=2)if(x&1)re++;return re;}
LL f[N*2][N][N][N][2],two[N*2];
short v[N*2][N][N][N][2];
short upda(int i,int a,int b,int j,LL val){
int c = cot(val);
LL &fn = f[i][a][b][c][j];short &vn = v[i][a][b][c][j];
if(!vn){
vn = 1;
fn = val;
}else fn = min(fn,val);
if(a==A&&b==B&&c==C){ans = val;return 0;}
return 1;
}
int main(){
int i,j,a,b,c;
a = scan();b = scan();c = scan();
A = cot(a);B = cot(b);C = cot(c);
L = max(L,(int)log2(a));
L = max(L,(int)log2(b));
L = max(L,(int)log2(c));
ans = -1;
bool ok = 1;
v[0][0][0][0][0] = 1;
f[0][0][0][0][0] = 0;
for(two[0] = 1,i=1;i<=61;i++)two[i] = two[i-1]*2;

for(i=0;i<=L;i++){
int now = 0;
for(a=0;a<=A;a++)
for(b=0;b<=B;b++)
for(c=0;c<=C;c++)
for(j=0;j<=1;j++)
if(v[i][a][b][c][j]){
now = 1;
int last = f[i][a][b][c][j];
//0 0
ok = upda(i+1,a,b,0,last)&&ok;
//1 0
ok = upda(i+1,a+1,b,1&j,last+two[i]*1)&&ok;
//0 1
ok = upda(i+1,a,b+1,1&j,last+two[i]*1)&&ok;
//1 1
ok = upda(i+1,a+1,b+1,1,last+two[i]*2)&&ok;
}
if(!now || !ok)
break;
}
if((int)log2(ans) > L)ans = -1;
printf("%d\n",ans);
return 0;
}

题解:
DP
f[i][a][b][c][j]
当前枚举到(二进制下的)第i位,a' b' c'各用a,b,c了几个1,j表示最后一位是否有进位
这时的最小答案
题目说得很绕……隐藏了一个条件:a'b'c'的最大长度不能超过原最大长度
  评论这张
 
阅读(134)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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