Codeforces 1427E. Xum 题解

题目链接：E. Xum

题目大意：洛谷

题解：咋做法又和官方题解不一样啊。

一个很好想的思路是考虑每一次将最高位去掉转换成一个子问题，所以说我们的目标就是构造出最高位的那一个 1，即令 \(high_x\) 为 \(x\) 转换为二进制后最高的非 0 位，我们需要找到 \(2^{high_x}\) ，那么我们可以将 \(x\) 在二进制意义下向左平移使得平移最小的非 0 位与 \(high_x\) 相等，令这个数为 \(y\) ，然后再将两个数异或起来，这样的话我们就可以将 \(high_x\) 处置为 0，令这个数为 \(z\) ，然后再将 \(z+y\) 记为 \(p\)，紧跟着将 \(p\oplus x\) 得到 \(q\) ，最后在将 \(y+y\) 得到 \(h\) ，然后将 \(q\oplus h\) 得到 \(2^{high_x+1}\) ，然后在利用这一个数将 \(y\) 中在 \(>high_x\) 的位全部异或掉，这样的话我们就得到了 \(2^{high_x}\) ，可以将其转换成子问题。

可能上面讲得不太好理解，下面举一个例子（以下所有的数均为二进制下的数）：

x=000111
000111 + 000111 = 001110
001110 + 001110 = 011100
011100 ^ 000111 = 011011
011011 + 011100 = 110111
110111 ^ 000111 = 110000
011100 + 011100 = 111000
110000 ^ 111000 = 001000
011100 ^ 001000 = 010100
001000 + 001000 = 010000
010100 ^ 010000 = 000100
000111 ^ 000100 = 000011

至此，原问题成功地被转换为了规模更小的子问题。

时间复杂度以及操作数均为 \(O(\log^2 n)\) 。

代码：

#include 
typedef long long ll;
const int Maxn=100000;
int x;
struct Answer{
    int op;
    ll a,b;
}ans[Maxn+5];
int len;
bool vis[60];
void work(int x){
    if(x==1){
        return;
    }
    int high;
    for(int i=19;i>=0;i--){
        if((x>>i)&1){
            high=i;
            break;
        }
    }
    ll tmp=x;
    for(int i=0;i>i)&1){
            ans[++len].op=1;
            ans[len].a=tmp;
            ans[len].b=(1ll<