Codeforces 1632 B. Roof Construction —— 简单位运算

本文主要是介绍Codeforces 1632 B. Roof Construction —— 简单位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

你现在有一个[0,n)的排列，你要构造一个数组a使得数组的值最小，值的运算方法：max(a[i]^a[i+1])(1<=i<n)

题解：

依旧是拓展思维…那么这道题目我们想要使得答案最小，肯定要让相邻两个数的高位尽量相等呀。比如7,3,4三个数，肯定要让4和7放在一起将最高位消掉才行。
那么从最高位的方面去考虑，是否应该将最高位都是1的放在一起？那具体怎么放才能最小？它们内部的问题我并没有去探讨，因为我发现了一件事情：你这个连续的数必然也是要与其它数交界的，当然你可以选择一端在边界，另一端呢？肯定是要与最高位不是1的数接触，那么异或之后最高位的1肯定存在，那么如何使剩下的位最小呢？那么让1000…B和0B接触不就好了？剩下的你们随便排，反正最大值已经是1000…B了，剩下的无论怎么排都不会更大。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int t=1;while(t<n)t<<=1;t>>=1;for(int i=1;i<t;i++)printf("%d ",i);printf("0");for(int i=t;i<n;i++)printf(" %d",i);printf("\n");}return 0;
}

这篇关于Codeforces 1632 B. Roof Construction —— 简单位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---