代码源：500、异或和或-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是代码源div2的每日一题，对应cf分数1400。

知识点：位运算

异或和或 – 题目 – Daimayuan Online Judge

对于一个长度为 n 的0101序列 a1,a2,…,an。

你可以执行以下操作任意多次：

选择两个下标 1≤i,j≤n(i≠j)。
记x=ai xor aj , y=ai or aj , 其中 xor 表示按位异或 , or 表示按位或。
然后令 ai=x,aj=y 或 ai=y,aj=x。

给定两个01序列 s,t , 请你判断是否可以通过有限次(可以为0次)操作将序列 s 变为 t。

输入格式

第一行一个整数 t , 表示数据的组数(1≤t≤103)。接下来 t 组数据：

每组第一行一个01字符串 s(1≤|s|≤10^3)，每组第二行一个01字符串 t(1≤|t|≤103)。

注意：|s|可能不等于 |t|。

输出格式

如果可以通过有限次(可以为0次)操作将序列 s 变为 t , 输出 YES , 否则输出 NO。

样例输入

样例输出

YES
NO
复制代码

样例解释

第一组数据选择 i=2,j=3 , 那么 x=1,y=1 , 接着令 ai=x,aj=y 即可得到 t 序列。

第二组数据 |s|=2,|t|=3 显然无法满足要求。

问题解析

这题并不需要真的去遍历字符串s来把他变成字符串t的样子，我们只需要知道能否经过“^”和“|”两种运算将s变成t即可。在解决问题前，我们可以打个草稿来看看01与“^”和“|”的组合情况

当两边都是1的时候：1^1=0、1|1=1
当两边都是0的时候：0^0=1、0|0=0
当一边为1一边为0的时候：0^1=1、0|1=1（当然反过来也是一样1^0=1、1|0=1）

通过这三种情况我们不难看出，1可以只靠自己就能够变成0（1^1=0），也就是说即使字符串s全为0组成，我也可以通过^运算来凭空生成0，但是，并不能把所有的1都变成0，毕竟只靠1变成0的方法是：1^1=0,1|1=1，这样会使得一个1变成0，而另一个依然是1，而只靠1个1是无法变成0的，所以不管怎么样，1是无法被消除干净的，最少也会留下一个1。

但0并不能够靠自己来变成1（0^0=1、0|0=0），所以如果s全是0，那就无法发生任何变化了，毕竟只有0，怎么变都是0。

至于一个0一个1的情况，就是可以把一个0同化成1，另一个1也是变成1（没变化）。

现在就可以得出结论来了，如果s和t字符串的组成情况，其中一个是没有1，另一个是有1的情况下，两者是不可能变成一样的，毕竟没有1，只靠0是无法变成1的，而如果你有1，那你也无法消除完所有的1变成全是0。至于其他的情况，我们则总是有办法在有限的次数中完成s=t的转化的。

还有一点就是，我们一开始就可以先比较他们两个的长度，如果长度不一样那就直接输出NO即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        string s1, s2;
        cin >> s1 >> s2;
        int n = s1.size(), m = s2.size();
        if (n != m)
        {
            cout << "NO" << endl;
            continue;
        }
        int s1_zero = 0, s1_one = 0, s2_zero = 0, s2_one = 0;
        for (int i = 0; i < n; i++)
        {
            if (s1[i] == '0')s1_zero++;
            else s1_one++;

            if (s2[i] == '0')s2_zero++;
            else s2_one++;
        }
        if (s2_one == 0 && s1_one != 0)cout << "NO" << endl;
        else if (s2_one != 0 && s1_one == 0)cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}
复制代码