AcWing 157 树形地铁系统(树的最小表示)

2020-12-26 06:27

阅读：399

标签：else 字符串地铁 puts http 完成 str end ref

题目链接

解题思路

??求出两个字符串代表的树的最小表示，进行比对就能得到答案，为了方便处理，给他设定一个根，即在开头加一个0，当然在结尾也要再加上一个0。
??关于最小表示的求法，每次都求出子树字典序最小的组合方式，然后向上合并为字典序最小的组合方式即可，显然可以用递归来完成。

代码

const int maxn = 1e5+10;
int u,p[maxn];
string dfs(string s) {
    ++u;
    vector tmp;
    while(s[u]==‘0‘) tmp.push_back(dfs(s));
    ++u;
    sort(tmp.begin(),tmp.end());
    string res = "0";
    for (auto s : tmp) res += s;
    res += ‘1‘;
    return res;
}
int main(){
    int t; cin >> t;
    while(t--) {
        string s1,s2;
        cin >> s1 >> s2;
        s1 = ‘0‘+s1+‘1‘;
        s2 = ‘0‘+s2+‘1‘;
        u = 0; string rs1 = dfs(s1);
        u = 0; string rs2 = dfs(s2);
        if (rs1==rs2) puts("same");
        else puts("different");
    }
    return 0;
}

AcWing 157 树形地铁系统(树的最小表示)

标签：else 字符串地铁 puts http 完成 str end ref

原文地址：https://www.cnblogs.com/shuitiangong/p/13378529.html

上一篇：window docker的安装

下一篇：重学c#系列——非托管实例(五)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 157 树形地铁系统(树的最小表示)
文章链接：http://soscw.com/index.php/essay/38290.html

亲，登录后才可以留言！

AcWing 157 树形地铁系统(树的最小表示)

解题思路

代码

评论

热门文章

推荐文章

最新文章

置顶文章