首页 > 其他 > 详细

Luogu P3294 【[SCOI2016]背单词】

时间:2018-10-20 19:16:42      阅读:175      评论:0      收藏:0      [点我收藏+]

阅读理解题

。。。。。。

 



$Trie$

后缀问题不好处理,我们把它转化为前缀问题,用字典树解决问题

贪心

容易想到,一个串的后缀要先于它插入

对于一个串和其若干后缀串,容易想到,我们要先插入后缀串

然后递归进入$size$最小的子串

bool cmp(const int &x,const int &y)
{
    return size[x]<size[y];
}
void makes(int x)
{
    size[x]=1;
    for(int i=0;i<t[x].size();i++)
    {
        makes(t[x][i]);
        size[x]+=size[t[x][i]];
    }
    sort(t[x].begin(),t[x].end(),cmp);
}
void dfs(int x)
{
    id[x]=tot++;
    for(int i=0;i<t[x].size();i++)
    {
        ans+=tot-id[x];
        dfs(t[x][i]);
    }
}



注意

求$size$要重构树,只保留关键点

因为我太蒻了,并不会指针,所以提供一个并查集重构树的方法

在建$Trie$时给所有串的结尾和$Trie$树的根节点标号,表示新树中点的编号

void insert(const string &s,int id)
{
    int now=0,l=len[id];
    for(int i=0;i<l;i++)
    {
        int c=idx(s[i]);
        now=tr[now][c]?tr[now][c]:tr[now][c]=++cnt;
    }
    val[now]=id;
}



然后遍历$Trie$树,如果一个节点的子节点没有被标号,就把它并入当前节点的集合;否则把这个子节点作为当前节点所在集合的根的儿子(就是连一条边)

void make(int x)
{
    for(int v,i=0;i<26;i++)
        if(v=tr[x][i])
        {
            if(!val[v])
                f[v]=find(x);
            else
                t[val[find(x)]].push_back(val[v]);
            make(v);
        }
}



代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int maxl=510010,maxn=1e5+10;
int n,tr[maxl][30],val[maxl],cnt,len[maxn],size[maxn],tot,f[maxl],id[maxn],ans;
vector<int>t[maxn];
string st[maxn];
inline int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
inline int idx(char c)
{
    return c-a;
}
void insert(const string &s,int id)
{
    int now=0,l=len[id];
    for(int i=0;i<l;i++)
    {
        int c=idx(s[i]);
        now=tr[now][c]?tr[now][c]:tr[now][c]=++cnt;
    }
    val[now]=id;
}
void make(int x)
{
    for(int v,i=0;i<26;i++)
        if(v=tr[x][i])
        {
            if(!val[v])
                f[v]=find(x);
            else
                t[val[find(x)]].push_back(val[v]);
            make(v);
        }
}
bool cmp(const int &x,const int &y)
{
    return size[x]<size[y];
}
void makes(int x)
{
    size[x]=1;
    for(int i=0;i<t[x].size();i++)
    {
        makes(t[x][i]);
        size[x]+=size[t[x][i]];
    }
    sort(t[x].begin(),t[x].end(),cmp);
}
void dfs(int x)
{
    id[x]=tot++;
    for(int i=0;i<t[x].size();i++)
    {
        ans+=tot-id[x];
        dfs(t[x][i]);
    }
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>st[i];
        len[i]=st[i].length();
        for(int j=0;j<len[i]/2;j++)
            swap(st[i][j],st[i][len[i]-j-1]);
        insert(st[i],i);
    }
    for(int i=1;i<=cnt;i++)
        f[i]=i;
    make(0),makes(0),dfs(0);
    printf("%lld\n",ans);
    return 0;
}

 

Luogu P3294 【[SCOI2016]背单词】

原文:https://www.cnblogs.com/ivanovcraft/p/9822422.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!