题解：P10477 Subway tree systems

Oct_ · 2024-05-18 17:07:16 · 题解

题目传送门

解题思路

把 0 看成 1，1 看成 -1。

对于一个子树，如果从开头到某一段的和为 0，表示又回到了这个子树的根。

根据子树把字符串截乘小段，再排序。字符串类型方便比较两个树是否相同。

注意截成的小段递归求解时，要把开头和结尾的 0 和 1 去掉，才算是以这个子树的根为起点（开头本来表示进入这个根，结尾本来表示离开这个根）。

好用的 STL：ss=s.substr(a,b)，a 为起点下标，b 为长度。

对于 vector 的排序：sort(vs,begin(),vs.end())

AC Code：

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
void stl(string &s)
{
    if(s=="01") return;
    s=s.substr(1,s.size()-2);
    int st=0,cnt=0;
    vector<string>vs;
    vs.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);
            stl(ss);
            vs.push_back(ss);
            st=i+1;
        }
    }
    sort(vs.begin(),vs.end());
    s='0';
    for(int j=0;j<vs.size();++j) s+=vs[j];
    s+='1';
    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cin>>s1;
        cin>>s2;
        s1='0'+s1+'1';
        s2='0'+s2+'1';//方便后面递归
        stl(s1);
        stl(s2);
        if(s1==s2) printf("same\n");
        else printf("different\n");
    }
    return 0;
}

拜拜！