​Problem - 2146D1 - Codeforces​

Problem - 2146D1 - Codeforces

题意很简单 给定一个从0开始的排列 b 重排b 得到a 使得sum(a|b)最大 b按顺序给出

首先 a|b 操作 我们可以看作a+b-a&b 那么我们只需要让所有的a&b 的和最小即可 观察样例发现 所有的答案都是（n+1）*n 所以我们猜测 存在一种重新排列的方式 使得所有的a&b =0

首先对于r=2^k-1 的情况 也就是 r的所有位置为1 的时候 我们可以直接对称进行构造
比如r=15 我们可以0于15 1与14 2与13 也就是（r-i）&i 一定为0 因为r全为1 r-i 就是去掉了i中为1 的部分 与i进行& 操作结果一定是 0 所以对于这种情况我们可以直接倒序输出

当r不等于2^k-1的时候 也就是会多一位最高位的时候 我们发现 最高位有1 的部分 如果去掉最高位 那么他们剩下的部分和低一位的时候没有区别

换句话说

01 2 3 4 5 6 7 他们本来是对称对称进行&的 全部为0 但是如果当前多了一个8 和9

8和9 去掉最高位后就是 0 和1 而0和1 本来就是和7 和6 进行&操作 所以我们可以令8 9 看作0 1 与7 6 进行&操作 然后剩下的部分重复这一过程即可

形式的 我们找到最高与r一致 并且所有位为1 的值m m-i 与i一定是&后为0 的 我们令i在（m-r 到r）范围 这样剩下的部分重复进行操作即可

#include <bits/stdc++.h> using namespace std; #define int long long const int N=2e5+5; int a[N]; void solve(){ int l,r; cin>>l>>r; int n=r-l+1; int r1=r; cout<<(r+1)*r<<'\n'; while(r1>=0){ int bit=0; int tmp=r1; while(tmp){ tmp/=2; bit++; } int m=(1<<bit)-1; int st=m-r1; for(int i=st;i<=r1;i++){ a[i]=m-i; } r1=st-1; } for(int i=0;i<n;i++){ cout<<a[i]<<' '; }cout<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--)solve(); return 0; }