P10477 题解
题目传送门
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 和 1去掉,才算是以这个子树的根为起点)
Step 3 思路解释
先输入字符串 s 1 s_1 s1, s 2 s_2 s2,然后去寻找和为 0 0 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)!