前言

期末考试考进前\(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;
}

【洛谷P4341】外星联络

原文：https://www.cnblogs.com/stoorz/p/12182378.html