POJ 1635 Subway tree systems （树的最小表示法）

题意：一串01序列，从一个点开始，0表示去下一个点，1表示回到上一个点，最后回到起点，遍历这棵树时每条边当且仅当走2次（来回）

给出两串序列，判断是否是同一棵树的不同遍历方式

题解:我们把每一个节点下个每棵子树形成的01序列排序（我们把01序列看做括号序列，0看做'（', 1看做‘）’，则就是把每个并列的括号序列排序），再比较得出的字符串就好。

方法：把不标准的东西标准化，再比较。注意我们要保证标准化是唯一的

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

char str[Max];

string dfs(int now)

{

    vector<string> vec;

    while(str[now]=='')//可看做‘(’

    {

        vec.push_back(''+dfs(now+));

        now+=vec.back().size();//末尾元素的长度

    }

        string tem;

    sort(vec.begin(),vec.end());//将01序列进行排序

    int m=vec.size();

    for(int i=;i<m;++i)

        tem+=vec[i];

    return tem+'';//看做‘)’

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",str);

        string op1=dfs();

        scanf("%s",str);

        string op2=dfs();

        if(op1==op2)

            printf("same\n");

        else

            printf("different\n");

    }

    return ;

}

巴特西

POJ 1635 Subway tree systems （树的最小表示法）

最新文章

热门文章