「题解」2025 ICPC 陕西省赛

唉唉，神秘暑假；

唉唉，神秘 VP；

L. 简单题

Easy-

给定 $n\times n$ 的矩阵 $a$ 满足 $a_{i,j}=(i-1)\times n + j$，若每行恰好选两个数，每列恰好选两个数，问被选择的数字之和的最小值。

明显可以看出无论如何选择，$(i-1)\times n$ 的部分总是会取到两遍 $i\in[1,n]$；同理，$j$ 的部分也是会取到两遍 $j\in[1,n]$，因此我们任意地选行首和行尾的数字之和相加即可。

当然，　$\color{red}{\mathbf{LOCK717}}$ 同志指出：我们可以用公式来实现 $O(1)$ 的复杂度。且不论在 $n\le10^3$ 的数据范围下是否有必要，我们还是推一下公式吧：

$$ \begin{align} S&=\sum_{i=1}^{n}[(i-1)n+j_{i,1}+(i-1)n+j_{j,2}]\\ &=\sum_{i=1}^{n}2(i-1)n+\sum_{i=1}^{n}(j_{i,1}+j_{i,2})\\ \end{align} $$

同时：

$$ \begin{align} \sum_{i=1}^{n}2(i-1)n&=2n\sum_{i=1}^n(i-1)=n^2(n-1)\\ \sum_{i=1}^{n}(j_{i,1}+j_{i,2})&=2\sum_{j=1}^nj= n(n+1)\\ \end{align} $$

于是有：

$$ S=n^2(n-1)+n(n+1)=n^3+n $$

代码

1
2
3
4
5
6


using i64 = long long;
void solve() {
    i64 n;
    cin >> n;
    cout << n * (n * n + 1) << "\n";
}

C. 最大公因数

Easy

给定正整数 $a,b$，求 $x$ 使得 $\gcd(a,x)=1\and\gcd(b,x)>1$

不妨令 $x=b$，若 $\gcd(a,x)\neq1$ 则 $x\leftarrow \frac{x}{\gcd(a,x)}$，直到 $\gcd(a,x)=1$ 为止。

此时再验证 $\gcd(b,x)>1$ 是否成立，若成立则输出 $x$，否则输出 $-1$

证明

由算术基本定理，记

$$ a=\prod_{p\in\mathcal P}p^{\alpha_p},\qquad b=\prod_{p\in\mathcal P}p^{\beta_p}, $$

其中 $\mathcal P$ 是所有在 $a$ 或 $b$ 中出现的素数，且 $\alpha_p,\beta_p\ge0$。任何正整数 $x$ 都可写作

$$ x=\prod_{p\in\mathcal P}p^{\gamma_p},\qquad \gamma_p\ge0. $$

则

$$ \gcd(a,x)=1\iff\forall\,p:\ \min(\alpha_p,\gamma_p)=0 \quad\Longleftrightarrow\quad \forall\,p\text{ with }\alpha_p>0:\ \gamma_p=0, $$

而

$$ \gcd(b,x)>1\iff\exists\,p:\ \min(\beta_p,\gamma_p)\ge1 \quad\Longleftrightarrow\quad \exists\,p\text{ with }\beta_p>0:\ \gamma_p\ge1. $$

算法取初值 $x_0=b$，对每一步定义

$$ x_{k+1} =\frac{x_k}{\gcd(a,x_k)}. $$

写出素因子分解

$$ x_k=\prod_{p}p^{\gamma_p^{(k)}},\quad \gcd(a,x_k)=\prod_{p}p^{\min(\alpha_p,\gamma_p^{(k)})}, $$

则

$$ \gamma_p^{(k+1)} =\gamma_p^{(k)}-\min(\alpha_p,\gamma_p^{(k)}) =\max\bigl(\gamma_p^{(k)}-\alpha_p,\,0\bigr). $$

由此，经过有限步后必有

$$ \gamma_p^{(\infty)} =\max(\beta_p-\alpha_p,0), $$

即算法结束时

$$ x=\prod_{p\in\mathcal P}p^{\gamma_p^{(\infty)}} =\prod_{\,p:\,\beta_p>\alpha_p}p^{\,\beta_p-\alpha_p}. $$

显然此时对于所有 $\alpha_p>0$ 都有 $\gamma_p^{(\infty)}=0$，故 $\gcd(a,x)=1$；若存在素数 $p$ 使 $\beta_p>\alpha_p$，则对应 $\gamma_p^{(\infty)}>0$，从而 $\gcd(b,x)\ge p>1$。若对所有 $p$ 都有 $\beta_p\le\alpha_p$，则 $x=1$ 并且 $\gcd(b,x)=1$，算法返回 $-1$，与无解情形相符。故所述方法正确。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


using i64 = long long;
void solve() {
    i64 a, b;
    cin >> a >> b;
    i64 x = b;
    while (gcd(a, x) != 1)
        x /= gcd(a, x);
    if (gcd(b, x) > 1)
        cout << x << "\n";
    else
        cout << "-1\n";
}

G. 学生

Easy

给定 $n$ 个整数 $a_i$，若：

$\exist\ l,r(l<i\and r>i),a_l\ge a_i\and a_i \le a_r$

或者

$\exist\ l,r(l<i\and r>i),a_l\le a_i\and a_i \ge a_r$

则可以删除 $a_i$，问最后最少能剩下多少人。

显然对于 $i=1$ 和 $i=n$ 来说，这两个元素是肯定删不掉的。

那么我们就只需要考虑全局最大值和全局最小值是否在开头或结尾即可。

记得特判 $n=1$ 的特殊情况。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;
    if (n == 1) {
        cout << "1\n";
        return;
    }
    int ans = 2;
    auto [mx, mn] = ranges::minmax(a);
    if (mx != a.front() and mx != a.back())
        ans++;
    if (mn != a.front() and mn != a.back())
        ans++;
    cout << ans << "\n";
}

J. 赢

Easy+

给定长度为 $n$ 的小写字符串 $s$ 和 $k$ 次操作，每次操作能在任意位置插入任意一个字符，问最多能找到多少个 lose。

可以枚举 lose 的所有非空子序列，共 $2^4-1=15$ 种情况，然后根据需要补的字符数量贪心地选择即可。同时如果 $k$ 有剩余的话我们能多找到 $\lfloor res/4\rfloor$ 个。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


void solve() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    map<string, int> mp;
    mp["l"] = mp["o"] = mp["s"] = mp["e"] = 3;
    mp["lo"] = mp["ls"] = mp["le"] = mp["os"] = mp["oe"] = mp["se"] = 2;
    mp["ose"] = mp["lse"] = mp["loe"] = mp["los"] = 1;
    mp["lose"] = 0;
    string t = "";
    priority_queue<int> pq;
    for (auto c : s) {
        string x = t + c;
        if (mp.count(x)) {
            t = x;
        } else {
            if (mp.count(t)) {
                pq.push(-mp[t]);
            }
            t = "";
            t += c;
        }
    }
    if (mp.count(t))
        pq.push(-mp[t]);
    int ans = 0;
    while (not pq.empty()) {
        if (k >= -pq.top()) {
            k -= -pq.top();
            ans++;
            pq.pop();
        } else {
            break;
        }
    }
    ans += k / 4;
    cout << ans << "\n";
}

K. 福利

Mid-

有两种奶牛：无私奶牛有 $n$ 头，自私奶牛有 $m$ 头。Steve 给出两个选项 A 和 B：选 A 的牛会平分共 $x$ 千克草（若共有 $k$ 头牛选 A，则每头得 $x/k$），选 B 的牛则各自获得 $y$ 千克。所有奶牛都知道 $n,m,x,y$ 的值。

选择按照两步进行：

无私奶牛先行。如果 $n>0$，它们推举出一位“领袖”，并由这位领袖为所有无私奶牛统一决定选 A 还是选 B，以使得最终全体奶牛得到的草总量最大（此时领袖已知下面第 2 步自私奶牛的决策规则）。
自私奶牛随后独立决策。如果 $m>0$，每只自私奶牛在知道所有无私奶牛已经作出的选择后，会假设其他所有自私奶牛都选 B，然后比较自己若选 A 可得的草量 $x/(U+1)$（其中 $U$ 是已有多少头无私牛选 A）与选 B 可得的 $y$：若 $x/(U+1)>y$ 则选 A，否则选 B。

求按照上述规则操作后，所有奶牛共能获得多少千克草（答案必为整数）。

按照题意分类讨论即可，情况比较复杂，详情见代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


using i64 = long long;
void solve() {
    i64 n, m, x, y;
    cin >> n >> m >> x >> y;

    i64 ans1 = 0, ans2 = 0, ans3 = 0; // 三种方案
    i64 maxn = 0;                     // 需要无私选 A 的头数
    bool has_case3 = false;

    /*——— 先处理无私奶牛相关 ——*/
    if (n > 0) {
        ans1 += x + (n - 1) * y; // 方案 1：留 1 头无私选 A
        ans2 += n * y;           // 方案 2：无私全选 B

        maxn = (y == 0 ? 0 : x / y + (x % y != 0));
        maxn = max<i64>(maxn - 1, 0); // ceil(x / y) - 1
        if (maxn > n) {
            ans3 = n * y; // 方案 3：U 太大，退化成全选 B
        } else {
            ans3 += (n - maxn) * y + x * (maxn > 0);
            has_case3 = true;
        }
    }

    /*——— 再处理自私奶牛相关 ——*/
    if (m > 0) {
        if (n == 0)
            ans1 += (x > y ? x : y * m);
        else
            ans1 += ((double)x / 2 > y ? 0 : y * m);

        ans2 += (x > y ? x : y * m);
        ans3 += (has_case3 ? y * m : (x > y ? x : y * m));
    }

    i64 ans = max({ans1, ans2, ans3});
    cout << ans << '\n';
}

A. 染色

Mid

给定 $n$ 个方块，每个方块的颜色最初是 $c_i$，把区间 $[l,r]$ 染成颜色 $i$ 的代价是 $w_i+(r-l+1)$，问对于每种颜色 $i$，把所有方块染成此色的最小代价是多少。

按照题意直接模拟即可，注意细节。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


using i64 = long long;
void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    // 按颜色收集出现位置
    vector<vector<int>> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        pos[c[i]].push_back(i);
    }

    vector<i64> ans(n + 1, 0);
    // 对每个目标颜色 col 计算最小花费
    for (int col = 1; col <= n; col++) {
        auto &P = pos[col];
        // 如果从未出现过，直接整条刷一遍
        if (P.empty()) {
            ans[col] = w[col] + n;
            continue;
        }

        // 找出所有“非 col 段”
        vector<pair<int, int>> segs;
        if (P.front() > 1) {
            segs.emplace_back(1, P.front() - 1);
        }
        for (int i = 0; i + 1 < (int)P.size(); i++) {
            if (P[i + 1] > P[i] + 1) {
                segs.emplace_back(P[i] + 1, P[i + 1] - 1);
            }
        }
        if (P.back() < n) {
            segs.emplace_back(P.back() + 1, n);
        }

        int m = segs.size();
        i64 total_non = n - P.size();
        // 初始：每段都单独刷
        i64 cost0 = 1ll * m * w[col] + total_non;

        // 考虑合并相邻两段：省一次 w[col]，但多刷 gap
        i64 Q = 0, sum_gap = 0;
        for (int i = 0; i + 1 < m; i++) {
            i64 gap = segs[i + 1].first - segs[i].second - 1;
            if (gap < w[col]) {
                Q++;
                sum_gap += gap;
            }
        }

        ans[col] = cost0 - Q * w[col] + sum_gap;
    }

    // 输出
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i < n ? ' ' : '\n');
    }
}

D. 买股票

Mid

给定 $n$ 个运算和一个初始值 $v$，第 $i$ 个运算要么是 $\times x_i$，要么是 $+x_i$，确定一个排列以最大化每一个运算后 $v_i$ 的平均值。

首先我们可以启发式的得出：两种运算的 $x_i$ 各自是单调不升的。这一点我们随便举几个例子就不难得出。然后问题转化为：如何构造一个排列使得 $\bar{v}$ 最大？考虑到 $n\le 30$，一个朴素的方法是枚举所有的排列，时间复杂度是 $O(n!)\approx 2\times10^{32}$ 显然过于大了。于是我们可以使用 DFS，维护元组 $(i_{\times},i_{+},cur,sum)$，终止条件是 $i_\times=N_\times\and i_+=N_+$，在此时更新答案即可。对于任意的 $i_\times<N_\times$ 都可以分支使得下一步的状态是 $i_\times\gets i_\times+1$，$i_+$ 同理，不断递归即可。

需要注意的地方

VP 的时候，某位队员写了一行很神秘的 #define double long double 导致接连好几发 TLE 了~~（还查不出哪有问题）~~，在这里指出：double 本身就是 64 位的，而 long double 则是 128 位的，不知道慢到哪里去了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


using i32 = int;
using f64 = double;
void solve() {
    i32 n;
    f64 v;
    cin >> n >> v;
    vector<f64> plus, times;
    for (int i = 0; i < n; i++) {
        char op;
        f64 x;
        cin >> op >> x;
        if (op == '+')
            plus.emplace_back(x);
        else
            times.emplace_back(x);
    }
    ranges::sort(plus, greater{});
    ranges::sort(times, greater{});
    const i32 Np = plus.size(), Tp = times.size();
    f64 ans = 0;
    auto dfs = [&](this auto &&self, i32 ip, i32 it, f64 cur, f64 sum) {
        if (ip == Np - 1 and it == Tp - 1) {
            ans = max(ans, sum);
            return;
        }
        if (ip + 1 < Np) {
            self(ip + 1, it, cur + plus[ip + 1], sum + cur + plus[ip + 1]);
        }
        if (it + 1 < Tp) {
            self(ip, it + 1, cur * times[it + 1], sum + cur * times[it + 1]);
        }
    };
    dfs(-1, -1, v, 0);
    cout << fixed << setprecision(10) << ans / n << "\n";
}

E. 打字

Mid+

显然是状压 DP。

我们用一个长度为 $n$ 的二进制数 $\text{mask}$ 来表示一个集合 $S$ 代表哪些位置已经打印过，然后再引入一个变量 $\text{last}\in[0,n]$ 表示上一次打印的下标，其中若 $\text{last}=n$ 则表示尚未打印任何字符。那么我们的状态 $f_{\text{mask},\text{last}}$ 就表示：在已打印集合 $S$ 中，最后打印为 $\text{last}$ 位时的最小代价。不难得到初始条件是：对于 $S=\varnothing,\text{last}=n$ 时，此时没有消耗任何代价，即 $f_{\text{mask},\text{last}}=0$

我们从当前状态转移到下一个状态时，必然是会在集合 $S$ 中新增一个元素，记这个元素为 $j$，令 $\text{mask}’$ 表示 $S\cup {j}$，然后我们需要关心的就是我们光标移动的距离到底是多少，其距离并非是 $|\text{last}-j|$ 而是两者之间的已经存在的字符的个数（很惭愧，VP 的时候居然脑抽了没想到这一块）我们把它记做 $|\Delta|$，因此有转移方程：

$$ f_{\text{mask}',j}=\min(f_{\text{mask}',j},f_{\text{mask}, \text{last}}+|\Delta|t+\text{cost}_{s_\text{last},s_j}+t) $$

按照此方程实现即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


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

using i64 = long long;
constexpr i64 INF = (1LL << 60);

void solve() {
    int n, m;
    i64 t;
    cin >> n >> m >> t;

    string str;
    cin >> str;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) s[i] = str[i] - 'a';

    vector<vector<i64>> w(m, vector<i64>(m));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < m; ++j)
            cin >> w[i][j];

    int N = 1 << n;
    /* f[mask][last]，last==n 表示起点 */
    vector<vector<i64>> f(N, vector<i64>(n + 1, INF));
    f[0][n] = 0;

    for (int mask = 0; mask < N; ++mask)
        for (int last = 0; last <= n; ++last) {
            i64 cur = f[mask][last];
            if (cur == INF) continue;

            /* 当前光标位置与左手所指 */
            int cursor, finger;
            if (last == n) {
                cursor = 0;
                finger = 0;          // 初始在 'a'
            } else {
                cursor = __builtin_popcount(mask & ((1 << last) - 1)) + 1;
                finger = s[last];
            }

            for (int i = 0; i < n; ++i)
                if (!(mask >> i & 1)) {
                    int pos = __builtin_popcount(mask & ((1 << i) - 1));
                    i64 add = llabs(cursor - pos) * t + w[finger][s[i]] + 1;
                    int nxt = mask | (1 << i);
                    f[nxt][i] = min(f[nxt][i], cur + add);
                }
        }

    i64 ans = INF;
    int full = N - 1;
    for (int last = 0; last < n; ++last) ans = min(ans, f[full][last]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}