题解：CF1937B Binary Path

MhxMa · 2024-03-15 19:43:06 · 题解

题意

题目要求在一个二维网格中，从左上角出发，只能向右或向下移动，到达右下角的格子。网格中的每个格子包含一个二进制数。经过的路径上的数字按顺序连接成一个二进制字符串。现在要根据题意求解两个问题。

字典序是指字符串的大小关系，如果两个字符串长度相同，那么在第一个不同的字符处，较小的字符串对应的字符值要小于较大字符串对应的字符值。

分析

做这道题可以用 dp 求解，当然也可以用贪心，这里只讲 dp 的做法。

读入后，可以将 a 的第一个字符添加到一个临时字符串中（即初始化路径），同时将 b 中的字符添加到这个灵时字符串的末尾（即模拟移动过程），同时使用一个计数器标记至少有多少条路径。

接下来，使用一个队列来跟踪临时字符串中的字符是否需要更改，依次检查+判断：

• 如果后面的字符比当前字符大，那么我们已经得到了字典序最小的字符串，此时输出字符串和计数器的值，并结束程序。
• 如果后面的字符和当前字符相等，我们增加计数器的值。
• 如果后面的字符比当前字符小，我们将当前字符替换为后面的字符，并将需要更改的字符的下标加入队列中。

遍历队列元素，将队列中下标对应的位置对应的字符替换为 a 中下标相对的的字符，输出即可，输出的即为路径数量。

同时建议使用 char 读入。

代码

#include<bits/stdc++.h>
using namespace std;
char a[200005], b[200001];
void solv() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    string cur, ans;
    int cnt = 0;
    cur += a[1];
    for (int i = 1; i <= n; i++) {
        cur += b[i];
    }
    ans = cur;
    cnt = 1;
    queue<int> q;
    for (int i = 1; i < n; i++) {
        char pre = cur[i], nxt = a[i + 1];
        if (nxt > pre) {
            cout << cur << endl;
            cout << cnt << endl;
            return;
        } else if (nxt == pre)
            cnt++;
        else {
            cur[i] = nxt;
            q.push(i);
            while (!q.empty()) {
                ans[q.front()] = a[q.front() + 1];
                q.pop();
            }
            cnt = 1;
        }
    }
    cout << ans << endl;
    cout << cnt << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solv();
    }
}