【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,\cdots,N$ 个袋子，每个袋子里面有装有一些字符串

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

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

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

Solution

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

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

$dp[i][j+p.size-1]=\min\{dp[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,\ldots, N$ ，您可以选择是否执行一次下面的操作：

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

求使 $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 交替的，我们就可以记录一个交错的前缀和

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

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

如何计算 $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');
}

最后，关于 $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\limits_{i=1}^{N-1}\sum\limits_{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\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^N f(A_i,A_j) &=\sum\limits_{j=2}^{N}\sum\limits_{i=1}^{j-1}f(A_i,A_j)\\ &=\sum\limits_{j=2}^{N}\sum\limits_{i=1}^{j-1} A_i\times 10^{|A_j|}+A_j\\ &=\sum\limits_{j=2}^N (A_j\times (j-1)+10^{|A_j|}\times \sum\limits_{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;
}