p1383

当时有人说:

于是去看了一眼,觉得动归很可写啊,于是写了写转移发现不太能直接转移,因为异或不一定是加还是减,滚动数组不好搞.于是算了算2^100也才六万多,完全可以开E*2^B的数组保存状态.

借用c++自带的^运算就写成了这样子

然后发现自己日常读错题:人家首先要求要从已有的数开始异或.而且至少运行一次.这样的话这个代码初状态就很智障了.

首先考虑换一下状态吧:可以枚举步数,这里当然是小于等于2*E的了,因为每个数字最多用两次,一般只用一次或者不用.

 那么就有又了一个显然的状态转移.

复杂度不小了,200*100*50000=超时.想到不需要用2n次,改成n就可以,参考上面的推论.但是还是超时啊.

但是第一重循环真的有用么?想一想状态更新的过程发现是完全不必要的.我们再改一下就可以跑的飞快了.为什么可以去掉一重循环呢?因为考虑这个动归类似于背包的迭代更新,输出的答案最多是每个数都用一次为n,再循环那么多次没有意义.

所以最后AC代码和第一次的有什么不一样呢?这道题为什么没有人写动归呢?我认为是初状态的设置问题.它从各种动归常用的粗暴的设(0,0)为初状态到自己枚举得到出状态,变得复杂了一些.

复杂度(E^2+E*2^B).

没了.

using namespace std;
int read()
{
    int This=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        This=(This<<1)+ch-'0';
        ch=getchar();
    }
    return This;
}
int i,f,t;
int m,n,end;
int tt[20],o[210];
void write(int aa)
{
    memset(tt,0,sizeof(tt));
    for(i=0;aa;i++)
    {
        tt[i]=aa%2;
        aa=aa/2;
    }
    for(i=log2(m);i>=0;i--)
    {
        cout<<tt[i];
    }
    return ;    
}
int wei(int a,int b)
{
    int sum=0;
    for(;a>0||b>0;)
    {
        if((a&1) != (b&1))
        {
            sum++;
        }
        a=a/2;b=b/2;
    }
    return sum;
}
int minn,ans,tstep,j;
int step[66666],can[66666];
int main()
{    
    //freopen("123.in","r",stdin);
    memset(step,0x3f,sizeof(step));
    cin>>m>>n;
    m=(1<<m)-1;
    end=read();
    for(i=1;i<=n;i++)
        o[i]=read();
    for(i=1;i<=n;i++)
    {
        can[o[i]]=1;
        step[o[i]]=min(step[o[i]],2);
        for(f=1;f<=n;f++)
        {            
            step[o[i]^o[f]]=1;
            can[o[i]^o[f]]=1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(f=0;f<=m;f++)
        {
            if(can[f])
            {
                can[f^o[i]]=1;
                step[f^o[i]]=min(step[f^o[i]],step[f]+1);
            }
        }
    }
    minn=100000;
    tstep=100000;
    for(i=m;i>=0;i--)
    {
        if(can[i])
        {
            if(wei(i,end)==minn&&step[i]<=tstep)
            {
                tstep=step[i];
                ans=i;
            }
            else if(wei(i,end)<minn)
            {
                tstep=step[i];
                minn=wei(i,end);
                ans=i;
            }
        }
    }
    cout<<tstep<<' ';
    write(ans);
}