出题人题解 | #μ‘s挑选比赛歌曲#

原题解链接：https://ac.nowcoder.com/discuss/150263

后级数组:

时间复杂度$O(SUM(M)\ast log(SUM(M))+SUM(M)+N)O(SUM(M)*log(SUM(M))+\; SUM(M)+N)$

我们把歌曲当成字符串。

我们将所有的字符串，加上分割字符之后，跑后缀数组,然后$forfor$一遍$sasa$数组,通过$heightheight$数组，来维护一个$distdist$数组，用来代表当前后缀所在的字符串和所有其他字符串的“满足$SASA$小于当前SA的最近一个后缀"的$LCPLCP$,在过程中任意两串之间的关系取最大即可处理出所有不能同时选择的字符串。

然后二进制枚举选择的结果，判断里面是否存在矛盾关系。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+50;
int s[maxn];
int rk[maxn],sa[maxn],ht[maxn],n=0,N,K;
int st[maxn],a[maxn],fir[maxn],sec[maxn],tmp[maxn],buc[maxn];
int mp[maxn],len[22];
void suffixArray()
{
    memset(buc,0,sizeof(buc));
    copy(s,s+n,st);
    sort(st,st+n);
    int *ed = unique(st,st+n);
    for(int i=0;i<n;i++) a[i+1] = (lower_bound(st,ed,s[i])-st)+1;
    for(int i=0;i<n;i++) buc[a[i+1]] ++;
    for(int i=1;i<=n;i++) buc[i] += buc[i-1];
    for(int i=1;i<=n;i++) rk[i] = buc[a[i]-1] + 1;

    for(int t=1;t<=n;t*=2)
    {
        for(int i=1;i<=n;i++) fir[i] = rk[i];
        for(int i=1;i<=n;i++) sec[i] = i+t > n ? 0 : rk[i+t];

        memset(buc,0,sizeof(buc));
        for(int i=1;i<=n;i++) buc[sec[i]]++;
        for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
        for(int i=1;i<=n;i++) tmp[n-(--buc[sec[i]])] = i;

        memset(buc,0,sizeof(buc));
        for(int i=1;i<=n;i++) buc[fir[i]]++;
        for(int i=1;i<=n;i++) buc[i] += buc[i-1];
        for(int i=1;i<=n;i++) sa[buc[fir[tmp[i]]]--] = tmp[i];

        bool uniques = true;
        for(int j=1,i,last = 0;j<=n;j++)
        {
            i = sa[j];
            if(!last) rk[i] = 1;
            else if(fir[i]==fir[last]&&sec[i]==sec[last]) rk[i] = rk[last],uniques = false;
            else rk[i] = rk[last]+1;
            last = i;
        }
        if(uniques) break;
    }
    for(int i=1,k=0;i<=n;i++)
    {
        if(rk[i] == 1) k = 0;
        else
        {
            if(k > 0) k--;
            int j = sa[rk[i]-1];
            while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) k++;
        }
        ht[rk[i]] = k;
    }
}

int fight[22];
int main()
{
    scanf("%d%d",&N,&K);
    int cnt = 0;
    for(int i=0;i<N;i++)
    {
        scanf("%d",&len[i]);
        for(int j=n;j<n+len[i];j++)
        {
            scanf("%d",&s[j]);
            mp[j+1] = i;
        }
        if(len[i] < K)
        {
            for(int j=0;j<N;j++)
            {
                fight[j] |= (1 << i);
                fight[i] |= (1 << j);
            }
            continue;
        }
        s[n+len[i]] = 89+cnt++;
        n += len[i]+1;
    }
    suffixArray();
    int tmp = 0;
    for(int i=1;i<n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            int aa=mp[sa[i]],bb=mp[sa[j+1]];
            if(ht[j+1] < K || aa == bb)
                break;
            if(aa != bb)
            {
                fight[aa] |= 1 << bb;
                fight[bb] |= 1 << aa;
            }
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<N);i++)
    {
        bool flag = true;
        for(int j=0;j<N;j++)
        {
            if((i&(1 << j)) && (fight[j]&i))
            {
                flag = false;
                break;
            }
        }
        if(flag)
            ans = max(ans,__builtin_popcount(i));
    }
    printf("%d\n",ans);
}