第四届成都信息工程大学天梯赛

写了一半，群里发出来官方题解了……~~但是我码风比他的好，可读性强一点~~，但是为了~~强迫症和~~留作记录，我必须写完😇。所以这篇博客的性质已经从题解 transform 成赛后的感想了。

个人感觉有点像是水赛的感觉，L1 非常顺利，L2 和 L3 的最后两道开始调不出来，最终结果是 190 分(我的 L3-1 的 30 分还被队友吃了😭），L1 拿满，L2 的 3，4 WA，L3 的 2 TLE，3 没看。

我的 windows 还没回来，所以用的机房的编译一下就死机的电脑（但这不是我没存代码的理由），只能事后重敲一遍代码了，顺便回忆一下当时的心情。

L1 基础级#

L1 的 8 道题都非常顺利，没有被卡，可惜速度还是没有 @xx liu (qwertyuiop) 快。

L1-1 遇见YFffffff#

1
print('Hello YFffffff')

L1-2 桃之夭夭，灼灼其华#

1
n = int(input())
2
s = max(map(int, input().split()))
3
print(s, 'sad' if s & 1 else 'love')

L1-3 体温预警系统#

1
n = int(input())
2
if n:
3
    t = [0 for i in range(4)]
4
    s = ['zhengchang', 'dire', 'gaore', 'yichangshuju']
5
    for i in range(n):
6
        tmp = round(float(input()) * 10)
7
        if tmp in range(360, 373):
8
            t[0] += 1
9
        elif tmp in range(373, 381):
10
            t[1] += 1
11
        elif tmp in range(381, 411):
12
            t[2] += 1
13
        else:
14
            t[3] += 1
15
    print('\n'.join(f'{s[i]}:{t[i]}' for i in range(4) if t[i]))
16
else:
17
    print('wuxiaoshuju')

L1-4 破碎的心，无法挽回的距离#

1
#include <iostream>
2

3
using namespace std;
4

5
int a[110];
6

7
int main() {
8
    int n, res = 0x3f3f3f3f;
9
    cin >> n;
10
    for (int i = 1; i <= n; ++i) {
11
        cin >> a[i];
12
    }
13
    for (int p = 1; p <= 100; ++p) {
14
        int s = 0;
15
        for (int i = 1; i <= n; ++i) {
16
            s += (a[i] - p) * (a[i] - p);
17
        }
18
        res = min(res, s);
19
    }
20
    cout << res << endl;
21
    return 0;
22
}

L1-5 心碎？抽卡时间！#

1
a = list(map(int, input().split()))
2
b = list(map(int, input().split()))
3
for i in range(4):
4
    if a[i] < b[i]:
5
        print('spider YFffffff')
6
        break
7
    else:
8
        a[i + 1] += (a[i] - b[i]) // 5
9
else:
10
    print(a[4] if a[4] else 'QAQ')

L1-6 字符串糕手#

1
l = int(input())
2
s = input()
3
res = 1000
4
for i in range(l // 2, l):
5
    t = s[:i] + s[i::-1]
6
    res = min(res, i * 2 + 1 - l) if s == (s[:i] + s[i::-1])[:l] else res
7
    res = min(res, i * 2 - l) if s == (s[:i] + s[i - 1::-1])[:l] else res
8
print(res)

L1-7 若敢来氪，必叫你大败而归#

1
l = []
2
n, x = map(int, input().split())
3
for i in range(n):
4
    a = input().split()
5
    l.append((-int(a[1]), -int(a[2]), -int(a[3]), int(a[4]), a[0]))
6

7
cnt = 0
8
l.sort()
9
for i in l:
10
    if x - i[3] >= 0:
11
        print(i[4])
12
        x -= i[3]
13
        cnt += 1
14
    else:
15
        break
16
print(cnt)

L1-8 回到她的身边好吗#

1
n, m, k, p = map(int, input().split())
2
a = [(0, 0)]
3
for i in range(m):
4
    a.append(tuple(map(int, input().split())))
5
a.append((n, n))
6
a.sort()
7
for i in range(1, len(a)):
8
    if a[i][0] - a[i - 1][1] > k:
9
        if p and k:
10
            p, k = p - 1, k - 1
11
        else:
12
            print('buguanle', a[i - 1][1])
13
            break
14
else:
15
    print('YES', k)

这个时候 L1 顺着做完了，还在沾沾自喜。

L2 进阶级#

实话说我感觉不是很困难的，但是 wa 了两道题。

L2-1 来自YFffffff的挑战#

这个策略当时有一定蒙的成分，实际上也是正确的。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    int T;
9
    cin >> T;
10
    while (T--) {
11
        int n;
12
        string s, t = "";
13
        cin >> n >> s;
14
        if (n == 1 || s[1] >= s[0]) cout << s[0] << s[0] << endl;
15
        else {
16
            for (char c : s) {
17
                if (t.empty() || c <= t.back()) t += c;
18
                else break;
19
            }
20
            cout << t;
21
            for (int i = t.length() - 1; i >= 0; --i) cout << t[i];
22
            cout << endl;
23
        }
24
    }
25
    return 0;
26
}

L2_2 不要刁难我们了#

最短路板子题，做到这儿的时候也还是非常顺利，这时候心态已经被机房电脑磨的差不多了，这次不怪电脑怪我没事先拷过来一份新的编译器，我在本地调试的时候因为 >>> 不能连续，auto 遍历 vector 不能用被折磨的要死，还好是一遍过了。

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

5
using namespace std;
6

7
const int N = 200010;
8
vector<pair<int, int>> ed[N];
9
int w[N];
10
long long dis[N], cnt[N];
11
bool vis[N];
12

13
int main() {
14
    ios::sync_with_stdio(0);
15
    cin.tie(0), cout.tie(0);
16
    int n, m, s, t;
17
    cin >> n >> m >> s >> t;
18
    for (int i = 1; i <= n; ++i) cin >> w[i];
19
    for (int i = 1; i <= m; ++i) {
20
        int x, y, z;
21
        cin >> x >> y >> z;
22
        ed[x].push_back({z, y});
23
        ed[y].push_back({z, x});
24
    }
25
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
26
    memset(dis, 0x3f, sizeof(dis));
27
    cnt[s] = 1;
28
    dis[s] = 0;
29
    q.push({dis[s], s});
30
    while (!q.empty()) {
31
        int x = q.top().second;
32
        q.pop();
33
        if (vis[x]) continue;
34
        vis[x] = true;
35
        for (auto [v, y] : ed[x]) {
36
            if (dis[y] > dis[x] + w[y] + v) {
37
                dis[y] = dis[x] + w[y] + v;
38
                cnt[y] = cnt[x];
39
                q.push({dis[y], y});
40
            }
41
            else if (dis[y] == dis[x] + w[y] + v) {
42
                cnt[y] += cnt[x];
43
            }
44
        }
45
    }
46
    cout << dis[t] << endl << cnt[t] << endl;
47
    return 0;
48
}

L2-3 花非花，雾非雾#

我 wa 掉的做法是开了个队列存储边，有更改的时候从更改的点出发 dfs 更新所有能更新的点，但是问题在于我 dfs 的路径并不一定是按照边从前到后更新的；其实当时又想到用并查集，但是最后又暂时放弃了。

这道题最后的有效关系图一定是一个森林，每个连通子图都是有向树，边从根指向叶子，其中只有根结点的 a 已经给出，从根到叶子跑一遍 dfs 就可以更新出所有点的 a；用并查集可以维护一个子图内是否已经有一个 a 已经给出的根节点，对于一个 U 关系，两个已经有根的子图连在一起或者子图内部连边可能会矛盾，即使不矛盾这条边也是多余的，所以全部都判定为无效即可。

ps: dfs 会爆栈，别问我怎么知道的。

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

5
using namespace std;
6

7
const int N = 40010;
8
vector<pair<int, int>> ed[N];
9
int fa[N], a[N];
10
bool f[N]; // 维护是否已经有根
11

12
int getfa(int x) {
13
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
14
}
15

16
int main() {
17
    ios::sync_with_stdio(0);
18
    cin.tie(0), cout.tie(0);
19
    int n, m;
20
    cin >> n >> m;
21
    for (int i = 1; i <= n; ++i) fa[i] = i;
22
    while (m--) {
23
        char c;
24
        cin >> c;
25
        if (c == 'U') {
26
            int x, y, w;
27
            cin >> x >> y >> w;
28
            int px = getfa(x), py = getfa(y);
29
            if (px == py || (f[px] & f[py])) continue;
30
            fa[py] = px;
31
            f[px] ^= f[py];
32
            ed[x].push_back({w, y});
33
            ed[y].push_back({w, x});
34
        }
35
        else {
36
            int x, w;
37
            cin >> x >> w;
38
            if (!f[getfa(x)]) {
39
                a[x] = w;
40
                f[getfa(x)] = true;
41
            }
42
        }
43
    }
44
    queue<int> q;
45
    for (int i = 1; i <= n; ++i) {
46
        if (a[i]) q.push(i);
47
    }
48
    while (!q.empty()) {
49
        int x = q.front();
50
        q.pop();
51
        for (auto [v, y] : ed[x]) {
52
            if (a[y]) continue;
53
            a[y] = a[x] ^ v;
54
            q.push(y);
55
        }
56
    }
57
    for (int i = 1; i <= n; ++i) {
58
        if (!a[i]) {
59
            cout << "sad" << endl;
60
            return 0;
61
        }
62
    }
63
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
64
    cout << endl;
65
    return 0;
66
}

L2-4 是留不住你的冰寒飞影#

我现在还认为滑动窗口是可行的，考场上写的可能逻辑还是有点小问题，本质上我当时写的单调队列只是没有具象化的把点合并了。照着题解的思路写完代码之后发现我当时的问题是维护的范围小了，一个滑动窗口能 0 代价到达的最左端和最右端由左侧第二个和右侧第二个点决定，而不是窗口的左右端点。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6
int a[N];
7
int l[N], r[N], t;
8

9
int main() {
10
    int T;
11
    scanf("%d", &T);
12
    while (T--) {
13
        int n, k, m;
14
        scanf("%d%d%d", &n, &k, &m);
15
        for (int i = 1; i <= n; ++i) {
16
            scanf("%d", &a[i]);
17
        }
18
        t = 0;
19
        a[0] = -0x3f3f3f3f, a[n + 1] = 0x3f3f3f3f;
20
        for (int i = 1; i <= n; ++i) {
21
            if (i == 1 && a[i + 1] - a[i] > k || i == n && a[i] - a[i - 1] > k) {
22
                t++;
23
                l[t] = r[t] = a[i];
24
            }
25
            else if (a[i] - a[i - 1] <= k) {
26
                l[t] = min(l[t], a[i] - k);
27
                r[t] = max(r[t], a[i - 1] + k);
28
            }
29
            else if (a[i + 1] - a[i] <= k) {
30
                t++;
31
                l[t] = r[t] = a[i];
32
            }
33
        }
34
        for (int i = 2; i <= t; ++i) {
35
            m -= (l[i] - r[i - 1] + k - 1) / k;
36
        }
37
        if (m >= 0) printf("Yes\n");
38
        else printf("No\n");
39
    }
40
    return 0;
41
}

L3 登顶级#

L3-1 银白之森#

想到敲了二十多分钟基环树 dp 代码，我自己都想笑😇😇😇。这是一张后继图，每个点初度为1，所以构成基环树，然后我就想偏了。其实不用区分环内环外直接一起倍增预处理一下然后把 k 二进制分解算就行。还是忘不了之前一道树上倍增 + 环形dp 的基环树题😮‍💨，我写着写着发现环里面还得倍增，然后用了同一个倍增数组，又写了一会儿才发现问题的严重性，直接把代码全删了重写了一遍。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6

7
int f[N][50];
8
long long g[N][50];
9

10
int main() {
11
    int n, m;
12
    scanf("%d%d", &n, &m);
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%d", &f[i][0]);
15
        g[i][0] = f[i][0];
16
    }
17
    for (int j = 1; j < 50; ++j) {
18
        for (int i = 1; i <= n; ++i) {
19
            f[i][j] = f[f[i][j - 1]][j - 1];
20
            g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
21
        }
22
    }
23
    while (m--) {
24
        int x;
25
        long long k, res = 0;
26
        scanf("%d%lld", &x, &k);
27
        for (int i = 0; i < 50; ++i) {
28
            if (k >> i & 1) {
29
                res += g[x][i];
30
                x = f[x][i];
31
            }
32
        }
33
        printf("%lld\n", res);
34
    }
35
    return 0;
36
}

L3-2 摸球游戏#

当时矩阵快速幂 t 了，按说不该 t 的；但是这不是重点，重点是：我要向我高中数学老师道歉😭，这道题是一阶线性递推求通项，我把他当二阶的了，甚至还试图找特征方程。2025/03/07 晚上 22:00 我突然意识到了问题的严重性，于是一个不动点求出来等比数列的递推式然后秒了。他的题解太麻烦了，其实这就是一道平平无奇的高中概率题，果然上大学🧠会退化。

计球的总个数为 n，i 次操作后的期望为 $E_i$ ，根据期望递推，有

E_i = \frac{E_{i - 1}}{n}E_{i - 1} + \frac{n - E_{i - 1}}{n}(E_{i - 1} + 1)

化简得

E_i = \frac{n - 1}{n}E_{i - 1} + 1

计算不动点，解方程 $x = \frac{n - 1}{n}x + 1$ 得， $x= n$ . 所以有

E_i - n = \frac{n - 1}{n}(E_{i - 1} - n)

后面就不用我教了，首项是 n - a，公比是 $\frac{n - 1}{n}$ 等比数列通向公式直接求 $E_k$ 即可。

对不起 90 老师，过了半年就忘干净了😭😭😭.

1
#include <iostream>
2

3
using namespace std;
4

5
int MOD = 1000000007;
6

7
long long power(long long n, long long p) {
8
    long long res = 1, base = n;
9
    while (p) {
10
        if (p & 1) res = res * base % MOD;
11
        base = base * base % MOD;
12
        p >>= 1;
13
    }
14
    return res;
15
}
16

17
int main() {
18
    ios::sync_with_stdio(0);
19
    cin.tie(0), cout.tie(0);
20
    int T;
21
    long long a, b, c, k;
22
    cin >> T;
23
    while (T--) {
24
        cin >> a >> b >> k;
25
        b += a;
26
        cout << (((a - b + MOD) % MOD * power((b - 1) * power(b, MOD - 2) % MOD, k)) % MOD + b + MOD) % MOD << endl;
27
    }
28
    return 0;
29
}

L3-3 电荷#

这道自己做是真做不出来，正确的结论是一个 D 合法当且仅当按 x 排序检查和按 y 排序检查至少有一个可以通过，其余情况通过适当交换可以转化成按 x 和 y 检查的一种。如果我自己想只能想到按其中一个排序，调代码的时候也是调的非常头疼。

代码还可以压一压，排序和前缀后缀 max 和 min 可以写成一个函数~~。但是我已经不想看这个💩了~~

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
#include <vector>
5

6
using namespace std;
7

8
const int N = 100010;
9
pair<int, int> a[N];
10
int pre_mn[N], pre_mx[N], pos_mn[N], pos_mx[N];
11
int n;
12

13
long long pow2(int t) {
14
    return (long long)t * t;
15
}
16

17
long long calc(int l, int r) {
18
    if (l == 1 && r == n) return 0;
19
    int mn = 0x3f3f3f3f, mx = -0x3f3f3f3f;
20
    if (l != 1) mn = min(mn, pre_mn[l - 1]), mx = max(mx, pre_mx[l - 1]);
21
    if (r != n) mn = min(mn, pos_mn[r + 1]), mx = max(mx, pos_mx[r + 1]);
22
    return max(pow2(mx - mn), max(pow2(mx), pow2(mn)) + max(pow2(a[l].first), pow2(a[r].first)));
23
}
24

25
bool check(long long mid) {
26
    for (int i = 1, j = 1; i <= n; ++i) {
27
        while (j <= n && (long long)(a[j].first - a[i].first) * (a[j].first - a[i].first) <= mid) {
28
            if (calc(i, j) <= mid) return true;
29
            j++;
30
        }
31
        if (calc(i, j - 1) <= mid) return true;
32
    }
33
    return false;
34
}
35

36
int main() {
37
    scanf("%d", &n);
38
    for (int i = 1; i <= n; ++i) {
39
        scanf("%d%d", &a[i].first, &a[i].second);
40
    }
41
    sort(a + 1, a + n + 1);
42
    pre_mn[0] = 0x3f3f3f3f;
43
    pre_mx[0] = -0x3f3f3f3f;
44
    pos_mn[n + 1] = 0x3f3f3f3f;
45
    pos_mx[n + 1] = -0x3f3f3f3f;
46
    for (int i = 1; i <= n; ++i) {
47
        pre_mx[i] = max(pre_mx[i - 1], a[i].second);
48
        pre_mn[i] = min(pre_mn[i - 1], a[i].second);
49
    }
50
    for (int i = n; i; --i) {
51
        pos_mx[i] = max(pos_mx[i + 1], a[i].second);
52
        pos_mn[i] = min(pos_mn[i + 1], a[i].second);
53
    }
54
    long long l = 0, r = 80000000000000000;
55
    while (l < r) {
56
        long long mid = l + r >> 1;
57
        if (check(mid)) r = mid;
58
        else l = mid + 1;
59
    }
60

61
    long long res = l;
62
    for (int i = 1; i <= n; ++i) swap(a[i].first, a[i].second);
63
    sort(a + 1, a + n + 1);
64
    pre_mn[0] = 0x3f3f3f3f;
65
    pre_mx[0] = -0x3f3f3f3f;
66
    pos_mn[n + 1] = 0x3f3f3f3f;
67
    pos_mx[n + 1] = -0x3f3f3f3f;
68
    for (int i = 1; i <= n; ++i) {
69
        pre_mx[i] = max(pre_mx[i - 1], a[i].second);
70
        pre_mn[i] = min(pre_mn[i - 1], a[i].second);
71
    }
72
    for (int i = n; i; --i) {
73
        pos_mx[i] = max(pos_mx[i + 1], a[i].second);
74
        pos_mn[i] = min(pos_mn[i + 1], a[i].second);
75
    }
76
    l = 0, r = 80000000000000000;
77
    while (l < r) {
78
        long long mid = l + r >> 1;
79
        if (check(mid)) r = mid;
80
        else l = mid + 1;
81
    }
82
    res = min(res, l);
83
    printf("%lld\n", res);
84
    return 0;
85
}

终于补完了，奖励自己歇一晚上😴😴😴

Star's Blog