Chip Factory

题意：一个n个数的数列，求三个数其中两个数的和与另外一个数的异或值最大，输出这个最大值。

思路：和前面那个百度之星资格赛HDU4825的类似，多了两个过程，一个是枚举和，另一个是删除过程，第一次写删除操作，还一遍A了，小激动。

会不会是后台水，东北师范官方没有给出标准测试数据，也就是说这数据是hdu YY的，我猜是这样，碰到过类似的情况，错误的代码竟然A了区域赛的题。这样为了AC貌似有点不好呀，不过思路很值得学习！

struct tree

{

    int f;

    tree *next[N];

    tree()

    {

        for(int i=0; i<N; i++) next[i]=NULL;

        f=0;

    }

}*root;

int a[33];

ll s[1005];

void ch(ll x)//转化为二进制

{

    memset(a,0,sizeof(a));

    int len=0;

    while(x)

    {

        a[len++]=x%2;

        x/=2;

    }

}

void insert(ll x)//插入一个数

{

    ch(x);

    int len=32;//长度最多32位

    tree *p=root;

    while(len>=0)

    {

        int id=a[len];

        if(p->next[id]==NULL)

        {

            tree *temp=new tree;

            p->next[id]=temp;

        }

        p=p->next[id];

        p->f++;//每个点都构成一个数，经过此点，次数加一

        len--;

    }

}

ll query(ll x)

{

    ch(x);

    tree *p=root;

    for(int i=0; i<33; i++) a[i]^=1;//不一定要这样，只是写HDU4825的时候用的这种思路

    int len=32;

    ll ans=0;

    while(len>=0)

    {

        int id=a[len];

        if(p->next[id]==NULL||p->next[id]->f==0) id^=1;//为0表示此节点被撤销了，另寻他路

        if(id) ans+=(ll)1<<len;

        p=p->next[id];

        len--;

    }

    return ans^x;

}

void fre(ll x)

{

    ch(x);

    int len=32;

    tree *p=root;

    while(len>=0)

    {

        int id=a[len];

        p->next[id]->f--;//撤销路径

        p=p->next[id];

        len--;

    }

}

void del(tree *root)

{

    for(int i=0; i<N; i++)

        if(root->next[i])

            del(root->next[i]);

    delete(root);

}

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        root=new tree;

        for(int i=0; i<n; i++)

        {

            scanf("%I64d",&s[i]);

            insert(s[i]);

        }

        ll ans=0;

        for(int i=0; i<n; i++)

        {

            fre(s[i]);

            for(int j=i+1; j<n; j++)

            {

                fre(s[j]);

                ans=max(ans,query(s[i]+s[j]));//撤销点，枚举和

                insert(s[j]);

            }

            insert(s[i]);

        }

        printf("%I64d\n",ans);

        del(root);

    }

    return 0;

}

巴特西

HDU-5536 Chip Factory,又见字典树，好题+1！

Chip Factory

最新文章

热门文章