hdu 5014 异或序列

http://acm.hdu.edu.cn/showproblem.php?pid=5014

从最大的一个数开始找能配对使他们的异或值最大的一个数

最后输出

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

int s[100005],tran[100005];

bool vis[100005];

int tr(int x)

{

    int cnt = 0;

    while(x){

        cnt++;

        x>>=1;

    }

    return (1<<cnt) - 1;

}

int main(){

    int n;

    while(~scanf("%d",&n)){

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

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

        }

        clr0(vis);

        LL ans = 0;

        for(int x = n;x >= 0;--x){

            if(!vis[x]){

                vis[x] = true;

                int now = 1LL * tr(x);

                int y = now^x;//cout<<x<<','<<y<<endl;

                if(!vis[y]){

                    ans += now<<1;

                    tran[x] = y,tran[y] = x;

                    vis[y] = true;

                }

                else

                    ans += x,tran[x] = x;

            }

        }

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

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

            printf("%d%c",tran[s[x]]," \n"[x == n]);

     }

     return 0;

 }

巴特西

hdu 5014 异或序列

最新文章

热门文章