自动搬运

查看原文

来自洛谷，原作者为

	Yan719 “The best people in life are free.”

搬运于2025-08-24 22:59:54，当前版本为作者最后更新于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;
}