思路：模拟

积木每个单位的高度为1或2，拼接后不能超过3，所以耦合需要1和2的组合，即不能同时为2。

由于数据较小，因此模拟即可。判断串s的一个后缀是否能够与t的前缀耦合，即判断这两部分是否同时出现了2。

因此时间复杂度为$O(N^2)$

代码

Java

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        // 读取两个整数 a 和 b
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        // 读取两个字符串 s 和 t
        String s = sc.next();
        String t = sc.next();

        // 初始答案为 a 和 b 的和
        int ans = a + b;

        // 检查 s 的后缀和 t 的重叠部分
        for (int i = 0; i < s.length(); i++) {
            if (isValidOverlap(s.substring(i), t)) {
                int overlapLength = i + Math.max(s.length() - i, t.length());
                ans = Math.min(ans, overlapLength);
            }
        }

        // 检查 t 的后缀和 s 的重叠部分
        for (int i = 0; i < t.length(); i++) {
            if (isValidOverlap(t.substring(i), s)) {
                int overlapLength = i + Math.max(t.length() - i, s.length());
                ans = Math.min(ans, overlapLength);
            }
        }

        // 输出最小的重叠长度
        System.out.println(ans);
    }

    // 判断两个字符串的当前部分是否可以重叠
    private static boolean isValidOverlap(String s, String t) {
        int minLength = Math.min(s.length(), t.length());
        for (int i = 0; i < minLength; i++) {
            if (s.charAt(i) == '2' && t.charAt(i) == '2') {
                return false; // 如果两个字符串在同一位置上都为 '2'，则不能重叠
            }
        }
        return true; // 如果没有冲突，则返回 true
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> first_bricks;
vector<int> second_bricks;

int main() {
    string s1;
    string s2;

    cin >> n >> m;
    cin >> s1 >> s2;

    first_bricks.resize(n);
    second_bricks.resize(m);

    for (int i = 0; i < n; i++) {
        first_bricks[i] = s1[i] - '0';
    }
    for (int i = 0; i < m; i++) {
        second_bricks[i] = s2[i] - '0';
    }
    int ans = n + m;

    vector<int> sum(2 * n + m, 0);
    int second_begin_idx = n;
    int second_end_idx = n + m;
    for (int i = 0; i < n + m; i++) {
        int first_begin_idx = i;
        int first_end_idx = i + n;
        int flag = 0;

        for (int j = 0; j < 2 * n + m; j++) {
            int top_v = (j >= first_begin_idx && j <= first_end_idx) ? first_bricks[j - first_begin_idx] : 0;
            int bottom_v = (j >= second_begin_idx && j <= second_end_idx) ? second_bricks[j - second_begin_idx] : 0;
            if (top_v + bottom_v == 4) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            ans = min(ans, max(first_end_idx, second_end_idx) - min(first_begin_idx, second_begin_idx));
        }
    }

    cout << ans;

    return 0;
}

Python

temp_in = input().split()
n, m = int(temp_in[0]), int(temp_in[1])
s_n = input().split()[0]
s_m = input().split()[0]

def calc(n, m, s_n, s_m):
    result = m+n
    m_2 = [idx for idx, c in enumerate(s_m) if c == '2']

    for i in range(2):
        # 积木n 正向/反向 两种情况
        # if i == 1:
        #     s_n = s_n[::-1]
        n_2 = [idx for idx, c in enumerate(s_n) if c == '2']
        
        # 构造一个m+n+1的空间用来存储本次可以成功拼接的情况
        # 字符串n不动，只移动m，记录m的第一个字符的位置
        record = [ _ for _ in range(m+n+1)]
        for m_i in m_2:
            for n_i in n_2:
                temp_idx = m + n_i - m_i
                record[temp_idx] = -1
        # print(record)

        # 计算每种拼接情况的总长度
        for idx in record:
            if idx != -1:
                temp_ans = m+n
                if idx < m:
                    temp_ans = max(m, m-idx+n)
                else:
                    temp_ans = max(n, idx)
                if temp_ans < result:
                    result = temp_ans    
                    # print(idx, temp_ans)       
        
    return result
print(calc(n, m, s_n, s_m))

题目描述

NN有一种锯齿状的积木，这种积木比较长，但是每个单位长度的高度是相等的高度为 1 或者 2。

现在NN拿出了两块长度分别为n和 m 的积木，她现在想把这两块积木拼接在起，即使中间有空隙也没有关系。

但是拼接后的积木的高度要不超过 3，请你帮助NN计算在满足这个前提下拼接后的积木的长度最短可以是多少。

注：本题正解应当考虑积木可以翻转，但是考场上不翻转积木反而AC了，所以本题应当额外加上“不能够翻转积木”的条件

输入描述

第一行给出两个正整数 n,m，代表第一块和第二块积木的长度

第二行给出 n 个数字代表第一块积木每个单位的高度

第三行给出 m 个数字代表第二块积木每个单位的高度 $1\le n,m\le 1000$

输出描述

一个整数，表示拼接后的积木的最短长度

样例

输入

7 10
2212112
2112112112

输出

10

输入

3 2
222
22

输出

5