​Problem - 2146D1 - Codeforces​

Problem - 2146D1 - Codeforces题意很简单 给定一个从0开始的排列 b 重排b 得到a 使得sum(a|b)最大 b按顺序给出首先 a|b 操作 我们可以看作ab-ab 那么我们只需要让所有的ab 的和最小即可 观察样例发现 所有的答案都是n1*n 所以我们猜测 存在一种重新排列的方式 使得所有的ab 0首先对于r2^k-1 的情况 也就是 r的所有位置为1 的时候 我们可以直接对称进行构造比如r15 我们可以0于15 1与14 2与13 也就是r-ii 一定为0 因为r全为1 r-i 就是去掉了i中为1 的部分 与i进行 操作结果一定是 0 所以对于这种情况我们可以直接倒序输出当r不等于2^k-1的时候 也就是会多一位最高位的时候 我们发现 最高位有1 的部分 如果去掉最高位 那么他们剩下的部分和低一位的时候没有区别换句话说01 2 3 4 5 6 7 他们本来是对称对称进行的 全部为0 但是如果当前多了一个8 和98和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 N2e55; int a[N]; void solve(){ int l,r; cinlr; int nr-l1; int r1r; cout(r1)*r\n; while(r10){ int bit0; int tmpr1; while(tmp){ tmp/2; bit; } int m(1bit)-1; int stm-r1; for(int ist;ir1;i){ a[i]m-i; } r1st-1; } for(int i0;in;i){ couta[i] ; }cout\n; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while(t--)solve(); return 0; }