HDU 5014 异或之和

http://acm.hust.edu.cn/vjudge/contest/122814#problem/H

这道题就是求异或之和

知识点： a^b = c 等价于 b^c =a 和 a^c = b

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define MAXN 100000 + 10

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

#define INF 0x3f3f3f3f

int n,m;

int a[MAXN],b[MAXN];

int main()

{

    int i,j;

    while(~sf("%d",&n))

    {

        mem(a,);

        mem(b,-);

        long long sum = ;

        for(i=;i<=n;i++) sf("%d",&a[i]);

        for(i=n;i>=;i--)

        {

            int s = i;

            if(b[i] == -)

            {

                int cnt = ;

                while(s)

                {

                    s>>=;

                    cnt++;

                }

                int tmp = (<<cnt) -;

                b[i] = i^tmp;

                b[i^tmp] = i;

            }

        }

        //for(i=0;i<=n;i++) pf("%d ",b[i]);

        for(i=;i<=n;i++) sum+= i^b[i];

        pf("%I64d\n",sum);

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

        {

            pf("%d ",b[a[i]]);

        }

        pf("%d\n",b[a[n]]);

    }

    return ;

}