[cqoi2013]二进制a+b

BZOJ3107
这道题蛮有意思的..
可以考虑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;

}