首页 > 代码库 > HDU5014Number Sequence(贪心)
HDU5014Number Sequence(贪心)
HDU5014Number Sequence(贪心)
题目链接
题目大意:
给出n,然后给出一个数字串,长度为n + 1, 范围在[0, n - 1].然后要求你找出另外一个序列B,满足上述的要求,并且使得t = A0^B0 + Ai + 1 ^ Bi + 1 + ... + An ^ Bn 最大。
解题思路:
对于一个数字进行异或,要求结果最大的话,那么取这个数字的二进制互补数字是最好的情况,并且可以发现每次找到一个数字和对应的互补的数字都会是一段区间。就这样一段一段区间的去寻找每个点对应的最好的匹配点。
代码:
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1e5 + 5;
const int M = 20;
int num[N];
int Map[N];
int n;
ll t[M];
void init () {
t[0] = 1;
for (int i = 1; i <= M; i++)
t[i] = t[i - 1] * 2;
}
int main () {
init();
while (scanf ("%d", &n) == 1) {
for (int i = 0; i <= n; i++)
scanf ("%d", &num[i]);
int rear = n;
int front;
ll ans = 0;
// printf ("%lld\n", t[M - 1]);
while (rear >= 0) {
for (int i = 0; i < M; i++)
if (t[i] > rear) {
front = t[i] - rear - 1;
break;
}
for (int i = 0; i < (rear - front + 1) / 2; i++) {
Map[rear - i] = front + i;
Map[front + i] = rear - i;
}
if (rear == front)
Map[rear] = front;
rear = front - 1;
}
for (int i = 0; i <= n; i++)
ans += num[i] ^ Map[num[i]];
printf ("%lld\n", ans);
for (int i = 0; i < n; i++)
printf("%d ", Map[num[i]]);
printf ("%d\n", Map[num[n]]);
}
return 0;
}
HDU5014Number Sequence(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。