[cqoi2013]二进制a+b
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
这道题蛮有意思的..
可以考虑DP，这样来设计状态：
f(ma,mb,mc,n,q)表示a用了ma个1，b用了mb个1，c用了mc个1，当前到第n位，q∈{0,1}表示是否有进位
然后只需枚举当前位a取0，b取0、a取1，b取1、a取1，b取0这三种情况，根据q来判断mc需要增加多少和答案需要增加多少
最后的答案就是f(na,nb,nc,len,0),na是a中1的个数，nb是b中1的个数，nc是c中1的个数,len是最长的数的长度
这里q一定要取0是因为，当我们得到一个状态时，若q等于1，那么n是比实际上的长度少1的，因为当前位（也就是需要枚举的这一位，也就是n+1位）有一个1.
至于转移么，我写了个SPFA转移（而且写慢了..懒得改了..)，应该有更好的转移方式（SPFA转移写了整整4K..)
那么完整代码如下:
#include <stdio.h>
#include <queue>
#include <string.h>
typedef long long Long;
Long a = 0;
Long b = 0;
Long c = 0;
int na = 0;
int nb = 0;
int nc = 0;
int len = 0;
int get_num(Long n)
{
Long m = (1LL << 60);
int r = 0;
while(m)
{
if(m & n)
r++;
m >>= 1;
}
return r;
}
int get_len(Long n)
{
bool flag = false;
Long m = (1LL << 60);
int r = 0;
while(m)
{
if(m & n)
flag = true;
if(flag)
r++;
m >>= 1;
}
return r;
}
int MIN(int a,int b)
{
return a > b ? b : a;
}
Long MAX(Long a,Long b)
{
return a > b ? a : b;
}
const int N = 30;
void upmin(Long & m,Long n)
{
if(n < 0)
return;
if(m > n || m < 0)
m = n;
}
const Long INF = (1LL << 60);
Long pow(Long a,int b)
{
Long m = (1LL<<60);
Long r = 1LL;
while(m)
{
r *= r;
if(m & b)
r *= a;
m >>= 1;
}
return r;
}
struct node
{
int ma;
int mb;
int mc;
int q;
int n;
Long val;
node()
{}
node(int MA,int MB,int MC,int NN,Long VAL,int Q = 0)
{
ma = MA;
mb = MB;
mc = MC;
n = NN;
q = Q;
val = VAL;
}
bool operator==(const node & B)
{
return (ma == B.ma && mb == B.mb && mc == B.mc && q == B.q && n == B.n);
}
};
std::queue<node> queue;
Long f[N + 10][N + 10][N + 10][N + 10][2];
Long res = INF;
int main()
{
scanf("%lld%lld%lld",&a,&b,&c);
na = get_num(a);
nb = get_num(b);
nc = get_num(c);
int lena = get_len(a);
int lenb = get_len(b);
int lenc = get_len(c);
len = lena;
if(len < lenb)
len = lenb;
if(len < lenc)
len = lenc;
memset(f,-1,sizeof(f));
queue.push(node(0,0,0,0,0,0));
f[0][0][0][0][0] = 0;
#define F(A) (f[A.ma][A.mb][A.mc][A.n][A.q])
#define UP() \
{\
if(now_s.val < F(now_s) || F(now_s) < 0)\
{\
F(now_s) = now_s.val;\
queue.push(now_s);\
}\
}
node now_f;
node now_s;
do
{
now_f = queue.front();
queue.pop();
if(F(now_f) < now_f.val)
continue;
//if(now_f == node(2,2,2 ,2 , 1,1))
// fprintf(stderr,"QAQ %d\n",now_f.val);
// if(now_f.n == 2)
// fprintf(stderr,"%d %d %d n = %d val = %lld\n",now_f.ma,now_f.mb,now_f.mc,now_f.n,now_f.val);
if(now_f.n > len)
continue;
{
now_s = now_f;
now_s.n++;
now_s.q = 0;
UP();
}
if(now_f.ma < na)
{
now_s = now_f;
now_s.ma++;
now_s.n++;
if(now_s.q == 1)
{
now_s.val -= pow(2,now_s.n-1);
now_s.val += pow(2,now_s.n);
}
else
{
now_s.val += pow(2,now_s.n-1);
now_s.mc++;
}
UP();
}
if(now_f.mb < nb)
{
now_s = now_f;
now_s.mb++;
now_s.n++;
if(now_s.q == 1)
{
now_s.val -= pow(2,now_s.n-1);
now_s.val += pow(2,now_s.n);
}
else
{
now_s.val += pow(2,now_s.n-1);
now_s.mc++;
}
UP();
}
if(now_f.ma < na && now_f.mb < nb)
{
now_s = now_f;
now_s.mb++;
now_s.ma++;
now_s.n++;
if(now_s.q == 1)
{
now_s.val += pow(2,now_s.n);
now_s.mc ++;
}
else
{
now_s.val += pow(2,now_s.n);
now_s.mc++;
now_s.q = 1;
}
UP();
}
}
while(!queue.empty());
upmin(res,f[na][nb][nc][len][0]);
// upmin(res,f[na][nb][nc][len][1]);
// fprintf(stderr,"%lld %lld\n",f[na][nb][nc][len][0],f[na][nb][nc][len][1]);
if(res == INF)
res = -1LL;
printf("%lld\n",res);
return 0;
}
评论 (0)
