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の倍数であれば、答えが得られます.
#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;
}