Codeforces Round#769(Div.2) B. Roof Construction

本文主要是介绍Codeforces Round#769(Div.2) B. Roof Construction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定一个0至n-1的全排列，一个排列的消耗为数字与其相邻的异或，问如何排列能使消耗最小，并给出排列。

题解

我们首先来考虑消耗最小能是多少，异或的特点是相同为0，不同为1，考虑最高位的1，无论如何放置，无法使得最高位1的附近没有最高位为0，比如说 000 ，001，010，011，100，101，110，111
我们将最高位为1的放在最左边，由于不能放最高位为0的，那我们依次从左到右区放置，最后一定有个最高位为1的的右边为0，所以答案无法比最高位1更小。所以最小消耗，假定是n为10，那么最高位k=3，那么就是2^k=8，只要构造出该排列的消耗小于2^k即可。我们以2^k为分界点，比2^k小的数无论如何排列都无所谓，因为最大超不过2^k,2^k的2进制形式为100000……,所以在其左边放置一个000000……，比2^k大的数只要保证附近最高位一定为1即可，那最终构造的数列为： 001，010，011，000，100，101，110，111，顺序排列遇到2^k左边放0.

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10,mod=1e9+7;
typedef long long ll;
int a[N],st[N];
void solve()
{int n;cin >> n;int pow = 1;while (pow * 2 <= n - 1)pow *= 2;int cnt = 0;for (int i = 1; i <= n - 1; i++){   if (i == pow)a[cnt++] = 0;a[cnt++] = i;}for (int i = 0; i <= n - 1; i++)cout << a[i] << " ";cout << endl;
}
int main()
{int t;cin >> t;while (t--)solve();
}

这篇关于Codeforces Round#769(Div.2) B. Roof Construction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---