Roof Construction(异或/构造)

题目
题意：给定数n，要求构造$0,1,2...,n-1$的排列$a$，使得 m a x ( a i − 1 ⨁ a i ) max(a_{i-1} \bigoplus a_i) max(ai−1​⨁ai​)最小化。
官方题解
设不大于n-1的最小的2的幂次是k，则 m a x ( a i − 1 ⨁ a i ) max(a_{i-1} \bigoplus a_i) max(ai−1​⨁ai​)为 2 k 2^k 2k。构造方式 2 k − 1 , 2 k − 2 , . . . , 0 , 2 k , . . . , n − 1 2^k-1,2^k-2,...,0,2^k,...,n-1 2k−1,2k−2,...,0,2k,...,n−1

#include
using namespace std;
#define ll long long
const int maxn = 200010;int n;void solve() {scanf("%d", &n);int k = 0;while ((1 << (k+1)) < n) {++k;} for (int i = (1 << k) - 1; i >= 0; --i) {printf("%d ", i);}for (int i = (1 << k); i < n; ++i) {printf("%d ", i);}printf("\n");
}
int main() {int t;scanf("%d", &t);while(t--) {solve();} return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！