2025春训第九场 - Star's Blog

A. 鲁的智力#

我刚开始看到这道题之后默默的放弃了，选择了后面的 dp 题。

最小排名：至少有多少个人比他分数高。
最大排名：至少有多少个人比他分数低。

两边都是考虑极限情况，以第一种为例。一个人要想稳定的分数比另一个人高，那必然每道题都比另一个高，于是问题转化成至少有几个人每道题分数都比他高。设第 i 道题的排名是 $a_i$ ，考虑一道题的时候，情况是确定的，这道题比他高的人肯定满足所有题都比他高；两道题的时候，考虑边界情况——第二道题比他高的人和第一道题比他高的人最大程度的不重叠，所以人数应该是 $\max\{0, a_2 + a_1 - m - 1\}$ ；现在相当于前两道题已经合成一道大的题了，再不断往下计算就能算出来最后的结果。第二种同理。

1
#include <iostream>
2

3
using namespace std;
4

5
int a[1010];
6

7
int main() {
8
    int n, m, l, r;
9
    cin >> n >> m;
10
    l = r = m - 1;
11
    for (int i = 1; i <= n; ++i) {
12
        cin >> a[i];
13
        l = max(0, a[i] + l - m);
14
        r = max(0, (m - a[i]) + r - (m - 1));
15
    }
16
    cout << l + 1 << endl << m - r << endl;
17
    return 0;
18
}

B. 鲁的女孩#

最优的配对方案是一个正序一个倒序一一配对。关键的性质是 1 ≤ a, b ≤ 100，开两个数组记录 [1, 100] 每个数的个数，然后双指针扫描一次即可得出答案。事实可以证明，挺容易写挂的（比如我）

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

4
using namespace std;
5

6
int a[210], b[210];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n;
12
    cin >> n;
13
    for (int i = 1; i <= n; ++i) {
14
        int ta, tb;
15
        cin >> ta >> tb;
16
        a[ta]++, b[tb]++;
17
        int mx = -0x3f3f3f3f;
18
        int l = 0, r = 101;
19
        int lc = 0, rc = 0;
20
        while (l <= 100 && r > 0) {
21
            if (lc && rc) {
22
                mx = max(mx, l + r);
23
                int tmp = min(lc, rc);
24
                lc -= tmp, rc -= tmp;
25
            }
26
            if (!rc) rc = b[--r];
27
            if (!lc) lc = a[++l];
28
        }
29
        cout << mx << endl;
30
    }
31
    return 0;
32
}

C. 鲁的石板#

前排警告，最好别用 vector 一直申请内存容易 TLE😭

这题好像有数学的方法可以一个式子秒了，没关系，我会一个矩阵快速幂秒了。

线性 dp 的方法是开一个状态数组 f[N][2]，f[i][0] = 表示涂到第 i 块且第 i 块颜色和第一块一致的方案数，f[i][1] 表示涂到第 i 块且第 i 块颜色和第一块不一致的方案数，答案是 f[n][1]。

f_{i, 0} = f_{i - 1, 1}

f_{i, 1} = (m - 1)f_{i - 1, 0} + (m - 2)f_{i - 1, 1}

用矩阵乘法写这个递推式

\begin{pmatrix} f_{i - 1, 0} & f_{i - 1, 1} \end{pmatrix} \begin{pmatrix} 0 & m - 1\\ 1 & m - 2 \end{pmatrix} = \begin{pmatrix} f_{i, 0} & f_{i, 1} \end{pmatrix}

显然答案是 $[\begin{pmatrix} m & 0\end{pmatrix}\begin{pmatrix} 0 & m - 1 \\ 1 & m - 2 \end{pmatrix}^{n - 1}]_{1, 2}$ ，即 $m\begin{pmatrix} 0 & m - 1 \\ 1 & m - 2 \end{pmatrix}^{n - 1}_{1, 2}$ .

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

4
using namespace std;
5

6
const int MOD = 1000000007;
7

8
long long mat[2][2], res[2][2], a[2][2], b[2][2];
9

10
void mul(long long a[][2], long long b[][2]) {
11
    static long long t[2][2];
12
    t[0][1] = t[0][0] = t[1][1] = t[1][0] = 0;
13
    for (int k = 0; k < 2; ++k) {
14
        for (int i = 0; i < 2; ++i) {
15
            for (int j = 0; j < 2; ++j) {
16
                t[i][j] = (t[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
17
            }
18
        }
19
    }
20
    for (int i = 0; i < 2; ++i) {
21
        for (int j = 0; j < 2; ++j) {
22
            a[i][j] = t[i][j];
23
        }
24
    }
25
}
26

27
int main() {
28
    int T;
29
    scanf("%d", &T);
30
    while (T--) {
31
        int n, m;
32
        scanf("%d%d", &n, &m);
33
        if (n == 1) {
34
            cout << m << endl;
35
            continue;
36
        }
37
        mat[0][0] = 0, mat[0][1] = m - 1, mat[1][0] = 1, mat[1][1] = m - 2;
38
        res[0][0] = res[1][1] = 1, res[0][1] = res[1][0] = 0;
39
        n--;
40
        while (n) {
41
            if (n & 1) mul(res, mat);
42
            mul(mat, mat);
43
            n >>= 1;
44
        }
45
        printf("%d\n", (long long)m * res[0][1] % MOD);
46
    }
47
    return 0;
48
}

D. 游览计划#

提供一个暴力的解法，具体有多暴力见下图，差点拼尽全力无法战胜了……

暴力的流程是

对于每一个点跑一遍 bfs 找到到所有其他点的最短路；
对于每一个点找到最短路最长的三个点，记下来；
暴力枚举中间点 B, C，枚举到 B 距离最长的三个 A，到 C 距离最长的三个 D，过滤所有A, B, C, D 重复情况，把路径加起来更新答案。

这个做法显然是正确的，存了三个最远的点保证了最坏的情况下也不至于全部冲突。

代码后续更新了一下，不会 997ms 了。

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

4
using namespace std;
5

6
const int N = 4010, M = 5010;
7
int head[N], ne[M * 2], ver[M * 2], tot;
8
int d[N][N], q[N], hh, tt;
9
int mxp[N][3];
10

11
inline void read(int &_) {
12
    _ = 0;
13
    char c = getchar();
14
    while (!isdigit(c)) c = getchar();
15
    while (isdigit(c)) _ = _ * 10 + c - 48, c = getchar();
16
}
17

18
inline void add(int x, int y) {
19
    ver[++tot] = y;
20
    ne[tot] = head[x];
21
    head[x] = tot;
22
}
23

24
int main() {
25
    int n, m;
26
    read(n), read(m);
27
    for (int i = 1; i <= m; ++i) {
28
        int x, y;
29
        read(x), read(y);
30
        add(x, y);
31
        add(y, x);
32
    }
33
    memset(d, -1, sizeof(d));
34
    for (int i = 1; i <= n; ++i) {
35
        hh = tt = 0;
36
        d[i][i] = 0;
37
        q[tt] = i;
38
        while (hh <= tt) {
39
            int x = q[hh++];
40
            if (d[i][x] >= d[i][mxp[i][0]]) {
41
                mxp[i][2] = mxp[i][1], mxp[i][1] = mxp[i][0];
42
                mxp[i][0] = x;
43
            }
44
            else if (d[i][x] >= d[i][mxp[i][1]]) {
45
                mxp[i][2] = mxp[i][1];
46
                mxp[i][1] = x;
47
            }
48
            else if (d[i][x] >= d[i][mxp[i][2]]) {
49
                mxp[i][2] = x;
50
            }
51
            for (int j = head[x]; j; j = ne[j]) {
52
                int y = ver[j];
53
                if (~d[i][y]) continue;
54
                d[i][y] = d[i][x] + 1;
55
                q[++tt] = y;
56
            }
57
        }
58
    }
59
    int res = 0;
60
    for (int i = 1; i <= n; ++i) {
61
        for (int j = 1; j < i; ++j) {
62
            for (int k = 0; k < 3; ++k) {
63
                if (mxp[i][k] == j) continue;
64
                for (int p = 0; p < 3; ++p) {
65
                    if (i != mxp[j][p] && mxp[i][k] != mxp[j][p])
66
                        res = max(res, d[mxp[i][k]][i] + d[i][j] + d[j][mxp[j][p]]);
67
                }
68
            }
69
        }
70
    }
71
    printf("%d\n", res);
72
    return 0;
73
}