题解：P12682 【MX-J15-T2】叉叉学习位运算

Nephren · 2025-06-01 18:13:51 · 题解

思路详解

需要点思维的题，主要是考察二进制。

因为 >>1 和 <<1 这两个操作是在二进制的基础上实现的，所以我们先把 a 和 b 转换成二进制再考虑。

而使用这两个运算后对原数最明显的变化就是所有数向左或向右移动一位，如果溢出，就会导致消失一位，且移动后留下的空位以 0 补缺。于是在经历多次操作后，我们就能让 a 的二进制形式前后各消失几位，因为前导零不影响二进制转十进制的计算，后导零可以通过右移来使其消失，从而修改 a 的十进制数值。

又因为二进制相等的两个数相等，所以只需要通过删去 a 的二进制形式的前后几位，使其与 b 的二进制形式相等就能完成任务。换句话说，只要 b 的二进制形式是 a 的二进制形式的子串即可完成任务。

写完代码提交后我们就会发现只能获得 10 分，还不如特殊性质获得的 20 分多。问题就出在 b 的二进制形式的后导零上。因为左移可以增加后导零，而在判断是否为子串的过程中可能会被 a 的二进制形式中的其他位干扰，所以要提前去掉 b 的二进制形式的后导零再进行判断子串的操作。

然后就可以获得 70 分。注意到 a 和 b 的上限到达了 2^{64}，所以 long long 肯定会爆，因此需要用 __int128来代替它，这里我使用重载运算符来读入，这样就能获得满分了。

代码

#include<bits/stdc++.h>
using namespace std;
long long t;
std::istream& operator>>(std::istream& is, __int128& n)
{
    string s;
    is>>s;
    n=0;
    bool negative=false;
    size_t start=0;
    if (s[0]=='-')
    {
        negative=true;
        start=1;
    }
    for(size_t i=start;i<s.size();i++)
    {
        n=n*10+(s[i]-'0');
    }
    if(negative)n=-n;
    return is;
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        __int128 a,b;
        long long c[100009],d[100009],e=0,f=0,ok1=0,qd0=1;
        cin>>a>>b;
        for(;a>0;)
        {
            e++;
            c[e]=a%2;
            a/=2;
        }
        for(;b>0;)
        {
            if(b%2!=0||qd0==0)
            {
                f++;
                d[f]=b%2;
                qd0=0;
            }
            b/=2;
        }
        for(int j=1;j<=e-f+1;j++)
        {
            int ok=1;
            for(int k=1;k<=f;k++)
            {
                if(d[k]!=c[j+k-1]){ok=0;break;}
            }
            if(ok==1){cout<<"Yes"<<endl;ok1=1;break;}
        }
        if(ok1==0)cout<<"No"<<endl;
    }
}

完结撒花！