题解：CF1618F Reverse

WYZqaq · 2026-06-10 19:39:33 · 题解

首先，我们先考虑单独处理前两步，两个数相等的情况特判。

不难发现，前两步的处理只有 4 种情况可以操作，之后，我们发现，数字的反转操作可以不需要新增数字，也就是说，数字的反转操作可以通过加 0 操作进行，不会增加任何数字。

之后，不难发现前两步做完之后就只能加 1，不可以加 0，这是显然的。

所以，我们处理出前两步操作后的所有情况，去到目标串钟进行匹配，如果剩余部分均为 1，即可成功。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int num[105];
int num1[105];//加1不再翻 
int num2[105];//加1再翻
int num3[105];//加0不再翻 
int num4[105];//加0再翻 
int to[105];
main(){
    int x,y;
    cin>>x>>y;
    if(x==y){
        cout<<"Yes";
        return 0;
    }
    int tot=0;
    int k=x;
    int dick=y;
    while(x){
        num[++tot]=x%2;
        x/=2;
    }
    x=k;
    int tot1=0;
    while(y){
        to[++tot1]=y%2;
        y/=2;
    }
    y=dick;
    num2[1]=1;
    for(int i=1;i<=tot;i++){
        num2[i+1]=num[i];
    }
    for(int i=1;i<=tot+1;i++)num1[i]=num2[tot-i+2];
    int biao=0;
    for(int i=1;i<=tot;i++){
        if(num[i]==1){
            biao=i;
            break;
        }
    }
    int cnt=tot-biao+1;
    for(int i=1;i<=cnt;i++){
        num4[i]=num[i+biao-1];
    }
    for(int i=1;i<=cnt;i++){
        num3[i]=num4[cnt-i+1];
    }
    bool ans=false;
    for(int i=1;i<=tot1;i++){
        bool flag=true;
        if(i+tot+1-1>tot1){
            break;
        }
        for(int j=1;j<=tot+1;j++){
            if(to[i+j-1]!=num1[j]){
                flag=false;
                break;
            }
        }
        for(int j=1;j<i;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        for(int j=i+tot+1;j<=tot1;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        if(flag){
            ans=true;
            break;
        }
    }
    for(int i=1;i<=tot1;i++){
        bool flag=true;
        if(i+tot+1-1>tot1){
            break;
        }
        for(int j=1;j<=tot+1;j++){
            if(to[i+j-1]!=num2[j]){
                flag=false;
                break;
            }
        }
        for(int j=1;j<i;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        for(int j=i+tot+1;j<=tot1;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        if(flag){
            ans=true;
            break;
        }
    }
    for(int i=1;i<=tot1;i++){
        bool flag=true;
        if(i+cnt-1>tot1){
            break;
        }
        for(int j=1;j<=cnt;j++){
            if(to[i+j-1]!=num3[j]){
                flag=false;
                break;
            }
        }
        for(int j=1;j<i;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        for(int j=i+cnt;j<=tot1;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        if(flag){
            ans=true;
            break;
        }
    }
    for(int i=1;i<=tot1;i++){
        bool flag=true;
        if(i+cnt-1>tot1){
            break;
        }
        for(int j=1;j<=cnt;j++){
            if(to[i+j-1]!=num4[j]){
                flag=false;
                break;
            }
        }
        for(int j=1;j<i;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        for(int j=i+cnt;j<=tot1;j++){
            if(to[j]!=1){
                flag=false;
                break;
            }
        }
        if(flag){
            ans=true;
            break;
        }
    }
    cout<<(ans==true?"YES":"NO");
    return 0;
}