首页 > 代码库 > HDU 5014 Number Sequence （ 构造 ）
HDU 5014 Number Sequence （ 构造 ）
HDU 5014 Number Sequence （ 构造 ）
题目意思：
给出一个数列 由0 - n 组成
然后需要构造一个数列 （也是由0-n组成），使得 sum(A[i] ^ B[i])的值最大。
分析：
异或不能出现比这个数大的情况，，所以要从大的数往前找。
现计算出当前判断数的二进制位的位数m，然后再与2^m - 1进行异或,这样会保证最大，具体为什么，自己可以想一想
比如： 5 - 101 -- 3位 - 对应 111
101 ^ 111 = 010
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MAXN 100005#define CLR( a,b ) memset( a, b, sizeof(a) )int a[MAXN], vis[MAXN], b[MAXN];int cnt( int x ){ int ct = 0; while( x ) { ct++; x >>= 1; } return ct;}void Orz(){ int n, pos; long long ans; while( ~scanf( "%d", &n ) ) { CLR( a, 0 ); CLR( b, 0 ); CLR( vis, 0 ); ans = 0; for( int i = n;i >=0; --i ) { if( vis[i] ) continue; int ct = cnt( i ); int tmp = i ^ ( ( 1 << ct) - 1 ); b[ tmp ] = i; b[ i ] = tmp; vis[i] = vis[tmp] = 1; ans += ( ( 1 << ct ) - 1 ) << 1; } printf( "%I64d\n", ans ); for( int i = 0; i < n; ++i ) { scanf( "%d", &pos ); printf( "%d ",b[pos] ); } scanf( "%d", &pos ); printf( "%d\n", b[pos]); }}int main(){ Orz(); return 0;}
HDU 5014 Number Sequence （ 构造 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。