Codeforces Global Round 27的C题

题目大意
给定一个n,n>=5
ans=0
ans&a1|a2&a3|a4&a5...an,数组a是一个排列
下标是奇数让ans对其进行&操作,否则进行|操作,求ans能达到的最大值.
分奇偶来讨论,在n为奇数的情况下,最后一次操作是|,在n为偶数的情况下,最后一次操作是&.
n二进制最高位的计算方法k=log2(n).
首先讨论n为奇数的情况下,最后一个数尝试放2^k,前n-1个数需要凑成2^k-1,我们只需要考虑前5个数就能够满足这些条件.
p[n-i]用来表示第n-i数是多少,p[n-5]放一个3,p[n-4]放一个1,p[n-3]放一个2^k-2,p[n-2]放一个2^k-1,p[n-1]放一个2^k,p[n-5]的二进制位是110,它的作用是保护最低位的1,p[n-4]的二进制位是100,它的作用是清空除了最低位1以外的所有1,经过前两步操作以后剩下100,p[n-3]的作用是避免p[n-2]被更改,p[n-3]最低位的1是没有了的,它和1进行|操作以后又变成了p[n-2],所以它和p[n-2]进行&操作不会改变p[n-2],最后和p[n-1]|进行操作,可以得到前k位全是1的最大数.
整理一下,猜测最大数为凑成前k位全是1的数,把它拆分成最高位1和剩下的1,分别放到p[n-1]和p[n-2]当中,要想顺利的达成目的,就得避免p[n-2]被改变,这要求p[n-3]和p[n-2]相等,但是排列不会出现两个相等的数,那么只能继续拆分p[n-2]变成最低位的1和剩余的1,剩余的1放在p[n-3]当中,p[n-4]当中放1,此时p[n-4]|p[n-3]=p[n-2],但要怎么避免1被改变呢,如果p[n-5]是一个偶数,它和p[n-4]进行&操作就会破坏掉1,那么这就要求p[n-5]是一个奇数,此时不管p[n-6]是多少它都不会破坏掉最低位的1,这样就可以保证p[n-4]的1不被破坏掉1了,我们选了3当做这个奇数,但是可以发现,当k位2的时候p[n-2]=2^k-1也等于3,这不行,排列不能重复,此时我们可以选择5,5没有出现过.到此奇数的情况就大功告成了.

下面讨论偶数的情况,我们知道n为偶数的情况下,最后一次操作是&,也就是我们能够凑成的最大的数是n,不妨就让p[n-1]等于n,此时要求p[n-2]也是n,但排列不能出现两个数,我们继续分解,分解成1和n-1,由于n是奇数,n-1的二进制位仅仅变化1那一位,现在我们让p[n-2]=n-1,而p[n-3]等于最低位是1的任何数,p[n-3]前面是&操作,这要求p[n-4]是个奇数,那就随便填两个数1,3就可以了,只要不和n和n-1重复即可.

void solve() {
    int n;
    std::cin >> n;

    int k = (int)std::log2(n);
    std::vector<int> p(n);
    int ans;
    std::vector<bool> vis(n + 1);
    if (n % 2 == 0) {
        ans = (2 << k) - 1;
        p[n - 1] = 1 << k;
        p[n - 2] = (1 << k) - 1;
        p[n - 3] = (1 << k) - 2;
        p[n - 4] = 1;
        p[n - 5] = k == 2 ? 5 : 3;
        for (int i = n - 5; i < n; i++) {
            vis[p[i]] = true;
        }
        for (int i = 0, x = 1; i < n - 5; i++) {
            while (vis[x]) {
                x++;
            }
            p[i] = x;
            vis[x] = true;
        }
    }
    else {
        ans = n;
        p[n - 1] = n;
        p[n - 2] = n - 1;
        p[n - 3] = 3;
        p[n - 4] = 1;
        for (int i = n - 4; i < n; i++) {
            vis[p[i]] = true;
        }
        for (int i = 0, x = 1; i < n - 4; i++) {
            while (vis[x]) {
                x++;
            }
            p[i] = x;
            vis[x] = true;
        }
    }

    std::cout << ans << "\n";
    int v = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            v &= p[i];
        }
        else {
            v |= p[i];
        }
        std::cout << p[i] << " \n"[i == n - 1];
    }
}