Xum
洛谷传送门
-
题意：
简化来说就是给你一个奇数 \(x\)，而你只能使用 \(+\) 或 \(\bigoplus\)，让你构造出一个包含 \(1\) 的数集。
-
Analysis：
首先为了得到 \(1\)，我们一般有两种思路，第一种是构造出 \(n\) 与 \(n+1\) 这种“出解情况”，这种思路考场寄掉了，先咕。
那么来说说正解思路：
对于一个数 \(x\)，我们考虑它的运算集：“\(+\)”可以实现二进制数的左移操作，而 \(\bigoplus\) 本身就是二进制操作，因此，我们考虑以下转移：说明：未知位用a代替，设二进制数长度为 \(k\)。
\[1aaaaaaa1\tag{1} \]左移 \(k\) 位得：
\[1aaaaaaa100000000\tag{2} \]\(1\) 式 \(\bigoplus\) \(2\) 式得：
\[1aaaaaaa0aaaaaaa1\tag{3} \]\(3\) 式 \(+\) \(2\) 式得：
\[1aaaaaaa10aaaaaaa1\tag{4} \]\(2\) 式自加后与 \(\bigoplus\) \(4\) 式得：
\[aaaaaaa1\tag{5} \]\(5\) 式 \(\bigoplus\) \(1\) 式即可得最高位：
\[100000000\tag{6} \] -
实现：
经过上述分析，我们已经实现了消去最高位，接下来只要一直循环求解下去即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define lowbit(x) (x&(-x))
int x;
struct Node{
int opt,x,y;
};
vector<Node> putout;
int solve(int x){
int y=x,ans=x>>1;
while(ans){
putout.push_back((Node){1,y,y});
y<<=1;
ans>>=1;
}
int z=x^y;
putout.push_back((Node){2,x,y});
int r=y+z;
putout.push_back((Node){1,y,z});
int s=y+y;
putout.push_back((Node){1,y,y});
int t=r^s;
putout.push_back((Node){2,r,s});
int u=t^x;
putout.push_back((Node){2,t,x});
while(y!=lowbit(y)){
if(y&u){
putout.push_back((Node){2,y,u});
y^=u;
}
putout.push_back((Node){1,u,u});
u+=u;
}
putout.push_back((Node){2,x,y});
x^=y;
return x;
}
signed main(){
scanf("%lld",&x);
while(x!=1) x=solve(x);
printf("%lld\n",putout.size());
for(int i=0;i<putout.size();i++){
if(putout[i].opt==1) printf("1 %lld %lld\n",putout[i].x,putout[i].y);
else if(putout[i].opt==2) printf("2 %lld %lld\n",putout[i].x,putout[i].y);
}
return 0;
}