NC16652. 等价串
描述
一串长度为 n 的字符串 A 和一串长度为 m 的字符串 B。并且这两串字符串只会含有 0 或 1 。
铁子可以对字符串 A 执行两种操作，两种操作可以执行任意次。
操作1(无情替换):铁子可以用 11 替换掉 0 ，也可以用 00 替换掉 1 .
操作2(极限删除):铁子可以删除掉 111 ，也可以删除 000 .
现在问，字符串 A 可以变成字符串 B 吗？
输入描述
第一行有一个整数T，表示有T(1<=T<=1000)组测试数据。
接下来的每组数据，第一行有两个整数n，m(1<=n,m<=100)，表示字符串A和字符串B的长度。
接下来有两行字符串，分别表示字符串A和字符串B。
输出描述
对于每组测试数据，如果字符串A可以变为字符串B，则输出一行”YES”,否则输出一行”NO”.输出不包括引号。
示例1
输入:
3 3 4 010 1110 3 4 010 1111 7 2 0001000 00
输出:
YES NO YES
说明:
对于第一个样例，铁子可以对字符串A使用一次无情替换可以变成1110C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 620K, 提交时间: 2020-02-16 14:25:12
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,x=0,y=0;
cin>>n>>m;
string a,b;
cin>>a>>b;
for(int i=0;i<n;i++)
a[i]=='1'?x++:x+=2;
for(int i=0;i<m;i++)
b[i]=='1'?y++:y+=2;
puts((x-y)%3==0?"YES":"NO");
}
}
C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 496K, 提交时间: 2020-02-28 16:41:44
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n1,n2,k1,k2;
string a,b;
cin>>t;
while(t--)
{
n1=0,n2=0;
cin>>k1>>k2>>a>>b;
for(int i=0;i<k1;i++)
n1+=(a[i]=='1'?1:2),n1%=3;
for(int i=0;i<k2;i++)
n2+=(b[i]=='1'?1:2),n2%=3;
cout<<(n1==n2?"YES":"NO")<<endl;
}
}
Python3 解法, 执行用时: 56ms, 内存消耗: 4596K, 提交时间: 2022-01-11 11:36:16
for _ in range(int(input())):
a,b,c=input(),input(),input()
print("YES" if (b.count("0")+2*b.count("1"))%3==(c.count("0")+2*c.count("1"))%3 else "NO")