HDU 5014 – Number Sequence [找规律+贪心]

点击打开HDU题目链接

给定一些0~N的数列,求一个0~N的数列,使得对应两个数异或值的和最大。

感觉最近找规律的题越来越不顺手了,特别是二进制相关的题目,这次就是,从好多方面考虑,一直不对。

一种正确的解法是从大到小贪心找出每个数对应的数,手动按位取反就是,这样能保证小的数取反时不越界,同时保证了有最大的异或值。想到这种方法后写出来验证下就可以了。

#include <bits/stdc++.h>
using namespace std;


const int maxn = 100005;
int n, a[maxn], res[maxn];

int main() {
    ios_base::sync_with_stdio(false);
    while(cin >> n) {
        for(int i = 0; i <= n; ++i)
            cin >> a[i];
        memset(res, -1, sizeof(res));
        long long sum = 0;
        for(int i = n; i >= 0; --i) {
            if(res[i] == -1) {
                int cnt = 0, t = i;
                while(t > 0) {
                    ++cnt;
                    t >>= 1;
                }
                int M = (1<<cnt)-1;
                res[i] = i^M;
                res[i^M] = i;
                sum += M * 2;
            }
        }
        cout << sum << endl;
        for(int i = 0; i <= n; ++i) {
            if(i != n) cout << res[a[i]] << " ";
            else cout << res[a[i]] << endl;
        }
    }
    return 0;
}

欢迎留言