2025春训第十七场

A. 最大公约数#

直接枚举 1 ~ n 对于每一个数从他不等于自己的约数里面找个最大的，然后全部取个 max。

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
int main() {
7
    int n, res = 1;
8
    cin >> n;
9
    for (int i = 1; i <= n; ++i) {
10
        int l = sqrt(i);
11
        for (int j = 2; j <= l; ++j) {
12
            if (i % j == 0) {
13
                res = max(res, i / j);
14
                break;
15
            }
16
        }
17
    }
18
    cout << res << endl;
19
    return 0;
20
}

B. 数的变换#

非常的水。

约数中每有一个约数 2，次数 + 1；
每有一个约数 3，次数 + 2（因为算完之后还需要处理造出来的一个 2；
每有一个约数 5，次数 + 3（因为算完之后还需要处理造出来的两个 2）；

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        long long n, t = 0;
10
        scanf("%lld", &n);
11
        while (n % 5 == 0) n /= 5, t += 3;
12
        while (n % 3 == 0) n /= 3, t += 2;
13
        while (n % 2 == 0) n /= 2, t ++;
14
        if (n == 1)
15
            printf("%lld\n", t);
16
        else
17
            printf("-1\n");
18
    }
19
    return 0;
20
}

C. 回文#

这道题其实可以直接暴力，因为一共只可能有 $\binom{2}{26}$ 种可能的不能配对的方式，于是就有不多于 $\binom{2}{26}^2$ 种可能的交换情况，于是直接枚举所有情况交换即可。

1
#include <iostream>
2
#include <algorithm>
3
#include <map>
4

5
using namespace std;
6

7
int a[26];
8
map<pair<int, int>, int> mp;
9
int mn = 0x3f3f3f3f;
10

11
int ord(char c) {
12
    return c - 'a';
13
}
14

15
long long getmin(int x, int y) {
16
    return min(min(a[x], a[y]), mn * 2);
17
}
18

19
int main() {
20
    ios::sync_with_stdio(0);
21
    cin.tie(0), cout.tie(0);
22
    int n;
23
    cin >> n;
24
    for (int i = 0; i < 26; ++i) {
25
        cin >> a[i];
26
        mn = min(mn, a[i]);
27
    }
28
    string s;
29
    cin >> s;
30
    s = ' ' + s;
31
    long long res = 0;
32
    for (int i = 1; i <= (n / 2); ++i) {
33
        if (s[i] != s[n - i + 1]) {
34
            res += min(min(a[ord(s[i])], a[ord(s[n - i + 1])]), mn * 2);
35
            int lv = ord(s[i]), rv = ord(s[n - i + 1]);
36
            if (lv > rv) swap(lv, rv);
37
            mp[{lv, rv}]++;
38
        }
39
    }
40
    long long ss = 0;
41
    for (auto [p, t] : mp) {
42
        if (t > 1) {
43
            ss = min(ss, -2ll * min(min(a[p.first], a[p.second]), mn * 2));
44
        }
45
        for (auto [pp, _] : mp) {
46
            if (pp == p) continue;
47
            ss = min(ss,
48
                min(
49
                    getmin(p.first, pp.first) + getmin(p.first, pp.second),
50
                    getmin(p.first, pp.second) + getmin(p.second, pp.first)
51
                ) - getmin(p.first, p.second) - getmin(pp.first, pp.second)
52
            );
53
        }
54
    }
55
    res = min(res, res + ss);
56
    cout << res << endl;
57
    return 0;
58
}

E. 船长的自助餐#

一道数据比较友好的 dp 题，至于我为什么在红温，当然是没好好读题就去做了 😇😇😇

连着吃 $\lceil \log_{\frac{2}{3}}{M} \rceil$ 次胃容量就变成 0 了，当然如果你没发现这个，直接把胃容量整个当一个状态塞进去应该也是不会 TLE 的，如果能离散化一下会更快。

记 $f_{i, j, 1}$ 为吃到第 i 天，已经连续吃了 j 次，并且第 i 天吃了的情况下能吃的最大值； $f_{i, j, 0}$ 为第 i 天没吃的情况下的最大值。

f_{i, 1, 0} = \max \{ f_{i - 1, j, 0} \}

f_{i, j, 0} = \max \{f_{i - 1, j, 0}, f_{i - 1, j, 1} \} \ (j \neq 1)

f_{i, j, 1} = \max\{f_{i - 1, j, 0} + \min \{m_j, A_i\}, f_{i - 1, j - 1, 1} + \min \{m_j, a_i \} \} \ (m_j = \text{连续吃了} j \text{次后胃容量})

1
#include <iostream>
2
#define int long long
3

4
using namespace std;
5

6
const int N = 1010;
7

8
int n, m[70], a[N];
9
long long f[N][70][2];
10

11
signed main() {
12
    scanf("%lld%lld", &n, &m[1]);
13
    int l;
14
    for (l = 2; m[l - 1]; ++l) m[l] = m[l - 1] * 2 / 3;
15
    l--;
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%lld", &a[i]);
18
    }
19
    for (int i = 1; i <= n; ++i) {
20
        for (int j = 1; j <= l; ++j) {
21
            f[i][1][0] = max(f[i][1][0], f[i - 1][j][0]);
22
        }
23
        for (int j = 1; j <= l; ++j) {
24
            f[i][j][0] = max(f[i][j][0], max(f[i - 1][j][0], f[i - 1][j][1]));
25
        }
26
        f[i][1][1] = f[i - 1][1][0] + min(m[1], a[i]);
27
        for (int j = 2; j <= l; ++j) {
28
            f[i][j][1] = max(f[i - 1][j][0] + min(m[j], a[i]), f[i - 1][j - 1][1] + min(m[j], a[i]));
29
        }
30
    }
31
    long long res = 0;
32
    for (int i = 1; i <= l; ++i) {
33
        res = max(res, max(f[n][i][0], f[n][i][1]));
34
    }
35
    printf("%lld\n", res);
36
    return 0;
37
}

Star's Blog

A. 最大公约数#

B. 数的变换#

C. 回文#

E. 船长的自助餐#