【有根树最小表示】AcWing 157

传送门

最小表示这颗有根树,注意要加入哨兵元素

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
string gao(string &s, int &i)
{
    vector<string> v;
    i++;
    while(s[i] == '0')
    {
        v.push_back(gao(s, i));  
    }
    i++;
    string res = "0";
    sort(v.begin(), v.end());
    for(auto &str: v) res += str;
    res += "1";
    return res;
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> s1 >> s2;
        s1 = '0' + s1 + '1';
        s2 = '0' + s2 + '1';
        int n = 0, m = 0;
        //cerr << gao(s1, n) << ' ' << gao(s2, m) << endl;
        //n = 0, m = 0;
        if(gao(s1, n) == gao(s2, m)) puts("same");
        else puts("different");
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注