F - Robot Rotation
一句话不开LL,见祖宗
感谢大佬,和洛谷上的题解
上面已经将的很清楚了,但是如果你跟我一样一开始看不懂他们的代码,那么这篇可能为你解惑
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define int LL//LL!
map<LL,LL> ma;
int n,x,y ;
vector<int> a,b;
LL ansx=-1,ansy=-1;
void solve(){
ma.clear();
int len=a.size();
int llen=len/2;
LL sum=0;
for(auto v:a) sum-=v;//为了放便反向的减法,先全部减一遍,要加的时候加上双倍的就行了
//这里是选法,二进制状态压缩,1表示选正,0表示选负,i一开始为0,表示什么都不选(全为负),然后一位一位加上去,到最后二进制全为1表示全选正
for(int i=0;i<(1<<llen);i++){
LL res=0;
//双向搜索
for(int j=0;j<llen;j++){//二进制里为1就选正
if(i>>j&1) res+=2*a[j];//因为之前减过,所以要加上双倍才可以
}
ma[res]=i;//选法i(注意是i的二进制,也就是选法)
}
for(int i=0;i<(1<<(len-llen));i++){
LL res=0;
for(int j=0;j<len-llen;j++)
if(i>>j&1) res+=2*a[j+llen];
if(ma.count(x-(sum+res))) {//x=sum+res1+res2=>x-sum-res2
ansx=(i<<llen)+ma[x-sum-res];//合并在一起(二进制)
return;
}
}
}
signed main(){//LL!
cin>>n>>x>>y;
for(int i=1;i<=n;i++){
int v;
cin>>v;
if(i&1) b.push_back(v);//记录对y轴的改变
else a.push_back(v);//x轴
}
solve();
swap(a,b),swap(ansx,ansy),swap(x,y);//换一下,可以重复利用函数
solve();
swap(ansx,ansy);//转换回来
if(ansx==-1||ansy==-1) {//无解
cout<<"No";
return 0;
}
cout<<"Yes\n";
int to=1;//一开始朝x轴正方向
vector<char> c;
//当然也可以不用这么麻烦
for(int i=1;i<=n;i++){
if(i&1){//y轴,to肯定在x轴朝右(1)或者左(3)
int now=ansy&1;ansy>>=1;
if(now==0){//负向
if(to==1){
c.push_back('R');
}else{
c.push_back('L');
}
to=4;//更新to的朝向
}
else{//正向
if(to==1){//x轴正向
c.push_back('L');
}else{
c.push_back('R');
}
to=2;
}
}
else{//x轴
int now=ansx&1;ansx>>=1;//取出该位置的值,1为取正方向,0为负方向
if(now==0){
if(to==2){
c.push_back('L');//逆时针转到负向
}
else{
c.push_back('R');
}
to=3;
}
else{//正向
if(to==2){
c.push_back('R');//顺时针旋到正向
}
else{
c.push_back('L');
}
to=1;
}
}
}
for(auto v:c) cout<<v;
return 0;
}