题解：P10646 [NordicOI 2023] ChatNOI

Yan719 · 2024-10-22 10:34:49 · 题解

洛谷 P10646

题意

给定 n 个单词组成的文本和一个参数 k。

对于一个句子 s，我们称它的质量为每连续 k + 1 个单词在原文本中出现次数的最小值。

举个例子：

当这个文本的参数为 k = 2 时：

row row to the fishing rocks
out in the ocean they go
a cow is sitting and rowing
and the sun rises
and the sun sets
but the cow and the boat are still there

那么，句子 cow and the sun rises 的质量就是 1。

其中，cow and the 出现了 1 次，and the sun 出现了 2 次，the sun rises 出现了 1 次。

所以质量为 1。

给定 q 组询问，每次给出 k 个单词和一个 m，你需要在这 k 个单词后添加 m 个单词，并使得句子的质量最大化。

请你给出方案。

思路

我们考虑构造答案的过程，对于每一个我们要填入的单词，实际上我们是只关心当前句子中最后的 k 个单词的，在我们填上当前这个单词后，我们的句子中的最后 k 个单词也发生了变化，我们可以将其看作一种转移。

譬如说当前的 k = 3，句子末尾为 a b c，那么当我们选择了单词 d 后，句子最末尾的 k 个单词就会变成 b c d。

我们可以将其视为 a b c 到 b c d 的一种转移。

像这样，我们可以将原文本中的每连续 k 个单词抽象为一个点，并根据原文本建边。

我们用题面中给的文本举例：

row row to the fishing rocks
out in the ocean they go
a cow is sitting and rowing
and the sun rises
and the sun sets
but the cow and the boat are still there

那么，对于 and the 到 the sun 这样一条边，它的边权就是 2，因为 and the sun 的出现次数为 2 次。

像这样建完边以后，每个句子所对应的质量就是在这些有向边上移动时，所经过的边的边权的最小值。

然后我们就可以按照边权从大到小枚举，假设当前枚举的边权为 x，那么我们就只连边权大于等于 x 的边，拓扑排序求出最长路。

对于每一个未被解决的询问判断初始状态是否可以往外走 m 步。

注意：当某一个询问的初始状态在一个环上，那么必定是可以无限走的，判断一下是否在拓扑排序时被遍历到即可。

这样的时间复杂度就是 O(nq)。

然后我们会发现，这个边权是十分奇妙的，它所对应的是某个单词在某段连续 k 个单词后的出现次数。

所以边权总和就是大约 n 的级别的。

因此，不同的边权的数量实际上就是大约 \sqrt{n} 种，我们只需要枚举这 \sqrt{n} 种，然后建边并拓扑排序即可。

时间复杂度为 O(\sqrt{n} \cdot (n + q))，忽略离散化用的 map 的复杂度。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 5e5 + 10, INF = 1e9;

struct Edge {
    int u, v, w, type;
    bool operator < (const Edge &i) const {
        return w > i.w;
    }
};

int n, k, q, cnt, a[N], c, b[N], m[N], deg[N], query[N], dp[N];
pii trans[N];
map<string, int> mp;
map<vector<int>, int> tw;
vector<int> W, ans[N];
vector<pii> p[N], g[N], e[N];
vector<Edge> edge;
queue<int> que;
string to[N];

void topo_sort() {
    fill(dp + 1, dp + c + 1, -INF);
    for (int i = 1; i <= c; i++) if (!deg[i]) que.push(i), dp[i] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (auto [v, w] : g[u]) {
            deg[v]--;
            if (dp[u] + 1 > dp[v]) {
                dp[v] = dp[u] + 1, trans[v] = {u, w};
            }
            if (!deg[v]) que.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        if (!mp.count(s)) mp[s] = ++cnt, to[cnt] = s;
        a[i] = mp[s];
    }
    for (int i = 1; i + k - 1 <= n; i++) {
        vector<int> ts;
        for (int j = i; j <= i + k - 1; j++) {
            ts.push_back(a[j]);
        }
        if (!tw.count(ts)) tw[ts] = ++c;
        b[i] = tw[ts];
        if (i) p[b[i - 1]].push_back({b[i], a[i + k - 1]});
    }
    for (int i = 1; i <= c; i++) {
        sort(p[i].begin(), p[i].end());
        for (int j = 0; j < p[i].size(); ) {
            pii t = p[i][j];
            int ct = 0;
            for (; j < p[i].size() && p[i][j] == t; j++) ct++;
            edge.push_back({t.first, i, ct, t.second});
        }
    }
    sort(edge.begin(), edge.end());
    for (auto [u, v, w, tp] : edge) W.push_back(w);
    sort(W.begin(), W.end());
    W.erase(unique(W.begin(), W.end()), W.end());
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> m[i];
        vector<int> ts;
        for (int j = 1; j <= k; j++) {
            string s; cin >> s;
            ts.push_back(mp[s]);
        }
        query[i] = (tw.count(ts) ? tw[ts] : -1);
    }
    reverse(W.begin(), W.end());
    for (int ew : W) {
        for (auto [u, v, w, tp] : edge) {
            if (w < ew) break;
            deg[v]++, g[u].push_back({v, tp});
            e[v].push_back({u, tp});
        }
        topo_sort();
        for (int i = 1; i <= q; i++) {
            if (query[i] != -1 && deg[query[i]] && ans[i].empty()) {
                int k = query[i];
                while (ans[i].size() < m[i]) {
                    for (auto [t, d] : e[k]) {
                        if (deg[t]) {
                            k = t, ans[i].push_back(d);
                            break;
                        }
                    }
                }
            } else if (query[i] != -1 && dp[query[i]] >= m[i] && ans[i].empty()) {
                int k = query[i];
                while (ans[i].size() < m[i]) {
                    ans[i].push_back(trans[k].second);
                    k = trans[k].first;
                }
            }
        }
        for (int i = 1; i <= c; i++) deg[i] = 0, g[i].clear(), e[i].clear(), trans[i] = {0, 0};
    }
    for (int i = 1; i <= q; i++) {
        if (query[i] == -1 || ans[i].empty()) {
            while (m[i]--) cout << to[1] << ' ';
            cout << '\n';
        } else {
            for (int x : ans[i]) cout << to[x] << ' ';
            cout << '\n';
        }
    }
    return 0;
}