admin管理员组文章数量:1602098
It has finally been decided to build a roof over the football field in School 179. Its construction will require placing nn consecutive vertical pillars. Furthermore, the headmaster wants the heights of all the pillars to form a permutation pp of integers from 00 to n - 1n−1, where p_ipi is the height of the ii-th pillar from the left (1 \le i \le n)(1≤i≤n).
As the chief, you know that the cost of construction of consecutive pillars is equal to the maximum value of the bitwise XOR of heights of all pairs of adjacent pillars. In other words, the cost of construction is equal to \max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}1≤i≤n−1maxpi⊕pi+1, where \oplus⊕ denotes the bitwise XOR operation.
Find any sequence of pillar heights pp of length nn with the smallest construction cost.
In this problem, a permutation is an array consisting of nn distinct integers from 00 to n - 1n−1 in arbitrary order. For example, [2,3,1,0,4][2,3,1,0,4] is a permutation, but [1,0,1][1,0,1] is not a permutation (11 appears twice in the array) and [1,0,3][1,0,3] is also not a permutation (n=3n=3, but 33 is in the array).
Input
Each test contains multiple test cases. The first line contains the number of test cases tt (1 \le t \le 10^41≤t≤104). Description of the test cases follows.
The only line for each test case contains a single integer nn (2 \le n \le 2 \cdot 10^52≤n≤2⋅105) — the number of pillars for the construction of the roof.
It is guaranteed that the sum of nn over all test cases does not exceed 2 \cdot 10^52⋅105.
Output
For each test case print nn integers p_1p1, p_2p2, \ldots…, p_npn — the sequence of pillar heights with the smallest construction cost.
If there are multiple answers, print any of them.
Sample 1
Inputcopy Outputcopy 4 2 3 5 10 0 1 2 0 1 3 2 1 0 4 4 6 3 2 0 8 9 1 7 5Note
For n = 2n=2 there are 22 sequences of pillar heights:
- [0, 1][0,1] — cost of construction is 0 \oplus 1 = 10⊕1=1.
- [1, 0][1,0] — cost of construction is 1 \oplus 0 = 11⊕0=1.
For n = 3n=3 there are 66 sequences of pillar heights:
- [0, 1, 2][0,1,2] — cost of construction is \max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3max(0⊕1,1⊕2)=max(1,3)=3.
- [0, 2, 1][0,2,1] — cost of construction is \max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3max(0⊕2,2⊕1)=max(2,3)=3.
- [1, 0, 2][1,0,2] — cost of construction is \max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2max(1⊕0,0⊕2)=max(1,2)=2.
- [1, 2, 0][1,2,0] — cost of construction is \max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3max(1⊕2,2⊕0)=max(3,2)=3.
- [2, 0, 1][2,0,1] — cost of construction is \max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2max(2⊕0,0⊕1)=max(2,1)=2.
- [2, 1, 0][2,1,0] — cost of construction is \max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3max(2⊕1,1⊕0)=max(3,1)=3.
题意:给你0~n-1个数,将i与i+1做按位异或运算(顺序随意),算运算结果最大值的最小值。
思路:最大的值,必然出现在最高位为1的地方。所以我们把这块输出,然后还有一个要和后面的做运算,为了最小我们只能放0,剩下的怎么输出都行,反正他也不会多大。
#include<iostream>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, k;
scanf("%d", &n);
for (int i = 25; i >= 0; i--)
if (pow(2, i) < n)
{
k = i;
break;
}
for (int i = n-1; i >= pow(2, k); i--)
printf("%d ",i);
printf("0 ");
for(int i=1;i< pow(2, k);i++)
printf("%d ", i);
printf("\n");
}
}
本文标签: Roofconstruction
版权声明:本文标题:Roof Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728395888a1156997.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论