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;
}

原文地址：https://blog.csdn.net/dengqingrui123/article/details/140850870

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！