程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5014 貪心+位處理

hdu 5014 貪心+位處理

編輯:關於C++

 
題意略。
分析: 通過發現規律貪心處理即可,從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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved