本文已参加[新人创造礼]活动，一同开启创造之路
标题描述
这是代码源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。
样例输入
2
001
011
11
101
样例输出
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;
}
- 时刻复杂度：O(n)（咱们只需要遍历一次来得到两个字符串的组成状况）
