• 欢迎光临~

题解 [SCOI2016] 背单词

开发技术 开发技术 2021-08-17 127次浏览
  • 题意

    题目链接: 传送门

    题目大意是给一些互不相同的字符串,对其进行排序。对于第$ i $个字符串 $ a_i $ ,它对答案的贡献是:

    1. 若存在一个字符串$ a_j $,满足 $ a_j $ 是 (a_i) 的后缀且 $ j>i $,则贡献为 $ n^2 $
    2. (a_i)的所有后缀均不出现在字符串序列中,则贡献为 $ i $
    3. (a_i)的所有后缀均不出现在$ a_i$后,记距离 (a_i)最近的后缀为 (a_j),则贡献为 (i-j)
  • Solution

    做法:贪心+Trie

    不难发现题目中给出的前两条规则并没有意义,对于规则1,可以把(a_i)的后缀放到(a_i)前,显然这是可以做到的。对于规则2,可以等效为规则3中 (j=0)的情况,所以实际上我们希望一个字符串离它的后缀尽可能的近。
    对于一个字符串 $ ai$ 它的后缀应当恰好顺次排列在它的前面,若这样的字符串组的大小为$ Size $,显然 $ Size $越小的应当被放到前面,我们假设这组字符串的中第一个字符串位于 (i) ,则这一组所产生的贡献应是 (i+Size-1),那么总的贡献显然只与 (i)的位置有关,根据贪心的思想排序即可。

    接下来考虑如何处理后缀(听说这题可以后缀数组?),发现并不是很好做,于是想到将字符串翻转,变为前缀处理。

    注意到字符串总长 $ len<=510000$,可以用考虑建立字典树。

    上述的排序方式体现到trie上,即使按每棵子树的大小排序,因为对于一个确定前缀 $ pre$ ,它所对应的字符串组中 (Size) 小的应该被放在前面。(即被优先遍历)

    我们只关心各个字符串之间的关系(已经通过trie建立),并不关心字符串具体的内容,从而发现我们可以删去不作为任何字符串结尾的节点,考虑重新建树,仅加入字符串的结尾节点。

    然后就可以统计答案了。

    先dfs求一下每棵子树的 $Size $ ,对于每个节点,按(Size)从小到大排列它的子树,然后再求每个节点的dfs序,依据规则3统计答案即可,注意开ll

    #include<bits/stdc++.h>
    #define rep(a,b,c) for (int a=b;a<=c;a++)
    #define per(a,b,c) for (int a=b;a>=c;a--)
    using namespace std;
    typedef long long ll;
    template <typename T> inline void read(T &x){
        ll f = 1;x = 0;char ch = getchar();
        while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}
        while (isdigit(ch)){x = (x << 1)+(x << 3)+(ch ^ 48);ch = getchar();}
        x *= f;
    }
    const int MAXN=550000;
    
    int n;
    ll SIZE[MAXN];
    inline bool cmp(int x,int y)
    {
        return SIZE[x]<SIZE[y];
    }
    
    struct node{
      ll ans=0;
      int tmp[MAXN][26],dfn[MAXN],tot,cnt;
      bool end[MAXN];
      vector<int> Son[MAXN];
       
      inline void insert(char *st)
      {
      	int Len=strlen(st),pos=0;
      	per(i,Len-1,0)
      	{
      		int ch=st[i]-'a';
      		if(!tmp[pos][ch])tmp[pos][ch]=++tot;
      		pos=tmp[pos][ch];
      	}
      	end[pos]=1;
      }
      
      inline void rebuild(int pos,int fa) 
      {
      	if(end[pos])
      		Son[fa].push_back(pos),fa=pos;		
      	rep(i,0,25) 
      		if(tmp[pos][i])rebuild(tmp[pos][i],fa);
      
      }
      inline void Sum(int pos)
      {
      	SIZE[pos]=1;
      	int L=Son[pos].size();
      	rep(i,0,L-1)
      	{	
      		Sum(Son[pos][i]);
      		SIZE[pos]+=SIZE[Son[pos][i]];
      	}
      	sort(Son[pos].begin(),Son[pos].end(),cmp);
      }
      inline void dfs(int pos)
      {
      	dfn[pos]=cnt++;
      	int L=Son[pos].size();
      	rep(i,0,L-1)
      	{
      		ans+=cnt-dfn[pos];
      		dfs(Son[pos][i]);
      	}
      }
    };
    node Trie;
    int main()
    {
      read(n);
      rep(i,1,n)
      {
      	char st[MAXN];
      	scanf("%s",st);
      	Trie.insert(st);
      }
      
      Trie.rebuild(0,0);
      Trie.Sum(0);
      Trie.dfs(0);
      printf("%lldn",Trie.ans);
      
      return 0;
    

}

程序员灯塔
转载请注明原文链接:题解 [SCOI2016] 背单词
喜欢 (0)