题解 - CF1937B Binary Path

Luogu

题意

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

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

分析

做这道题可以用 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();
	}
}