自动搬运

查看原文

来自洛谷，原作者为

	billhenry bbbbbbbbbbbb

搬运于2025-08-24 21:49:32，当前版本为作者最后更新于2025-07-27 19:45:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目要求的是任意字符的后缀+若干字符+这个字符后一定走回根的字符。

方法：打两个标记深搜。

第一个标记为这个点是不是一个后缀+若干字符。先搜一遍所有点的后缀，打上第一个标记，接着从任意标记点开始走，走任意一个字符，如果走完了这个字符，且这个标记点没走到根，那么这个字符是不合法的，同时如果此时走到的位置没有标记，那么就可以打上第一个标记加入队列。

第二个标记是走到编码树的某个节点时，标记点是否走过根。

以下是代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 2100000
#define maxm 3010000

int n,m,id[maxn],in,son[maxn][3],tot,t[maxn],tp,ans[maxn],ansn;
char str[maxn];
bool suf[maxn],back1[maxn],ok[maxn];

void dfs(const int p1,const int p2){
	if(!son[p1][0]){
		dfs(1,p2);
		return;
	}
	if(!son[p2][0]){
		if(!suf[p1]) suf[t[++tp]=p1]=true;
		return;
	}
	dfs(son[p1][0],son[p2][0]);
	dfs(son[p1][1],son[p2][1]);
	return;
}

void dfs1(const int p1,const int p2){
	if(!son[p2][0]){
		if(!back1[p1]){
			back1[p1]=true;
			dfs1(p1,1);
		}
		return;
	}
	if(!son[p1][0]){
		if(p2!=1) ok[p1]=false;
		if(!suf[p2]){
			suf[p2]=true;
			dfs1(1,p2);
		}
		return;
	}
	dfs1(son[p1][0],son[p2][0]);
	dfs1(son[p1][1],son[p2][1]);
	return;
}

int main(){
	scanf("%d",&n);
	scanf("%s",str+1);
	
	t[tp=1]=tot=1;
	
	for(int i=1;i<=n;i++){
		char cc=str[i];
		if(cc=='1'){
			son[t[tp]][1]=++tot;
			t[++tp]=tot;
		}
		else if(cc=='0'){
			son[t[tp]][0]=++tot;
			t[++tp]=tot;
		}
		else if(cc=='B') tp--;
		else id[t[tp]]=++in;
	}
	tp=0;
	for(int i=2;i<=tot;i++) dfs(1,i);
	for(int i=1;i<=tot;i++)
		if(id[i]) ok[i]=true;
	for(int i=1;i<=tp;i++) dfs1(1,t[i]);
	
	ansn=0;
	for(int i=1;i<=tot;i++)
		if(ok[i]) ans[++ansn]=i;
	//for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
	printf("%d\n",ansn);
	for(int i=1;i<=ansn;i++) printf("%d\n",id[ans[i]]);
	
	return 0;
}