HDU 5014 Number Sequence（西安网络赛H题）

本文主要是介绍HDU 5014 Number Sequence（西安网络赛H题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 5014 Number Sequence

题目链接

思路：对于0-n，尽量不让二进制中的1互相消掉就是最优的，那么只要两个数只要互补就可以了，这样每次从最大的数字，可以找到和他互补的数字，然后这个区间就能确定了，然后剩下的递归下去为一个子问题去解决

代码：

#include <cstdio>
#include <cstring>const int N = 100005;int n, a[N], ans[N];
int cnt[N];int count(int x) {if (x == 0) return 1;int ans = 0;while (x) {ans++;x >>= 1;}return ans;
}void dfs(int n) {if (n <= 0) return;int tmp = (n^cnt[n]);for (int i = n; i >= tmp; i--) {ans[i] = n + tmp - i;}dfs(tmp - 1);
}int main() {for (int i = 0; i < N; i++)cnt[i] = ((1<<count(i)) - 1);while (~scanf("%d", &n)) {for (int i = 0; i <= n; i++)scanf("%d", &a[i]);memset(ans, 0, sizeof(ans));dfs(n);long long out = 0;for (int i = 0; i <= n; i++)out += (long long)(a[i]^ans[a[i]]);printf("%I64d\n", out);for (int i = 0; i <= n; i++)printf("%d%c", ans[a[i]], i == n ? '\n' : ' ');}return 0;
}

这篇关于HDU 5014 Number Sequence（西安网络赛H题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---