hdu 5014 貪心+位處理

hdu 5014 貪心+位處理

 
題意略。
分析: 通過發現規律貪心處理即可，從n開始反向遍歷到0，假設與數i匹配的是 Xi;
那麼i^Xi的二進制位一定全1，並且二進制位數等於i的二進制位數

#include 
#include 
#include 
#include 
#include 
const int N=1e5+100;
using namespace std;
typedef long long ll;
int a[N];
int b[N];

int main()
{
    int n;
    while(scanf(%d,&n)!=EOF)
    {
        memset(b,-1,sizeof(b));
        for(int i=0;i<=n;i++)scanf(%d,&a[i]);
        ll sum=0;

        for(int i=n;i>=0;i--)
        {
           if(b[i]!=-1)continue;
           int tmp=i,ans=0,cnt=1;
           while(tmp)
           {
             if((tmp&1)==0)ans+=cnt;
             tmp>>=1;
             cnt*=2;
           }
          sum+=2*(i^ans);
          b[i]=ans;
          b[ans]=i;
        }
        printf(%I64d
,sum);
        for(int i=0;i<=n;i++)
        {
          if(i==0)printf(%d,b[a[i]]);
          else printf( %d,b[a[i]]);
        }
        printf(
);
    }
    return 0;
}