做阀门网站效果怎么样,宁波做网站的哪个好,邢台网站推广公司,建设了网站要维护吗题目
poj 链接 洛谷链接 n n n 组数据#xff0c;每组数据给定两个 01 01 01 串#xff08;长度不超过 3000 3000 3000#xff09;#xff0c;意思如下#xff1a;
对于每一个 0 0 0#xff0c;代表该节点有一个子节点#xff0c;并前往该子节点。对于每一个 1 1 …题目
poj 链接 洛谷链接 n n n 组数据每组数据给定两个 01 01 01 串长度不超过 3000 3000 3000意思如下
对于每一个 0 0 0代表该节点有一个子节点并前往该子节点。对于每一个 1 1 1代表返回该节点的父亲节点。
求两个字符串说表示的树是否同构。
思路
考虑对于每一个节点进行递归处理因为可以知道一个大问题可以拆成多个小问题进行计算。为方便后续操作可虚构一个根节点的父亲节点即在字符串开头加上 0 0 0结尾加上 1 1 1。
对于每一个节点我们可以获得一个字符串代表该节点的子树首先去掉头尾的字符即去掉通往父亲节点的边记 S S S 为字符串 c n t cnt cnt 表示 S S S 从 0 0 0 到 i i i 中 0 0 0 的数量与 1 1 1 的数量的差 j j j 表示儿子的数量。容易得到以下结论
对于 S i 0 S_i 0 Si0,则 c n t ← c n t 1 cnt \gets cnt 1 cnt←cnt1。对于 S i 0 S_i 0 Si0,则 c n t ← c n t − 1 cnt \gets cnt - 1 cnt←cnt−1。对于 c n t 0 cnt 0 cnt0即一个儿子已经遍历结束则 j ← j 1 j \gets j 1 j←j1并统计前一个儿子所代表的子串进行递归。
如果全部儿子所代表的子串递归完毕可按照字符串排序的方式排列儿子所代表的字符串并在头尾添上 01 01 01。可以发现对于两个同构的树以上操作后获得的字符串相等。
代码
#includebits/stdc.h
#define int long long
using namespace std;
int T;
string a,b;
string paixu(string x) {//coutxendl;// 分离操作string y x;int num x.size(),cnt 0;x ;if(num 2) return y;for(int i 1;i num - 1;i) x y[i];num - 2;string new_string[1505];int j 1;for(int i 0;i num;i) {if(x[i] 0) cnt,new_string[j] 0;else cnt--,new_string[j] 1;if(cnt 0) {j;}}j--;//递归for(int i 1;i j;i) new_string[i] paixu(new_string[i]);//排序for(int i j;i 1;i--) {for(int k 1;k i;k) {if(new_string[k] new_string[k 1]) swap(new_string[k],new_string[k 1]);}}for(int i 2;i j;i) new_string[1] new_string[i];//cout(0 new_string[1] 1)endl;return (0 new_string[1] 1);
}
signed main() {scanf(%lld,T);while(T--) {cin a b;a 0 a 1;b 0 b 1;if(paixu(a) paixu(b)) printf(same\n);else printf(different\n);}return 0;
}
