$\texttt{A}$ 小红的字符串计数

知识点：模拟、计数

字符串长度只有 $\texttt{4}$，可以直接对每个字符统计它在串中出现了几次。由于出现 $\texttt{1}$ 次的字符本身只会被遍历到 $\texttt{1}$ 次，所以把出现次数为 $\texttt{1}$ 的位置累加即可。

时间复杂度 $\mathcal{O}(\texttt{1})$。

void solve() {
    string s;
    cin >> s;
    int ans = 0;
    for (auto c : s) ans += count(s.begin(), s.end(), c) == 1;
    cout << ans << endl;
}

$\texttt{B}$ 小红打舞萌

知识点：贪心、分类讨论

设一共可以游玩 $m=\lfloor x/\texttt{5}\rfloor$ 次。和别人一起玩每次可以多玩 $\texttt{1}$ 首歌，因此应尽量多选合作；又因为不能连续 $\texttt{2}$ 次合作，所以最多合作 $\lceil m/\texttt{2}\rceil$ 次。

因此答案为

$$\texttt{4}\left\lceil \frac{m}{\texttt{2}}\right\rceil+\texttt{3}\left\lfloor \frac{m}{\texttt{2}}\right\rfloor.$$

时间复杂度 $\mathcal{O}(\texttt{1})$。

void solve() {
    int n;
    cin >> n;
    n /= 5;
    cout << n / 2 * 7 + n % 2 * 4 << endl;
}

$\texttt{C}$ 魔物 $\texttt{76}$

知识点：差分、取模维护

维护相邻两项在模 $\texttt{5}$ 意义下的贡献，记

$$d_i=((a_{i+\texttt{1}}-a_i)\bmod \texttt{5}+\texttt{5})\bmod \texttt{5}.$$

答案就是所有 $d_i$ 的和。一次对区间 $[l,r]$ 整体加 $\texttt{1}$，区间内部相邻差值不变，只会影响两个边界：若 $l>\texttt{1}$，则 $d_{l-\texttt{1}}$ 增加 $\texttt{1}$；若 $r<n$，则 $d_r$ 减少 $\texttt{1}$，也就是模 $\texttt{5}$ 意义下加 $\texttt{4}$。所以每次询问只需要删除旧边界贡献，修改边界，再加回新边界贡献。

时间复杂度 $\mathcal{O}(n+q)$。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), d(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    auto calc = [&](int x) { return (x % 5 + 5) % 5; };

    int ans = 0;
    for (int i = 1; i < n; ++i) ans += d[i] = calc(a[i + 1] - a[i]);

    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l > 1) {
            ans -= d[l - 1];
            (d[l - 1] += 1) %= 5;
            ans += d[l - 1];
        }
        if (r < n) {
            ans -= d[r];
            (d[r] += 4) %= 5;
            ans += d[r];
        }
        cout << ans << endl;
    }
}

$\texttt{D}$ 小红的子序列

知识点：动态规划、质因数分解、路径还原

特殊地，长度为 $\texttt{1}$ 的数组一定合法，所以令 $f_i=\texttt{1}$。若当前选择 $a_i=x$，上一项必须是 $x/p$，其中 $p$ 是 $x$ 的一个质因子；反过来说，枚举 $x$ 的所有不同质因子就枚举完了所有可能前驱值。

从左到右扫描，维护 $\texttt{best}_v$ 表示已经扫过的位置中，以数值 $v$ 结尾的最长好子序列长度，$\texttt{id}_v$ 记录对应位置。处理 $x$ 时，用所有 $\texttt{best}_{x/p}+\texttt{1}$ 更新 $f_i$，同时记录前驱 $\texttt{pre}_i$。更新完再用 $f_i$ 刷新 $\texttt{best}_x$，这样自然保证子序列下标递增。最后从全局最优结尾沿 $\texttt{pre}$ 反向还原即可。

时间复杂度 $\mathcal{O}(V\log\log V+\sum_{i=\texttt{1}}^n\omega(a_i))$，其中 $V=\max a_i$，$\omega(x)$ 表示 $x$ 的不同质因子个数。

void solve() {
    int n, m = 0;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        m = max(m, a[i]);
    }

    vector<int> p(m + 1);
    for (int i = 2; i <= m; ++i) {
        if (!p[i]) {
            for (int j = i; j <= m; j += i) {
                if (!p[j]) p[j] = i;
            }
        }
    }

    vector<int> best(m + 1), id(m + 1);
    vector<int> f(n + 1, 1), pre(n + 1);
    int r = 1;

    for (int i = 1; i <= n; ++i) {
        for (int x = a[i]; x > 1;) {
            int y = p[x], v = a[i] / y;
            if (best[v] + 1 > f[i]) {
                f[i] = best[v] + 1;
                pre[i] = id[v];
            }
            while (x % y == 0) x /= y;
        }

        if (f[i] > best[a[i]]) {
            best[a[i]] = f[i];
            id[a[i]] = i;
        }
        if (f[i] > f[r]) r = i;
    }

    vector<int> ans;
    for (; r; r = pre[r]) ans.push_back(a[r]);
    reverse(ans.begin(), ans.end());

    cout << ans.size() << endl;
    for (auto x : ans) cout << x << ' ';
    cout << endl;
}

$\texttt{E}$ 小红的受欢迎子串

知识点：字符串、前后缀、自动机 $\texttt{DP}$

法 $\texttt{1}$：前后缀保留字符。

只能插入字符，不能删除或交换字符，因此若原串某个连续子串最终要被补成目标串 $p$，那么这个连续子串必须是 $p$ 的子序列。能保留的原串字符越多，需要插入的字符越少。

两个目标串 $\texttt{greet}$ 和 $\texttt{invite}$ 之间没有可用重叠，所以最终只需要考虑两种顺序：$\texttt{greet}$ 在前、$\texttt{invite}$ 在后，或者反过来。对每个目标串 $p$，预处理 $\texttt{pre}_i$ 表示前 $i$ 个字符中最多能保留多少字符补成 $p$，$\texttt{suf}_i$ 表示后缀 $[i,n]$ 中最多能保留多少字符补成 $p$。枚举分割点，最大化两段保留字符数 $mx$，答案就是

$$|\texttt{greet}|+|\texttt{invite}|-mx=\texttt{11}-mx.$$

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s;
    cin >> n >> s;

    auto calc = [&](string p) {
        int m = p.size();
        vector<int> st(n + 2), ed(n + 2), pre(n + 2), suf(n + 3);

        for (int l = 0; l < n; l++) {
            int pos = 0;
            for (int r = l; r < n && r < l + m; r++) {
                while (pos < m && p[pos] != s[r]) pos++;
                if (pos == m) break;
                pos++;
                int len = r - l + 1;
                st[l + 1] = max(st[l + 1], len);
                ed[r + 1] = max(ed[r + 1], len);
            }
        }

        for (int i = 1; i <= n; ++i) pre[i] = max(pre[i - 1], ed[i]);
        for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], st[i]);
        return make_pair(pre, suf);
    };

    string a = "greet", b = "invite";
    auto [pa, sa] = calc(a);
    auto [pb, sb] = calc(b);

    int mx = 0;
    for (int i = 0; i <= n; i++) {
        mx = max(mx, pa[i] + sb[i + 1]);
        mx = max(mx, pb[i] + sa[i + 1]);
    }

    cout << a.size() + b.size() - mx << endl;
}

法 $\texttt{2}$：顺序自动机 $\texttt{DP}$。

另一种写法是先固定两个目标串的出现顺序。令 $\texttt{out}k$ 表示已经完整处理完前 $k$ 个目标串，且当前不在某个目标串内部；令 $\texttt{in}{t,j}$ 表示正在用原串的一段连续子串补成第 $t$ 个目标串，并且已经匹配到该目标串前缀 $j$。当前字符如果能作为目标串剩余部分中的某个字符，就保留下来并跳到对应后继位置。

因为可以随时插入剩余字符来补完当前目标串，所以每处理一个原串字符前后都可以做一次“闭包”：把所有 $\texttt{in}$ 状态转为对应的 $\texttt{out}$ 状态。分别计算 $\texttt{greet}\to\texttt{invite}$ 和 $\texttt{invite}\to\texttt{greet}$ 两种顺序下最多能保留的字符数 $mx$，答案仍为 $\texttt{11}-mx$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s;
    cin >> n >> s;

    auto work = [&](string a, string b) {
        vector<string> p = {a, b};
        vector<vector<array<int, 26>>> nxt(2);

        for (int t = 0; t < 2; ++t) {
            int m = p[t].size();
            nxt[t].assign(m + 1, {});
            for (int i = 0; i <= m; ++i) {
                for (int c = 0; c < 26; ++c) {
                    nxt[t][i][c] = -1;
                    for (int j = i; j < m; ++j) {
                        if (p[t][j] == char('a' + c)) {
                            nxt[t][i][c] = j + 1;
                            break;
                        }
                    }
                }
            }
        }

        const int neg = -(1LL << 60);
        vector<int> out(3, neg);
        vector<vector<int>> in(2);
        in[0].assign(a.size() + 1, neg);
        in[1].assign(b.size() + 1, neg);
        out[0] = 0;

        auto close = [&]() {
            for (int k = 0; k < 2; ++k) {
                for (int j = 0; j < in[k].size(); ++j) {
                    out[k + 1] = max(out[k + 1], in[k][j]);
                }
            }
            out[1] = max(out[1], out[0]);
            out[2] = max(out[2], out[1]);
        };

        for (auto ch : s) {
            close();

            vector<int> nout = out;
            vector<vector<int>> nin(2);
            nin[0].assign(a.size() + 1, neg);
            nin[1].assign(b.size() + 1, neg);

            int c = ch - 'a';
            for (int k = 0; k < 2; ++k) {
                int pos = nxt[k][0][c];
                if (out[k] != neg && pos != -1) {
                    nin[k][pos] = max(nin[k][pos], out[k] + 1);
                }

                for (int j = 0; j < in[k].size(); ++j) {
                    if (in[k][j] == neg) continue;
                    int np = nxt[k][j][c];
                    if (np != -1) {
                        nin[k][np] = max(nin[k][np], in[k][j] + 1);
                    }
                }
            }

            out = nout;
            in = nin;
        }

        close();
        return out[2];
    };

    int mx = max(work("greet", "invite"), work("invite", "greet"));
    cout << 11 - mx << endl;
}

法 $\texttt{3}$：自动机 $\texttt{DP}$。

同时维护当前已经匹配到 $\texttt{greet}$ 和 $\texttt{invite}$ 的哪个前缀，以及两个模式串是否已经出现过。插入字符需要代价 $\texttt{1}$，保留原串字符代价为 $\texttt{0}$。因此在读入原串每个字符前，先用最短路求出“任意插入若干字符”后的最优状态，再转移这个原串字符；最后再做一次插入闭包即可。

插入的字符只需要考虑两个目标串中出现过的字符，因为其他字符既不会推进匹配状态，也不会让答案更优。

时间复杂度 $\mathcal{O}(nS\log S)$，其中 $S=\texttt{5}\cdot\texttt{6}\cdot\texttt{4}=\texttt{120}$。

constexpr int inf = 2e18 + 9;

struct State {
    int p, q, mask;
};

vector<int> build(const string &p) {
    int m = p.size();
    vector<int> fail(m);
    for (int i = 1; i < m; ++i) {
        int j = fail[i - 1];
        while (j > 0 && p[i] != p[j]) j = fail[j - 1];
        if (p[i] == p[j]) ++j;
        fail[i] = j;
    }
    return fail;
}

int extend(const string &pat, const vector<int> &fail, int j, char c, bool &hit) {
    int m = pat.size();
    while (j > 0 && pat[j] != c) j = fail[j - 1];
    if (pat[j] == c) ++j;
    if (j == m) {
        hit = true;
        j = fail[m - 1];
    }
    return j;
}

void solve() {
    int n;
    string s, tar1 = "greet", tar2 = "invite";
    cin >> n >> s;

    auto fail1 = build(tar1);
    auto fail2 = build(tar2);

    vector<int> alpha;
    string key = "gretinv";
    for (auto v : key) alpha.push_back(v - 'a');

    int id[5][6][4];
    vector<State> states;
    int cnt = 0;
    for (int p = 0; p < 5; ++p) {
        for (int q = 0; q < 6; ++q) {
            for (int m = 0; m < 4; ++m) {
                id[p][q][m] = cnt++;
                states.push_back({p, q, m});
            }
        }
    }

    const int S = cnt;
    array<array<int, 26>, 120> go{};
    array<array<int, 7>, 120> ins{};

    for (int idx = 0; idx < S; ++idx) {
        auto [p, q, mask] = states[idx];
        for (int c = 0; c < 26; ++c) {
            char ch = char('a' + c);
            int np = p, nq = q, nmask = mask;
            bool hit1 = false, hit2 = false;
            np = extend(tar1, fail1, np, ch, hit1);
            nq = extend(tar2, fail2, nq, ch, hit2);
            if (hit1) nmask |= 1;
            if (hit2) nmask |= 2;
            go[idx][c] = id[np][nq][nmask];
        }
        for (int k = 0; k < 7; ++k) ins[idx][k] = go[idx][alpha[k]];
    }

    auto closure = [&](const array<int, 120> &src, array<int, 120> &dist) {
        dist = src;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (int i = 0; i < S; ++i) {
            if (dist[i] < inf) pq.push({dist[i], i});
        }
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d != dist[u]) continue;
            for (int k = 0; k < 7; ++k) {
                int v = ins[u][k];
                if (dist[v] > d + 1) {
                    dist[v] = d + 1;
                    pq.push({dist[v], v});
                }
            }
        }
    };

    array<int, 120> dp, ndp, best;
    dp.fill(inf);
    dp[id[0][0][0]] = 0;

    for (char ch : s) {
        closure(dp, best);
        ndp.fill(inf);
        int c = ch - 'a';
        for (int u = 0; u < S; ++u) {
            if (best[u] >= inf) continue;
            int v = go[u][c];
            ndp[v] = min(ndp[v], best[u]);
        }
        dp = ndp;
    }

    closure(dp, best);

    int ans = inf;
    for (int i = 0; i < S; ++i) {
        if (states[i].mask == 3) ans = min(ans, best[i]);
    }
    cout << ans << endl;
}

$\texttt{F}$ 小红的数组构造

知识点：数学构造、完全背包、商集合、$\texttt{DFS}$ 回溯

法 $\texttt{1}$：商集合完全背包。

先看必要条件。因为 $\texttt{1}\le a_i\le x$，所以每项贡献满足

$$\texttt{1}\le \left\lfloor \frac{x}{a_i}\right\rfloor\le x.$$

因此若 $knx$，一定无解。接着把每一项的基础贡献 $\texttt{1}$ 扣掉，令 $d=k-n$。对于一个数 $a_i$，合法额外贡献为

$$\left\lfloor\frac{x}{a_i}\right\rfloor-\texttt{1}.$$

不同的 $\left\lfloor\frac{x}{a_i}\right\rfloor$ 可以用整除分块枚举出来，于是所有正的合法额外贡献就是一组硬币。因为每种贡献可以使用任意次，所以对 $d$ 做完全背包，令 $\texttt{dp}_j$ 表示凑出 $j$ 至少需要多少项，并用 $\texttt{pre}_j$ 记录最后一次选择的贡献。

若 $\texttt{dp}_d>n$，说明无法在 $n$ 项内凑出 $d$；否则沿 $\texttt{pre}$ 还原这些正贡献，不足 $n$ 项的位置补 $\texttt{0}$。额外贡献为 $c$ 时输出 $\left\lfloor x/(c+\texttt{1})\right\rfloor$，即可保证这一项的实际贡献为 $c+\texttt{1}$。

时间复杂度 $\mathcal{O}(Qd)$，其中 $Q$ 为不同合法商的个数，且 $Q=\mathcal{O}(\sqrt{x})$。

void solve() {
    int n, x, k;
    cin >> n >> x >> k;

    if (k < n || k > n * x) return cout << "NO" << endl, void();

    int d = k - n;
    if (d == 0) {
        cout << "YES" << endl;
        for (int i = 1; i <= n; ++i) cout << x << " \n"[i == n];
        return;
    }

    vector<int> coin;
    for (int l = 1; l <= x;) {
        int q = x / l, r = x / q, c = q - 1;
        if (c > 0 && c <= d) coin.push_back(c);
        l = r + 1;
    }

    const int inf = 1LL << 60;
    vector<int> dp(d + 1, inf), pre(d + 1, -1);
    dp[0] = 0;

    for (auto c : coin) {
        for (int j = c; j <= d; ++j) {
            if (dp[j - c] + 1 < dp[j]) {
                dp[j] = dp[j - c] + 1;
                pre[j] = c;
            }
        }
    }

    if (dp[d] > n) return cout << "NO" << endl, void();

    vector<int> ans;
    for (int rem = d; rem > 0;) {
        int c = pre[rem];
        ans.push_back(c);
        rem -= c;
    }

    while (ans.size() < n) ans.push_back(0);

    cout << "YES" << endl;
    for (int i = 0; i < n; ++i) {
        cout << x / (ans[i] + 1) << " \n"[i == n - 1];
    }
}

法 $\texttt{2}$：大小贡献划分并 $\texttt{DFS}$。

先看必要条件。因为 $\texttt{1}\le a_i\le x$，所以每项贡献满足

$$\texttt{1}\le \left\lfloor \frac{x}{a_i}\right\rfloor\le x.$$

因此若 $knx$，一定无解。

令每一项先贡献 $\texttt{1}$，还需要额外凑出

$$d=k-n.$$

若某一项的实际贡献为 $q$，则它的额外贡献为 $q-\texttt{1}$。问题转化成：能否用 $n$ 个合法额外贡献凑出 $d$。

设 $s=\lfloor\sqrt{x}\rfloor$，$B=s-\texttt{1}$。对于任意 $\texttt{0}\le c\le B$，令 $q=c+\texttt{1}$，有 $q\le s$，可以取 $a=\lfloor x/q\rfloor$，此时 $\lfloor x/a\rfloor=q$，所以所有小贡献 $\texttt{0},\texttt{1},\dots,B$ 都合法。于是当 $d\le nB$ 时，直接把 $d$ 分摊到 $n$ 个位置，每个位置不超过 $B$ 即可。

否则必须使用大贡献。所有大于 $B$ 的合法额外贡献都形如

$$\left\lfloor\frac{x}{a}\right\rfloor-\texttt{1},$$

可以通过整除分块在 $\mathcal{O}(\sqrt{x})$ 个不同商中全部枚举出来。将这些大贡献从大到小排列后 $\texttt{DFS}$，枚举每种贡献使用多少次。若当前剩余和 $\texttt{rem}$ 已经满足 $\texttt{rem}\le \texttt{cnt}\cdot B$，剩余 $\texttt{cnt}$ 个位置就一定能用连续的小贡献 $[\texttt{0},B]$ 填完。

$\texttt{DFS}$ 的完备性来自这个划分：所有合法贡献被完整分为连续小贡献 $[\texttt{0},B]$ 和枚举出来的大贡献集合。搜索到某个大贡献 $c$ 时，之后所有未决大贡献和小贡献都不超过下一个上界 $\texttt{nxt}$，所以代码中用 $\texttt{lo},\texttt{hi}$ 只剪掉“不可能凑够”或“已经超出”的使用次数；任何真实可行解在当前贡献 $c$ 的使用次数一定落在这个区间内。因此 $\texttt{DFS}$ 枚举了所有大贡献的多重集合，剩余部分再由连续小贡献填补，若搜索失败则不存在合法构造。

最后若某个位置的额外贡献为 $c$，目标贡献就是 $q=c+\texttt{1}$，输出 $a=\lfloor x/q\rfloor$ 即可保证该项贡献为 $q$。

时间复杂度 $\mathcal{O}(\sqrt{x}+S)$，其中 $S$ 为 $\texttt{DFS}$ 实际访问状态数。

void solve() {
    int n, x, k;
    cin >> n >> x >> k;

    if (k < n || k > n * x) return cout << "NO" << endl, void();

    int d = k - n, s = sqrtl(x);
    {
        while ((s + 1) * (s + 1) <= x) s++;
        while (s * s > x) s--;
    }

    int B = s - 1;
    vector<int> ans;

    auto add = [&](int cnt, int rem) {
        while (cnt--) {
            int c = min(B, rem);
            ans.push_back(c);
            rem -= c;
        }
    };

    if (d <= n * B) {
        add(n, d);
    } else {
        vector<int> h;
        for (int l = 1; l <= x;) {
            int v = x / l, r = x / v, c = v - 1;
            if (c > B && c <= d) h.push_back(c);
            l = r + 1;
        }

        using ull = unsigned long long;
        unordered_set<ull> vis;

        auto ceil = [&](int a, int b) {
            if (a <= 0) return 0LL;
            return (a + b - 1) / b;
        };

        auto dfs = [&](auto &&self, int i, int cnt, int rem) -> bool {
            if (rem == 0) {
                while (cnt--) ans.push_back(0);
                return true;
            }
            if (cnt == 0) return false;
            if (rem <= cnt * B) return add(cnt, rem), true;
            if (i == h.size()) return false;

            int c = h[i];
            if (rem > cnt * c) return false;

            int nxt = (i + 1 < h.size() ? h[i + 1] : B);
            int lo = ceil(rem - cnt * nxt, c - nxt);
            int hi = min(cnt, rem / c);
            if (lo > hi) return false;

            ull key = ((ull)i << 40) | ((ull)cnt << 20) | rem;
            if (vis.count(key)) return false;

            for (int t = hi; t >= lo; t--) {
                if (self(self, i + 1, cnt - t, rem - t * c)) {
                    while (t--) ans.push_back(c);
                    return true;
                }
            }

            vis.insert(key);
            return false;
        };

        if (!dfs(dfs, 0, n, d)) return cout << "NO" << endl, void();
    }

    cout << "YES" << endl;
    for (int i = 0; i < n; i++) {
        int v = ans[i] + 1;
        cout << x / v << " \n"[i == n - 1];
    }
}

约定

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii array<int, 2>
#define endl "\n"

void solve() {}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}