[数据结构与算法]Daimayuan Online Judge 异或和或

代码源每日一题

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

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

• 选择两个下标?1≤i,j≤n(i≠j)1≤i,j≤n(i≠j)。

• 记x=ai?xor?ajx=ai?xor?aj?,?y=ai?or?ajy=ai?or?aj?, 其中?xorxor?表示按位异或 ,?oror?表示按位或。

• 然后令?ai=x,aj=yai=x,aj=y?或?ai=y,aj=xai=y,aj=x。

给定两个0101序列?s,ts,t?, 请你判断是否可以通过有限次(可以为00次)操作将序列?ss?变为?tt。

输入格式

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

每组第一行一个0101字符串?s(1≤|s|≤103)s(1≤|s|≤103)，每组第二行一个0101字符串?t(1≤|t|≤103)t(1≤|t|≤103)。

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

输出格式

如果可以通过有限次(可以为00次)操作将序列?ss?变为?tt?, 输出?YES?, 否则输出?NO。

样例输入

2
001
011
11
101

样例输出

YES
NO

样例解释

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

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

思路：刚开始写错了，是因为没有考虑选中的两个数能够无限次数变化，例如：10与01，先将10变换为1 1，1 1又能变换成0 1.这是经过两次变化，所以我们便不再用模拟去写直接就是思维题了。因为1与0能生出1，而1 1又能生出0，所以一位一位的考虑便能一直生出0与1，但是最后一位的1最后会留下来，它与任何位数上组合也就顶多算是交换位置或者有多出一个1，所以一定会有一个1留下来。那么我们只用考虑1的个数即可。

完整代码：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
//#define int long long
#define fir first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define repd(i, l, r) for (int i = l; i >= r; --i)
#define pb push_back


string s;
string s2;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>s;
        cin>>s2;
        int one=0;
        int zero=0;
        if(s.size()!=s2.size())
        {
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='0')zero++;
            else one++;
        }
        int one2=0,zero2=0;
        for(int i=0;i<s2.size();i++)
        {
            if(s2[i]=='0')zero2++;
            else one2++;
        }
        if(one&&!one2)
        {
            cout<<"NO"<<endl;
        }
        else if(!one&&one2)
        {
            cout<<"NO"<<endl;
        }
        else if(one2&&one)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;
        }
    }
    return 0;
}