题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和一个$2$行$n$列的网格图，格子值只有0和1。

你从矩阵左上角出发，走到右下角。你只能向右/向下走。

把经过的格子值按顺序记录下来，得到一个长为$n+1$的01字符串。输出字典序最小的$01$字符串，以及有多少种走法可以得到该字符串。

输入样例

3
2
00
00
4
1101
1100
8
00100111
11101101

输出样例

000
2
11000
1
001001101
4

算法

贪心+字符串哈希

首先可以通过贪心的方式构造出字典序最小的路径，从$(1,1)$开始走，如果离右边的$1$更远就右移列指针，否则下移行指针。

由于路径一定是Z型，即在第一行走一段，然后急转直下后缀都在第二行上走。因此我们可以枚举那个转折点$j$，如果第一行$s_1$的前缀$[0,j]$和第二行$s_2$的后缀$[j,n)$分别与目标串的前缀$[0,j]$和后缀$[j+1,n]$相等，说明$j$是个合法的转折点，让方案数自增。要快速判断前后缀是否相等可以用字符串哈希来辅助。

复杂度分析

时间复杂度

贪心需要让$i$指针走完$[0,n)$，让$j$指针走完$[0,n)$，并且走完$n+1$步完成目标串（字典序最小的路径）的构造，因此时间复杂度为$O(n)$。

接下来枚举转折点$[0,n)$，判断每个转折点是否合法需要$O(1)$计算前缀和后缀的哈希值，时间复杂度还是$O(n)$。

综上，整个算法的时间复杂度为$O(n)$。

空间复杂度

两行的$1$索引列表均为$O(1)$的时间复杂度。目标串做字符串哈希额外空间为$n+1$，矩阵第一行和第二行做字符串哈希额外空间为$n$，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
int t, n;

class StringHash {
public:
    explicit StringHash(string& str, int base=131) {
        n = str.size();
        this->base = base;
        string s = "*" + str;
        h.resize(n + 1);
        p.resize(n + 1);
        p[0] = 1;
        for(int i = 1; i <= n; i++) {
            h[i] = h[i - 1]*base + s[i];
            p[i] = p[i - 1]*base;
        }
    }

    ULL shash(int left, int right) {
        ++left, ++right;
        return h[right] - h[left - 1]*p[right - left + 1];
    }

private:
    int base, n;
    vector<ULL> h, p;
};

int main() {
    cin >> t;
    while(t--) {
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        vector<int> pos1, pos2;
        for(int i = 0; i < n; i++) {
            if(s1[i] == '1') pos1.push_back(i);
            if(s2[i] == '1') pos2.push_back(i);
        }
        int x = 0, y = 0, i = 0, j = 0;
        string mn;
        while(y < n) {
            while(i < pos1.size() && pos1[i] <= y) i++;
            while(j < pos2.size() && pos2[j] < y) j++;
            int d1 = (i == pos1.size()? n: pos1[i]) - y;
            int d2 = (j == pos2.size()? n: pos2[j]) - y + 1;
            if(d1 >= d2) {
                mn.push_back(s1[y++]);
            }else {
                mn.push_back(s1[y]);
                x++;
                break;
            }
        }
        if(y == n && x == 0) {
            x++;
            mn.push_back(s2[y - 1]);
        }else {
            while(y < n) {
                mn.push_back(s2[y++]);
            }
        }
        cout << mn << endl;
        StringHash sh_target(mn);
        StringHash sh_pre(s1);
        StringHash sh_suf(s2);
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            ULL pre_hash = sh_target.shash(0, j);
            ULL suf_hash = sh_target.shash(j + 1, n);
            if(sh_pre.shash(0, j) == pre_hash && sh_suf.shash(j, n - 1) == suf_hash) {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}