題意

愛莉給了你一個非負整數 $n$，你需要把 $0,1,2,\dots ,n$ 劃分成若干組，滿足每一組的按位與為 $0$。

劃分的組不需要相鄰。

你需要最大化劃分組數并給出方案。

$1\le T\le 600$，$0\le n\le 10^5$，保證單個測試點內 $n$ 的和不超過 $2\times 10^5$。

思路

閑著沒事去看了兩眼，題目越簡潔，看著越嚇人，做法越要思考。實在沒想到這個只有黃的 T3，不過挺好玩的。

由打表樣例可見，每一組似乎都不超過 2 個。不妨就構造兩個兩個一組的答案，可能會多出一個 $0$，理論上可以得到 $?\frac{n+1}{2}?$ 組。

考慮怎么樣得到兩個數與起來為 $0$，需要二進制每一位要么相反要么均為 $0$。

假若有一個數 $2^x=(\mathrm{100...000}{)}_2$，其中 $0$ 有 $x$ 個，另一個數 $2^x?1=(\mathrm{11...111}{)}_2$，其中 $1$ 也有 $x$ 個；這二者與起來為 $0$，而若前者一直 $+1$，后者一直 $?1$，兩個數按位與起來總是為 $0$。為什么呢？每次 $+1$ 或者 $?1$，要么只改變末尾，要么發生進位改變高位——進位可能改變連續的高位。但是各位在初始狀態總是相反，所以兩個數同時改變各位依舊相反。

那么可以這樣構造：找到小于 $n$ 的最大 $2^x$，將 $n～2^x$ 加進隊列，然后從 $2^x$ 和 $2^x?1$ 依次向大和向小枚舉配對；設后者配對到 $pos$，當前者配對到 $n$ 就停下，然后向隊列中增補 $2^{x?1}～pos?1$，下一輪繼續遍歷到 $pos?1$ ……——如果還沒配對到 $n$，$pos$ 就到了 $2^{x?1}$ 怎么辦？此時 $2^{x?1}>pos?1$，可以直接忽略進隊列的操作，繼續把隊列里剩下的元素配對玩再說，根據上面的結論來看這時可行的。

最后看隊列有沒有剩下的，如果 $n$ 為奇數隊列中將會剩下一個，此時讓其和 $0$ 配對；否則 $0$ 自成一組。

講得有點口胡了。具體細節見代碼。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T,n;
ll p2[22];
void init()
{p2[0]=1;for(int i=1;i<=20;i++)p2[i]=p2[i-1]*2;
}
queue<ll>q;
void clean()
{while(!q.empty())q.pop();
}
int main()
{scanf("%lld",&T);init();while(T--){clean();scanf("%lld",&n);if(n==0){puts("1");puts("1 0");continue;}printf("%lld\n",(n+2)/2);ll x=upper_bound(p2+1,p2+21,n)-p2-1;for(int i=p2[x];i<=n;i++)q.push(i);for(int i=x-1;i>=0;i--){ll pos=p2[i+1]-1;while(!q.empty()&&pos>=p2[i]){printf("2 %lld %lld\n",pos,q.front());pos--;q.pop();}for(int j=p2[i];j<=pos;j++)q.push(j);}if(!q.empty())printf("2 0 %lld\n",q.front());else puts("1 0");}return 0;
}