自动搬运

查看原文

来自洛谷，原作者为

	Sky__Dream 自从遇见你，凛冬散尽，星河长明⎛⎝≥⏝⏝≤⎛⎝||主页暂时搬迁：https://www.luogu.com.cn/paste/80hamthc

搬运于2025-08-24 22:58:20，当前版本为作者最后更新于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;
}

拜拜！