首页 > 代码库 > ACM学习历程——HDU 5014 Number Sequence （贪心）（2014西安网赛）
ACM学习历程——HDU 5014 Number Sequence （贪心）（2014西安网赛）
Description
There is a special number sequence which has n+1 integers. For each number in sequence, we have two rules:
● a i ∈ [0,n]
● a i ≠ a j( i ≠ j )
For sequence a and sequence b, the integrating degree t is defined as follows(“?” denotes exclusive or):
t = (a 0 ? b 0) + (a 1 ? b 1) +???+ (a n ? b n)
(sequence B should also satisfy the rules described above)
Now give you a number n and the sequence a. You should calculate the maximum integrating degree t and print the sequence b.
● a i ∈ [0,n]
● a i ≠ a j( i ≠ j )
For sequence a and sequence b, the integrating degree t is defined as follows(“?” denotes exclusive or):
(sequence B should also satisfy the rules described above)
Now give you a number n and the sequence a. You should calculate the maximum integrating degree t and print the sequence b.
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains an integer n(1 ≤ n ≤ 10 5), The second line contains a 0,a 1,a 2,...,a n.
For each case, the first line contains an integer n(1 ≤ n ≤ 10 5), The second line contains a 0,a 1,a 2,...,a n.
Output
For each case, output two lines.The first line contains the maximum integrating degree t. The second line contains n+1 integers b 0,b 1,b2,...,b n. There is exactly one space between b i and b i+1(0 ≤ i ≤ n - 1). Don’t ouput any spaces after b n.
Sample Input
4
2 0 1 4 3
Sample Output
20
1 0 2 3 4
这个题目想到贪心策略就好办了。
最先想到的一种策略就是对于数k的二进制形式，把0换成1, 1换成0,亦或后将得到全1的最大数。而且每个数的0、1组合都是唯一的，自然其对应的那个数也是唯一的。
但是会遇到一种情况，比如二进制1111和11111,它们都是和0亦或得到最大。
于是这样考虑：
对于任意一个数，只有两种情况，一是和比它小的数亦或，二是和比它大的数亦或。如果和比它小的数亦或，自然对应的数第一位肯定是0。后面可能会跟若干个0,最坏是1111这种，对应的是0;如果和比它大的数亦或，会发现，对应的数二进制位数一定比这个数长，自然1111对应的可能是10000、110000等等。
于是，只需要从大到小进行一一匹配，就不会出现之前的情况。例如之前那种情况，如果11111先匹配，11111将会和0匹配，而1111将会在之前就和10000匹配了。
ps：据说sum结果是n*(n+1)，可以找规律找出来。不过我暂时推不出来。
ps：结果可能很大，需要long long来存。
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>using namespace std;int a[100005], Hash[100005], n;long long sum;void qt(){ sum = 0; memset(Hash, -1, sizeof(Hash)); int k, v, val, p; for (int i = n; i >= 0; i--) { if (Hash[i] >= 0) continue; k = i; p = 1; val = 0; for (;k;) { v = k & 1; val += (v^1) * p; p <<= 1; k >>= 1; } Hash[i] = val; Hash[val] = i; } for (int i = 0; i <= n; ++i) sum += a[i]^Hash[a[i]];}int main(){ //freopen("test.txt", "r", stdin); while (scanf("%d", &n) != EOF) { for (int i = 0; i <= n; ++i) scanf("%d", &a[i]); qt(); printf("%I64d\n", sum); for (int i = 0; i <= n; ++i) { if (i) printf(" "); printf("%d", Hash[a[i]]); } printf("\n"); } return 0;}
ACM学习历程——HDU 5014 Number Sequence （贪心）（2014西安网赛）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。