题解：CF1937B（Binary Path）

题解：CF1937B（Binary Path）

一、 理解题意

1. 题目链接

CodeForces；
洛谷。

2. 题目翻译

给定一个 由 $0$ 和 $1$ 组成的 $2$ 行 $n$ 列的网格上寻找一条路径，使得这条路径上所有的数串联起来形成的01串的字典序是所有路径里面最小的，并找出有多少种不同的做法能够取出相同的01串。

3. 数据范围

多测， $t$ 组数据，$1\le t\le 10^4$;
$1\le \sum n\le 2\cdot 10^5$。

二、 设计算法

1. 观察数据范围

本题可以接受 $O(n)$ 的线性做法。

2. 设计合理算法

这道题为什么只有 $2$ 行，而不是给定的 $m$ 行？
我们思考二者的区别，显然，对于前者，我们总共只会向下走一次。
进一步想。如果现在我们不在最下面一行或者最右面一列（也就是说我们可以向右或者向下走），假设这一步我们往右走，下一步我们可以继续向右（走到右侧的右侧）或者向下（走到右下侧），而假设我们这一步往下走，下一步我们只能向右走（走到右下侧）。显然，向右走的情况包括了向下走的情况。
因此，我们考虑贪心的走每一步，假设我们现在位于 $(x,y)$：
①当 $x=2$ 时，往右走；
②当 $y=n$ 时，往下走；
③当 $a_{x+1,y}\ge a_{x,y+1}$ 时，往右走；
④当 $a_{x+1,y}<a_{x,y+1}$时，往下走。
我们要记录唯一一次往下走是在哪一列（这里记为 $idz$），后面会用到。
现在我们已经知道最终的路径，但是如何求出一共有几种不同的情况呢？
显然，在第 $idz$ 列及它之前，如果有一段连续的区间使得区间内对于区间内所有的 $x$，$a_{1,x}$ 和 $a_{2,x-1}$ 都相等，那么在这一段区间内，选择哪个 $x-1$ 作为最终的那次往下走的步骤都是可以的。当然，这段连续区间的右端点必然是 $idz$。答案就是区间长度加上 $1$，加的就是我们贪心贪出来的那种情况。

3. 计算时间代价

妥妥的 $O(n)$，妥妥的 $AC$。

三、 实现代码

#include<bits/stdc++.h>
#define N 220000
using namespace std;
int t,n;
int sum[N];
char a[3][N];
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){sum[i]=0;}for(int i=1;i<=2;i++){scanf("%s",a[i]+1);}int idx=1,idy=1,idz=0;printf("%c",a[idx][idy]);while(idx!=2||idy!=n){if(idx==2){idy++;}else{if(idy==n){idx++;idz=idy;}else{if(a[idx][idy+1]==a[idx+1][idy]){idy++;}else{if(a[idx][idy+1]<a[idx+1][idy]){idy++;}else{idx++;idz=idy;}}}}printf("%c",a[idx][idy]);}printf("\n");int ans=1;for(int i=idz;i>1;i--){if(a[1][i]==a[2][i-1]){ans++;}else{break;}}printf("%d\n",ans);}return 0;
}