首页 > 代码库 > 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题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。