[SCOI2016]背单词

怼烎@ 2021-09-29 17:10 313阅读 0赞

![1365648-20180415105248735-2141819007.png][]

emm。。。可以允许我吐槽一下出题人的语文吗。。。这个题题面杀？！

emm。。。毕竟是。。。细川银？！

这个题运用（百度）一些操作。。。我终于看懂了题面。。。QVQ

题目大意：

给你n个字符串，不同的排列有不同的代价，代价按照如下方式计算（字符串s的位置为x）：

1.排在s后面的字符串有s的后缀，则代价为n^2；

2.排在s前面的字符串有s的后缀，且没有排在s后面的s的后缀

则代价为x-y（y为最后一个与s不相等的后缀的位置，注意：是位置）；

3.s没有后缀，则代价为x。

求最小代价和。

这样的话大佬们是不是就一眼秒了。。。

这样我们实行一个贪心策略貌似就可以了。。。

当然我们可以发现，如果你用到了第一个条件，那么肯定不是最优的。。。

由于我们是找后缀，所以呢，我们把正着给我们的字符串反过来

建立一棵 trie

这样就变成了一颗树，问题转化为给树上每个点标号，每个点的标号大于其父亲的编号，

每个点代价为他的标号减去其父亲标号，最小化代价

证明？

emm。。。博主窝是手玩dfs序玩出来了。。。

但是事实上严格证明貌似比较难搞啊。。。这里顺带把几个主要步骤也说了。。。

1.由trie树的性质我们可以知道，它会很机智的合并字符串重复的部分。。。

2.那么当我们对于每一段进行dfs，这个地方很清楚，如果你要取一个单词，

那么这个单词的后缀肯定需要先取到，所以优先级就很明白了。。。

这时我们在dfs中记录下来这条路径中包含的单词从短到长存入，第1梯队第2梯队。。。以此类推

3.对于已经得到的这些梯队我们还要通过一遍dfs，求得排序的优先级。。。

只需要求一段树上前缀和就可以了。。。

4.到了最关键的统计答案的地方，我们通过比较可以发现，对已知的有先后顺序的梯队，

对于每个梯队来讲，我们假设只有两个梯队 x1 x2 在第一梯队里，而 size\[x1\] > size\[x2\]，

如果把影响多的放在前面,因为以 x1 为后缀的单词比 x2 多

那么这样造成的差值肯定比 x2 放在前面大，意会一下。。。

写完dfs1，dfs2然后自己出数据手玩一下就好了。。。

统计答案只需要重新定义它现在的位置，和dfs到了第几个，然后计算就好了

emm。。。本蒟蒻的呆码会被最水的 n=2 的数据卡掉。。。QVQ。。。惨啊~~~

但是没人会出这种送分数据吧。。。→\_→

呆码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    int n,rt=1,t[510010][27];
    int cnt=1,num=1,sum;
    long long ans;
    int top[510010],siz[510010];
    char ch[510010];
    bool mark[510010];
    
    vector <int> v[100010];
    
    inline void insert(char *ch)
    {
        int l=strlen(ch+1); int now=rt,u;
        for(int i=l;i;i--){
            u=ch[i]-'a';
            if(!t[now][u])t[now][u]=++cnt;
            now=t[now][u];
        }
        mark[now]=1;
    }
    
    inline void dfs1(int x)
    {
        if(mark[x]) { v[top[x]].push_back(++num); top[x]=num; }
        for(int i=0;i<=25;i++)
            if(t[x][i])
            {
                top[t[x][i]]=top[x];
                dfs1(t[x][i]);
            }
    }
    
    inline void dfs2(int x)
    {
        siz[x]=1; int u;
        for(int i=0;i<v[x].size();i++)
        {
            u=v[x][i];
            dfs2(u);
            siz[x]+=siz[u];
        }
    }
    
    inline bool cmp(int x,int y) { return siz[x]<siz[y]; }
    
    inline void dfs3(int x)
    {
        top[x]=++sum;
        sort(v[x].begin(),v[x].end(),cmp);
        for(int i=0;i<v[x].size();i++)
        {
            ans+=sum+1-top[x];
            dfs3(v[x][i]);
        }
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ch+1);
            insert(ch);
        }
    
        top[rt]=1;
        dfs1(rt);
        dfs2(1);
        dfs3(1);
        printf("%lld\n",ans);
        return 0;
    }

过不了样例的AC程序

转载于:https://www.cnblogs.com/zzzyc/p/8846657.html

[1365648-20180415105248735-2141819007.png]: /images/20210725/b3e217f6ae1d4a07a0f480d3b0f3510c.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/b0e068cecf174dfa9fba51599ba17e15.png