【洛谷P4341】外星联络

前言

期末考试考进前\(68.29\)名我吃shi。

题目

题目连接：https://www.luogu.com.cn/problem/P4341
给出一个01串，按字典序输出每一个出现次数超过1的子序列的出现次数。

思路

随机跳到这道题的。一眼\(Tire\)。
然后就当模板题打了。。。练一下手顺便白嫖一道紫。
建立一棵01\(Tire\)，记录每一个点的到达次数，最后\(dfs\)一边即可。
空间过得去。

代码

#include <cstdio>
#include <cstring>
using namespace std;

const int N=3010;
int n,tot=1,a[N],trie[N*N][2],sum[N*N];

void update(int i)
{
	int p=1;
	for (;i<=n;i++)
	{
		if (!trie[p][a[i]]) trie[p][a[i]]=++tot;
		p=trie[p][a[i]];
		sum[p]++;
	}
}

void dfs(int x)
{
	if (sum[x]>1) printf("%d\n",sum[x]);
	if (trie[x][0]) dfs(trie[x][0]);
	if (trie[x][1]) dfs(trie[x][1]);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%1d",&a[i]);
	for (int i=1;i<=n;i++)
		update(i);
	dfs(1);
	return 0;
}