题目传送门
题目传送门（洛谷）
Step1 理解题意
- 一共有 T T T 组数据
- 有一个地铁，有一个中心车站（即为根），有一个人从中心车站出发。
- 对于每组数据，给定两个同样长度的01串 s 1 s_1 s1 , s 2 s_2 s2（即为他的遍历路线）
- 对于每个字符串， 0 0 0 代表离中心车站远一格， 1 1 1 代表离中心车站近一格。
- 问 s 1 s_1 s1 与 s 2 s_2 s2 所代表的遍历路线所形成的地铁是否一致
Step 2 样例解释
如上图，在第一个样例 0010011101001011 0010011101001011 0010011101001011 和 0100011011001011 0100011011001011 0100011011001011 中：
-
将 0 0 0 当作 1 1 1 , 1 1 1 当作 − 1 -1 −1
-
如果有一段子序列的和为 0 0 0,则说明又回到了根节点
-
比如 0010011101001011 0010011101001011 0010011101001011 中， 00100111 00100111 00100111、 01 01 01、 001011 001011 001011的和均为 0 0 0 结果为 4，1，3
-
同理，在 0100011011001011 0100011011001011 0100011011001011 中 01 01 01 、 00011011 00011011 00011011 、 001011 001011 001011 的结果为 0 0 0 结果为 1，4，3
-
可见 0010011101001011 0010011101001011 0010011101001011 和 0100011011001011 0100011011001011 0100011011001011 的结果为 s a m e same same
-
（ps：在截成的小段递归求解时，要把开头和结尾的 0 0 0 和 1 1 1 去掉，才算是以这个子树的根为起点）
Step 3 思路解释
先输入字符串 s 1 s_1 s1, s 2 s_2 s2,然后去寻找和为 0 0 0 的子串，然后将每一小块递归处理后，加入一个数组。扫描完成后，将数组排序，拼接，即最小表示。
- （ps：刚开始的时候要加上首位的 0 0 0 、 1 1 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;
}
------------------------------------------------------------------请多多指教-----------------------------------------------------------------------------------------
