hdu 6726 Transformation 2019百度の星再試合1002
2190 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=6726
A,B操作を考慮すると,A操作(a,2*(b−a)+a)->(a,4*(b−a)+a)->(a,8*(b−a)+a)のたびに,B操作も同様であることが分かった.
各a,b間の長さの増加は,元の長さのlen=abs(b−a)の2のべき乗倍であることがわかる.
また、a,bの移動の長さも元の長さlenの2のべき乗倍である
したがって,(a,b)がc,dに移動できる限り,答えは一意であり,辞書順の最小の問題は存在しない.
1つの問題に注意して、移動するときは(b-d)%len=0を判断しなければならない.なぜなら、lenの2のべき乗の倍を移動するたびに.
lenの2のべき乗次倍なので、b-dはlenの倍数であれば、答えが得られます.
A,B操作を考慮すると,A操作(a,2*(b−a)+a)->(a,4*(b−a)+a)->(a,8*(b−a)+a)のたびに,B操作も同様であることが分かった.
各a,b間の長さの増加は,元の長さのlen=abs(b−a)の2のべき乗倍であることがわかる.
また、a,bの移動の長さも元の長さlenの2のべき乗倍である
したがって,(a,b)がc,dに移動できる限り,答えは一意であり,辞書順の最小の問題は存在しない.
1つの問題に注意して、移動するときは(b-d)%len=0を判断しなければならない.なぜなら、lenの2のべき乗の倍を移動するたびに.
lenの2のべき乗次倍なので、b-dはlenの倍数であれば、答えが得られます.
#include
#define maxl 100010
using namespace std;
typedef pair p;
long long a,b,c,d,cnt;
bool flag;
int ans[maxl];
inline void prework()
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
}
inline bool jug(long long x)
{
cnt=0;
long long len=abs(c-d);
while(x<=len)
{
if(x==len)
return true;
x=x*2;cnt++;
}
return false;
}
inline void mainwork()
{
flag=false;long long x,len;
ans[0]=0;
if(a==b)
{
if(a!=c || b!=d)
{
flag=false;
return;
}
else
{
flag=true;
ans[0]=0;
}
}
else if(aa || d>=1ll;
}
}
else if(a>b)
{
x=a-b;
if(bc || !jug(x))
{
flag=false;
return;
}
if((b-d)%x!=0)
{
flag=false;
return;
}
flag=true;
long long num=(b-d)/x;
for(int i=1;i<=cnt;i++)
{
if(num&1ll)
ans[++ans[0]]=1;
else
ans[++ans[0]]=2;
num>>=1ll;
}
}
}
inline void print()
{
if(flag)
{
puts("Yes");
for(int i=1;i<=ans[0];i++)
printf("%c",'A'+ans[i]-1);
puts("");
}
else
puts("No");
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
prework();
mainwork();
print();
}
return 0;
}