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

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。