牛客小白月赛4-F-等价串题解

你的名字 2022-12-28 11:17 141阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入分析
     *  输出分析
     *  输入
     *  输出
     *  说明
 *  算法分析
 *  解题代码

--------------------

链接：https://ac.nowcoder.com/acm/contest/134/F  
来源：牛客网

# 题目描述 #

一串长度为 **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”\*\*.输出不包括引号。

## 输入 ##

3
    3 4
    010
    1110
    3 4
    010
    1111
    7 2
    0001000
    00

## 输出 ##

YES
    NO
    YES

## 说明 ##

> 对于第一个样例，铁子可以对字符串A使用一次无情替换可以变成1110

# 算法分析 #

刚拿到这道题，以为很复杂，结果很简单

这道题思维转变一下，把 `串A` 和 `串B` 中的字符同时转换成字符`1` ，最后如果 `串A` 与 `串B` 相等，或者说 `串A` 和 `串B` 的长度相差`3*n`个字符`1`，即可以变换（因为3个字符 `1` 对于 `串A` 来说是可以被删除的，对于 `串B` 来说是可以被增加的）。

**那么现在的问题来了，怎么将两个字符串都转换成只包含 `1` 的字符串呢？**

*  对于 `串A` 而言可以用 `11` 替换 `0` ，用 `00` 替换 `1`。
 *  那么 `串A` 很好解决，用 `11` 去替换 `0` 即可
 *  而 `串B` 是由 `串A` 进行变换得来的，那么 `串B` 中的字符 `0` 是仅由 `串A` 由 <`00`替换`1`>的来的。
    
     *  如果串为 `00`，则用 `1` 替换 `00`。
     *  如果串为 `0`，则添加 `000`，变为 `0000`，因此用 `11` 时替换 `0`。

# 解题代码 #

#include <iostream>
    #include <string>
    #include <cmath>
    using namespace std;
    
    int main()
    {
        
        int t;
        cin >> t;
        
        while(t--){
        
            string s1,s2;
            int n,m;
            cin >> n >> m;
            
            cin >> s1 >> s2;
            
            string ss1 = "",ss2 = "";
          	//处理串A
            for(int i = 0; i < s1.size(); i++){
        
                if(s1[i] == '0')	//用11替换0
                    ss1 += "11";
                else
                    ss1 += s1[i];	//原本的1就保留下来
            }
            
            for(int i = 0; i < s2.size(); i++){
        
                if(s2[i] == '0'){
        
                    if((i < s2.size() - 1) && s2[i + 1] == '0'){
        	//用1替换00
                        ss2 += "1";
                        i++;
                        continue;
                    }
                    ss2 += "11";	//用11替换0
                }
                else
                    ss2 += s2[i];	//原本的1就保留下来
            }
            
          	//如果两个串相同，或者两个串长度相差3*n就说明，可经过变换得到
            if(ss1 == ss2 || abs((int)ss1.size() - (int)ss2.size()) % 3 ==0)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        
        return 0;
    }