首页 > 代码库 > hdu 5014 Number Sequence(贪心)
hdu 5014 Number Sequence(贪心)
题目链接:hdu 5014 Number Sequence
题目大意:给定n,表示有0~n这n+1个数组成的序列a,要求构造一个序列b,同样是由0~n组成,要求∑ai⊕bi尽量大。
解题思路:贪心构造,对于n来说,找到n对应二进制的取反对应的数x,那么从x~n之间的数即可两两对应,然后x-1即是一个子问题。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
int arr[maxn];
ll solve (int n) {
if (n < 0)
return 0;
int k = 0;
while ((1<<k) <= n) k++;
int t = (1<<k) - 1;
ll ret = 0;
for (int i = t - n; i <= n; i++) {
ret += t;
arr[i] = t - i;
}
ret += solve(t - n - 1);
return ret;
}
int main () {
int n, x;
while (scanf("%d", &n) == 1) {
printf("%lld\n", solve(n));
for (int i = 0; i <= n; i++) {
scanf("%d", &x);
printf("%d%c", arr[x], i == n ? ‘\n‘ : ‘ ‘);
}
}
return 0;
}
hdu 5014 Number Sequence(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。