題干：

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.?

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.?

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,b?2,...,b?n. There is exactly one space between b?i?and b?i+1?(0 ≤ i ≤ n - 1). Don’t ouput any spaces after bn.?

Sample Input

4 2 0 1 4 3

Sample Output

20 1 0 2 3 4

題目大意：

● a?i?∈ [0,n]?
● a?i?≠ a?j( i ≠ j )?

同樣的b也滿足該規則，
現在問你是否存在一個序列b，使得t最大

t = (a?0?異或 b?0) + (a?1 異或?b?1) +???+ (a?n 異或?b?n)

n(1 ≤ n ≤ 10?5)

解題報告：

? ?直接從大到小貪心，讓每一個數和 他按位取反的那個數匹配。這樣雖然可能會剩下一個0，但是易知這樣一個1都沒有浪費，所以這樣得到的結果一定是最優的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,a[MAX]; int b[MAX]; ll ans; int main() {while(cin>>n) {ans = 0;memset(b,-1,sizeof b);b[0]=0;for(int i = 0; i<=n; i++) cin>>a[i];for(int sta = n; sta>0; sta--) {if(b[sta] != -1) continue;int bit;for(bit = 22; bit>=0; bit--) {if(sta&(1<<bit)) break;}if(bit == -1)continue;int oth = 0; for(int i = bit; i>=0; i--) {if(sta & (1<<i)) continue;else oth |= (1<<i);}b[oth] = sta; b[sta] = oth;}for(int i = 0; i<=n; i++) ans += i^b[i];printf("%lld\n",ans);for(int i = 0; i<=n; i++) printf("%d%c",b[a[i]],i == n ? '\n' : ' '); }return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 5014】Number Sequence（贪心构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。