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
版权声明:本文标题:Roof Construction(异或构造) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728396576a1157076.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论