Roof Construction(异或构造)

admin管理员组

文章数量:1602103

题目
题意：给定数n，要求构造 0 , 1 , 2... , n − 1 0,1,2...,n-1 0,1,2...,n−1的排列 a a 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<bits/stdc++.h>
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;
}

本文标签： Roofconstruction