A 小红买橘子

知识点：数学

每花 $x$ 元可以买 $y$ 个橘子，因此只需要计算至少买到 $z$ 个橘子需要买多少组。组数为：

$$\left\lceil \frac z y \right\rceil=\frac{z+y-1}{y}$$

所以答案为：

$$\frac{z+y-1}{y}\times x$$

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

void solve() {
    int x, y, z;
    cin >> x >> y >> z;
    cout << (z + y - 1) / y * x << endl;
}

B 小红的传送阵

知识点：枚举、最短距离

不使用传送阵时，答案为 $|k|$。

若使用第 $i$ 个传送阵，则先从 $0$ 走到 $x_i$，传送到 $y_i$，再从 $y_i$ 走到 $k$，花费为：

$$|x_i|+|k-y_i|$$

枚举所有传送阵取最小值即可。

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

void solve() {
    int n, k;
    cin >> n >> k;
    int ans = abs(k);
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        ans = min(ans, abs(x) + abs(k - y));
    }
    cout << ans << endl;
}

C 小红的好三角形

知识点：计数、哈希表、等腰三角形

若底边平行于坐标轴，则底边的两个点要么横坐标相同，要么纵坐标相同。

以竖直底边为例，设底边两点为 $(x,y_1),(x,y_2)$。第三个点必须位于这条底边的垂直平分线上，即纵坐标为：

$$m=\frac{y_1+y_2}{2}$$

因此只要统计纵坐标为 $m$ 的点数即可。若点 $(x,m)$ 存在，需要减去它，因为三点共线，不能构成非退化三角形。

横向底边同理处理。用哈希表记录每个横坐标上的点、每个纵坐标上的点，以及点是否存在即可。

时间复杂度 $\mathcal{O}\left(\sum cnt_x^2+\sum cnt_y^2\right)$。

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

    unordered_map<int, vector<int>> X, Y;
    unordered_map<int, unordered_map<int, int>> mp;

    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        X[x].push_back(y);
        Y[y].push_back(x);
        mp[x][y] = 1;
    }

    int ans = 0;
    for (auto &[x, v] : X) {
        for (int i = 0; i < v.size(); ++i) {
            for (int j = i + 1; j < v.size(); ++j) {
                int m = v[i] + v[j];
                if (m & 1) continue;
                m /= 2;
                ans += Y[m].size() - mp[x][m];
            }
        }
    }

    for (auto &[y, v] : Y) {
        for (int i = 0; i < v.size(); ++i) {
            for (int j = i + 1; j < v.size(); ++j) {
                int m = v[i] + v[j];
                if (m & 1) continue;
                m /= 2;
                ans += X[m].size() - mp[m][y];
            }
        }
    }

    cout << ans << endl;
}

D 小红的好字符串

知识点：子序列 DP、取模

前导零不会影响十进制数的值，因此只需要维护子序列对应数字模 $6$ 的余数。

设 $dp_r$ 表示当前已经选出的子序列中，数值模 $6$ 等于 $r$ 的方案数。初始空子序列满足 $dp_0=1$。

枚举每个数字 $d$，对于每个旧余数 $r$，若选择当前数字接到子序列末尾，新余数为：

$$(r\times 10+d)\bmod 6$$

同时也可以不选当前数字。最后 $dp_0$ 中包含空子序列，需要减去 $1$。

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

const int MOD = 998244353;

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

    array<int, 6> dp{};
    dp[0] = 1;

    for (auto ch : s) {
        int d = ch - '0';
        auto ndp = dp;
        for (int r = 0; r < 6; ++r) {
            int nr = (r * 10 + d) % 6;
            ndp[nr] = (ndp[nr] + dp[r]) % MOD;
        }
        dp = ndp;
    }

    cout << (dp[0] - 1 + MOD) % MOD << endl;
}

E 小红的博弈

知识点：博弈

关键结论：若所有石子堆大小的出现次数都是偶数，则后手必胜；否则先手必胜。

如果所有堆都能按大小两两配对，后手可以始终模仿先手：先手从某个大小为 $s$ 的堆中拿走 $x$ 个，后手就在它的配对堆中也拿走 $x$ 个。由于两堆原本大小相同，后手一定可以操作，并且局面重新变成两两配对。

如果存在某个大小出现奇数次，令 $s$ 为最大的出现奇数次的堆大小。先手从一堆大小为 $s$ 的堆中拿走 $s$ 个石子，此后所有仍可能被操作的堆大小都不小于 $s$，且这些堆可以两两配对，于是先手转为使用模仿策略即可获胜。

因此只需判断是否存在出现次数为奇数的堆大小。

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

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

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end());

    bool f = false;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && a[j] == a[i]) ++j;
        if ((j - i) & 1) {
            f = true;
            break;
        }
        i = j;
    }

    cout << (f ? "red" : "fang") << endl;
}

F 小红打牌

知识点：枚举、贪心、状态压缩

共有 $11$ 种顺子起点。对于每种顺子，枚举它使用次数对 $\texttt{3}$ 取模后的值，即 $\texttt{0},\texttt{1},\texttt{2}$，总状态数为：

$$3^{11}$$

这样做的原因是：同一种顺子每使用 $\texttt{3}$ 次，会消耗三个连续点数各 $\texttt{3}$ 张牌，等价于这三个点数各出一次三张相同牌。

枚举完顺子余数后，先检查用牌是否合法，剩余牌尽量组成三张相同牌。若 $b>a$，则三组相同牌可以改成三次顺子，并额外增加：

$$3(b-a)$$

此时在剩余的“三张相同牌块”上，从左到右贪心合成连续三段即可。因为处理到位置 $i$ 后，包含 $i$ 的后续顺子只可能从 $i$ 开始，所以能合成多少就合成多少是最优的。

时间复杂度 $\mathcal{O}(13\cdot 3^{11})$。

void solve() {
    int n, a, b;
    cin >> n >> a >> b;

    array<int, 13> cnt{};
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        cnt[x - 1]++;
    }

    int lim = 1;
    for (int i = 0; i < 11; ++i) lim *= 3;

    int ans = 0;
    for (int mask = 0; mask < lim; ++mask) {
        int t = mask;
        array<int, 13> used{}, block{};
        int cur = 0;

        for (int i = 0; i < 11; ++i) {
            int r = t % 3;
            t /= 3;
            cur += r * b;
            used[i] += r;
            used[i + 1] += r;
            used[i + 2] += r;
        }

        bool ok = true;
        for (int i = 0; i < 13; ++i) {
            if (used[i] > cnt[i]) {
                ok = false;
                break;
            }
            block[i] = (cnt[i] - used[i]) / 3;
            cur += block[i] * a;
        }
        if (!ok) continue;

        if (b > a) {
            int res = 0;
            for (int i = 0; i < 11; ++i) {
                int t = min({block[i], block[i + 1], block[i + 2]});
                res += t;
                block[i] -= t;
                block[i + 1] -= t;
                block[i + 2] -= t;
            }
            cur += 3 * (b - a) * res;
        }

        ans = max(ans, cur);
    }

    cout << ans << endl;
}

模板

#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;
}