P10477 题解

题目传送门

题目传送门（洛谷）

Step1 理解题意

• 一共有 $T$ 组数据
• 有一个地铁，有一个中心车站（即为根），有一个人从中心车站出发。
• 对于每组数据，给定两个同样长度的01串 $s_1$ , $s_2$（即为他的遍历路线）
• 对于每个字符串，$0$ 代表离中心车站远一格，$1$ 代表离中心车站近一格。
• 问 $s_1$ 与 $s_2$ 所代表的遍历路线所形成的地铁是否一致

Step 2 样例解释

如上图，在第一个样例 $0010011101001011$ 和 $0100011011001011$ 中：

• 将 $0$ 当作 $1$ , $1$ 当作 $-1$

• 如果有一段子序列的和为 $0$,则说明又回到了根节点

• 比如 $0010011101001011$ 中，$00100111$、$01$、$001011$的和均为 $0$ 结果为 4，1，3

• 同理，在 $0100011011001011$ 中 $01$ 、 $00011011$ 、 $001011$ 的结果为 $0$ 结果为 1，4，3

• 可见 $0010011101001011$ 和 $0100011011001011$ 的结果为 $same$

• （ps：在截成的小段递归求解时，要把开头和结尾的 $0$ 和 $1$ 去掉，才算是以这个子树的根为起点）

Step 3 思路解释

先输入字符串 $s_1$, $s_2$,然后去寻找和为 $0$ 的子串，然后将每一小块递归处理后，加入一个数组。扫描完成后，将数组排序，拼接，即最小表示。

• （ps：刚开始的时候要加上首位的 $0$ 、$1$ ，因为我们的递归是从进入一棵树开始的。）

Step 4 Ac code

#include<bits/stdc++.h>
using namespace std;
string s1,s2;

void fin(string &s){
	if(s=="01") return;
	s=s.substr(1,s.size()-2);
	int st=0,cnt=0;
	vector<string>pass;
	//pass.clear(); 
	for(int i=0;i<s.size();i++){
		cnt+=(s[i]=='0'?1:-1);
		if(!cnt){
			string ss=s.substr(st,i-st+1);
			fin(ss);
			pass.push_back(ss);
			st=i+1;
		}
	}
	sort(pass.begin(),pass.end());
	s='0';
	for(int j=0;j<pass.size();j++) s+=pass[j];
	s+='1';
	return;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		cin>>s1>>s2;
		s1='0'+s1+'1',s2='0'+s2+'1';
		fin(s1);fin(s2);
		if(s1==s2) printf("same\n");
		else printf("different\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

------------------------------------------------------------------请多多指教-----------------------------------------------------------------------------------------