【2025秋120】ACM周测（个人赛，div3）题解

B - A+B+C

Question

给出三个集合 $A, B, C$ ，每次询问给出一个 $X$ ，问是否存在从 $A, B, C$ 中挑出一个数字 $a, b, c$ ，使得 $a + b + c = X$

Solution

由于集合大小很小， $n^{3}$ 得预处理出 $a + b + c$ 可能的所有值，最后 map 判断即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, l;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];
    cin >> l;
    vector<int> c(l);
    for (int i = 0; i < l; i++) cin >> c[i];
    
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                mp[a[i] + b[j] + c[k]] = 1;
    
    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (mp.count(x) ? "Yes" : "No") << endl;
    }
    return 0;
}

C - String Bags

Question

初始时有一个空字符串 $S$ ，此外有 $1, 2, \dots, N$ 个袋子，每个袋子里面有装有一些字符串

袋子 $i$ 里包含 $A_{i}$ 个字符串，对于每个袋子，你可以选择两种操作中的一种：

支付 $1$ 元，从袋子中选择一个字符串，将其连接到 $S$ 的末尾
什么也不做

给定一个字符串 $T$ ，找到使最终 $S = T$ 所需要的最小金额

Solution

一眼背包问题，定义 $d p [i] [j]$ 表示枚举到第 $i$ 个袋子，前 $i - 1$ 个袋子已经把 $1 \sim j$ 的字符串组成了的最小代价

对于每个袋子中的一个串 $p$ ，如果 $p = T [j, j + p . s i z e - 1]$ ，那么代表可以往后添加 $p$ 字串，于是转移方程为：

d p [i] [j + p . s i z e - 1] = min {d p [i - 1] [j] + 1}

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    string T; cin >> T; T = " " + T;
    int n; cin >> n;
    vector<vector<string> > a(n + 1);
    for (int i = 1; i <= n; i++) {
        int m; cin >> m;
        for (int j = 0; j < m; j++) {
            string s; cin >> s;
            a[i].push_back(s);
        }
    }
    vector<vector<int> > dp(n + 1, vector<int>(T.size(), INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < T.size(); j++) {
            for (int k = 0; k < a[i].size(); k++) {
                if (j + a[i][k].size() - 1 >= T.size()) continue;
                if (T.substr(j, a[i][k].size()) == a[i][k])
                    dp[i][j + a[i][k].size() - 1] = min(dp[i][j + a[i][k].size() - 1], dp[i - 1][j - 1] + 1);
            }
        }

        for (int j = 0; j < T.size(); j++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, dp[i][T.size() - 1]);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

D - Gomamayo Sequence

Question

给你一个长度为 $N$ 的字符串 $S$ ，它由 0 和 1 组成

长度为 $N$ 的字符串 $T$ 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个好字符串：

恰好有一个整数 $i$ 使得 $1 \leq i \leq N - 1$ 和 $T$ 的第 $i$ 个字母和第 $(i + 1)$ 个字符相同

对于每个 $i = 1, 2, \dots, N$ ，您可以选择是否执行一次下面的操作：

如果 $S$ 的 $i$ 个字符是 0，则将其替换为 1，反之亦然。如果执行此操作，代价是 $C i$

求使 $S$ 成为一个好字符串所需的最小总成本

Solution

考虑到有且仅有一个 $i$ ，满足 $T_{i} = T_{i + 1}$ ，不妨假设 $T_{i} = T_{i + 1} = 1$ ，那么可知 $T_{i - 1} = 0, T_{i + 2} = 0$

$i$ 前面和 $i + 1$ 后面都是 0101 交替的，我们就可以记录一个交错的前缀和

定义 $p r e [i] [0]$ 表示第 $i$ 个字母，前面都是 0101 交替的，且第 $i$ 个字母为 0 花费的最小代价， $p r e [i] [1]$ 表示第 $i$ 个字母，前面都是 0101 交替的，且第 $i$ 个字母为 1 花费的最小代价

同理， $s u f [i] [0]$ 表示第 $i$ 个字母，后面都是 0101 交替的，且第 $i$ 个字母为 0 花费的最小代价

如何计算 $p r e$ ？交错着刷前缀和就好了

for (int i = 1; i <= n; i++) {
    pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
    pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
}

最后，关于 $T_{i} = T_{i + 1}$ 只有 $0$ ， $1$ 两种情况，分别枚举一次即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    vector<ll> c(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    
    vector<vector<ll> > pre(n + 2 , vector<ll>(2, 0)); auto lst = pre;
    for (int i = 1; i <= n; i++) {
        pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
        pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
    }
    for (int i = n; i > 0; i--) {
        lst[i][0] = lst[i + 1][1] + c[i] * (s[i] != '0');
        lst[i][1] = lst[i + 1][0] + c[i] * (s[i] != '1');
    }

    ll ans = INF;

    //00
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '0') + c[i + 1] * (s[i + 1] != '0');
        now += pre[i - 1][1] + lst[i + 2][1];
        ans = min(ans, now);
    }
    //11
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '1') + c[i + 1] * (s[i + 1] != '1');
        now += pre[i - 1][0] + lst[i + 2][0];
        ans = min(ans, now);
    }
    cout << ans << '\n';
    return 0;
}

E - Another Sigma Problem

Question

定义 $f (x, y)$ 表示把两个十进制接起来

例如 $f (2, 14) = 214$

给定数组 $A$ ，求：

\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (A_{i}, A_{j})

Solution

化简 $f (A_{i}, A_{j}) = A_{i} \times 10^{| A_{j} |} + A_{j}$

\begin{aligned} \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (A_{i}, A_{j}) & = \sum_{j = 2}^{N} \sum_{i = 1}^{j - 1} f (A_{i}, A_{j}) \\ = \sum_{j = 2}^{N} \sum_{i = 1}^{j - 1} A_{i} \times 10^{| A_{j} |} + A_{j} \\ = \sum_{j = 2}^{N} (A_{j} \times (j - 1) + 10^{| A_{j} |} \times \sum_{i = 1}^{j - 1} A_{i}) \end{aligned}

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll TT = 998244353;
ll ans = 0;
int main() {
    int n; cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> sum(n + 1, 0);
    vector<ll> pow10(15, 1);
    for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + a[i]) % TT;
    for (int i = 1; i <= 14; i++) pow10[i] = pow10[i - 1] * 10 % TT;
    for (int j = 2; j <= n; j++) {
        ans += a[j] * (j - 1);
        int num = log10(a[j]) + 1;
        ans += sum[j - 1] * pow10[num] % TT;
        ans %= TT;
    }
    cout << ans % TT << endl;
    return 0;
}