题解：P10646 [NordicOI 2023] ChatNOI

· · 题解

思路

何意味？

发现字符串没有任何用，可以将每个字符串映射到整数上。

考虑图论建模，将每个长度为 k 的连续段看做一个点。在这个连续段后加入一个数字看做一条边，边权为加入这个数字后形成长度为 k+1 的连续段在 w 中出现的次数，终点为后 k 个数字形成的连续段。

那么在一个长度为 k 的前缀后增加 m_i 个数，这个长度为 k 的前缀刚好就是一个点。质量就可以表示为从这个点出发走 m_i 步，路径上边权最小值。

先考虑考虑如何判断答案是否大于等于 x。问题转化为从一个点出发，只经过边权大于等于 x 的边是否能走 m 步。

这个就十分经典了，考虑倒着建图，然后跑拓扑排序即可。若跑完后一个点的度数不是 0，说明这个点可以跑到一个环上，最长路为 \infin。

若从大到小枚举 x，对于每个点，因为从这个点出发的最长路是单调不降的，所以维护一个指针，按 m 从小到大的顺序扫每个点上的询问，若合法就构造方案并将指针向后移动，不合法就退出。

为了构造方案，我们还需要为每个点找到最长路上的后继。对于可以到环的点，至少有一条满足终点仍可以到环的出边，后继为这条出边的终点。对于其他点，后继就是图上最长路的后继。

发现边权之和是 O(n) 量级的，此时就有一个经典结论即为不同边权的数量为 O(\sqrt n) 量级的，暴力枚举答案即可做到 O(n\sqrt n)。实现的好可以通过。

其实还可以做到更优。

进一步挖掘性质，若 val_i 为第 i 条边的边权，发现我们需要扫的边数的总和为 \sum\limits_{x=1}^{n}\sum[val_i\ge x]=\sum val_i，也就是说，扫的边数的总和为 O(n)。对应的，每次没有连边的点最长路肯定为 0，是没用的。扫的点数总和就也是 O(n) 的。所以我们只需要每次把有用的点拿出来做缩点即可。

使用哈希表将每个字符串映射为一个数以及将一个连续段映射到一个点可以做到时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int N = 5e5+5,base1 = 23333,mod1 = 1e9+9,base2 = 20101013,mod2 = 147744151,base = 1e9,inf = 2e9;
int n,k,q,tot,cnt,a[N],en[N],lim[N];
string t[N],s;
gp_hash_table<int,int> mp,mp1,mp2;
vector<pair<int,int>> vec[N],vec2[N];
int now[N];
int head[N],to[N],nxt[N],top;
inline void add(int u,int v)
{
    nxt[++top] = head[u];
    head[u] = top;
    to[top] = v;
}
int p[N],ttt;
bool vis[N];
int rt[N],dis[N],du[N];
vector<string> ans[N];
bool ok[N];
inline void work(int x)
{
    while(now[x]<vec2[x].size()&&vec2[x][now[x]].first<=dis[x])
    {
        auto _ = vec2[x][now[x]++];
        int lim = _.first,id = _.second,p = x;
        while(lim--)
        {
            p = rt[p];
            ans[id].push_back(t[en[p]]);
        }
    }
}
inline int get(string &s)
{
    int res = 0;
    for(auto i:s) res = res*27+i-'a'+1;
    return res;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i = 1;i<=n;i++)
    {
        cin>>s;
        int x = get(s);
        if(!mp[x]) mp[x] = ++tot,t[tot] = s;
        a[i] = mp[x];
    }
    int las = 0;
    for(int i = 1;i<=n-k+1;i++)
    {
        int h1 = 0,h2 = 0;
        for(int j = i;j<i+k;j++)
            h1 = (h1*base1+a[j])%mod1,h2 = (h2*base2+a[j])%mod2;
        int h = h2*mod1+h1;
        if(!mp1[h])
        {
            mp1[h] = ++cnt;
            en[cnt] = a[i+k-1];
        }
        int now = mp1[h];
        if(las) mp2[las*base+now]++;
        las = now;
    }
    for(auto _:mp2)
        vec[_.second].push_back({_.first/base,_.first%base});
    cin>>q;
    for(int i = 1,x;i<=q;i++)
    {
        cin>>x;
        int h1 = 0,h2 = 0;
        for(int j = 1;j<=k;j++)
        {
            cin>>s;
            int now = mp[get(s)];
            h1 = (h1*base1+now)%mod1,h2 = (h2*base2+now)%mod2;
        }
        int p = mp1[h2*mod1+h1];
        vec2[p].push_back({x,i}),lim[i] = x;
    }
    for(int i = 1;i<=cnt;i++) sort(vec2[i].begin(),vec2[i].end());
    dis[0] = -1;
    for(int i = n;i;i--)
    {
        if(!vec[i].size()) continue;
        for(auto _:vec[i])
        {
            if(!vis[_.second]) p[++ttt] = _.second,vis[_.second] = 1;
            if(!vis[_.first]) p[++ttt] = _.first,vis[_.first] = 1;
            add(_.second,_.first);
        }
        for(int i = 1;i<=ttt;i++) du[p[i]] = 0;
        for(int i = 1;i<=ttt;i++)
        {
            int x = p[i];
            dis[x] = 0;
            for(int i = head[x];i;i = nxt[i])
            {
                int y = to[i];
                du[y]++;
            }
        }
        queue<int> q;
        for(int i = 1;i<=ttt;i++)
            if(!du[p[i]]) q.push(p[i]);
        while(!q.empty())
        {
            int u = q.front();q.pop();
            for(int i = head[u];i;i = nxt[i])
            {
                int v = to[i];
                if(dis[u]+1>dis[v]) dis[v] = dis[u]+1,rt[v] = u;
                du[v]--;
                if(!du[v]) q.push(v);
            }
        }
        for(int i = 1;i<=ttt;i++)
        {
            int x = p[i];
            if(du[x])
            {
                dis[x] = 2e9;
                for(int i = head[x];i;i = nxt[i])
                {
                    int y = to[i];
                    rt[y] = x;
                }
            }
        }
        for(int i = 1;i<=ttt;i++)
            work(p[i]);
    }
    for(int i = 1;i<=q;i++)
    {
        if(!ans[i].size()) while(lim[i]--) cout<<t[1]<<' ';
        else for(auto _:ans[i]) cout<<_<<' ';
        cout<<'\n';
    }
    return 0;
}