C. Alya and Permutation
传送门：Problem - C - Codeforces
Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her.
Given an integer n, construct a permutation pp of integers 1,2,…,n that maximizes the value of k (which is initially 0) after the following process.
Perform nn operations, on the ii-th operation (i=1,2,…,n),
- If ii is odd, k=k&pik=k&pi, where && denotes the bitwise AND operation.
- If ii is even, k=k|pik=k|pi, where || denotes the bitwise OR operation.
Input
The first line contains a single integer t (1≤t≤500) — the number of test cases.
The only line of each test case contains a single integer n (5≤n≤2⋅10^5) — the length of the permutation.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.
Output
For each test case, output the maximum value of k in the first line and output the permutation p1,p2,…,pn in the second line.
If there are multiple such permutations, output any.
题意翻译
给定正整数 n，有一个变量 k，初始值为 0。请构造一个 1∼n的排列 p 使得经过如下 n 次操作后，k 的值最大。
- 对于第 i 次操作，如果 i 是奇数，执行 k=k and pi；如果 ii 是偶数，执行 k=k or pi。
请输出最终 k 的最大值和排列 p。
5≤n≤2×10^5
很明显的构造题，如果对位运算的 & 和 | 操作非常熟悉的话有可能会第一时间想到怎么构造，当然这些不重要，找规律么，我们可以随便找两个数 & 和 | 操作一下，发现只要经过 & 操作的数都不会变大，就比如3 & 4不会超过 4以此类推，按照题目的意思，奇数的最后一位一定是一个 & 操作，那么就得到关键信息了：因为 & 操作怎么操作都不会大于自身所以如果是奇数就最大值就一定是 n。我们只需要用 1 ~ n - 1 构造 n 出来就是答案了。
那么我们换到偶数来看看，也可以发现最后一位应该放 n， 然后如何最大呢？比如 10 的二进制吧
1010 那么肯定 | 一个 0111或者0101最大么。这里我们构造0111因为这种形式好构造，那么就得出倒数第二位的结果了：m = n 二进制的最高位减 1 ，m 代表二进制的位数这里我们全部取1， 得到的10进制数字就是倒数第二位，那么我们发现这个数字一定是奇数因为二进制的第一位是1，所以我们用上面我已经推导的构造奇数的办法构造这个数即可
代码
#include <iostream>
#include <vector>#define ll long longusing namespace std;int t, n;void solve()
{cin >> n;if(n & 1){int u, v;for(int i = 1;i < n - 1;i ++){if(i | (n - 1) == n){u = i;break;}}for(int i = 1;i < n - 1;i ++){if((u & i) | (n - 1) == n && i != u){v = i;break;}}cout << n << endl;for(int i = 1;i <= n;i ++){if(i == n || i == n - 1 || i == u || i == v) continue;cout << i << " ";}cout << u << " " << v << " " << n - 1 << " " << n << endl;}else{int high = 0, m = n, mx = 0;while(m){m /= 2;high ++;}for(int i = 1;i <= high;i ++){mx += 1 << (i - 1);}high --;int u, v, z = 0;for(int i = 1;i <= high;i ++){z += 1 << (i - 1);}for(int i = 1;i < n;i ++){if(i != z && i != z - 1 && i | (z - 1) == z){u = i;break;}}for(int i = 1;i < n;i ++){if(i != z && i != z - 1 && i != u && (i & u) | (z - 1) == z){v = i;break;}}cout << mx << endl;for(int i = 1;i <= n;i ++){if(i == u || i == v || i == z || i == n || i == z - 1) continue;cout << i << " ";}cout << u << " " << v << " " << z - 1 << " " << z << " " << n << endl;}
}int main()
{cin >> t;while(t --){solve();}return 0;
}加油
