官方题解 | 欢乐赛#59 题解

你好

2025-10-27 11:04:18

发布于：浙江

28阅读

0回复

0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	赛跑	入门
T2	撑杆跳	入门
T3	接龙	入门
T4	小明的等腰三角形计数	入门
T5	逃离丛林	普及-
T6	超级拼装	普及-

T1 赛跑

题目大意

小明和他的朋友皓仔正在长度为 $n$ 的环形的操场跑道上赛跑，小明的跑步速度 $a$ 米每秒，皓仔的速度维持在 $b$ 米每秒 $(b > a)$ ，

皓仔现在在小明前方 $c$ 米处，问需要几秒钟他才可以再超过小明一次从而领先小明一整圈？

题解思路

现在已经领先了 $c$ 米，那还需要再跑出 $n - c$ 米的差距可以实现套圈。皓仔的速度比小明快，因此每秒可以多跑 $b - a$ 米，那么想要套圈所需的时间就是 $(n - c) / (b - a)$ 。（答案向上取整）

参考代码

#include <iostream>
using namespace std;
int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    n -= c;
    int d = b - a;
    cout << (n + d - 1) / d << endl; // 实现向上取整
}

T2 撑杆跳

题目大意

对于所有可以支撑小明体重的撑杆，寻找长度最大的并且输出。

题解思路

只需要遍历所有的撑杆，判断一下该撑杆能接受的体重是否大于等于小明的体重，可以的话更新一下撑杆长度的最大值。

参考代码

#include <iostream>
using namespace std;
int w[1000010], h[1000010];
int main() {
    int n, a, ans = 0;
    cin >> n >> a;
    for(int i = 1; i <= n; i++) cin >> w[i];
        for(int i  = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) {
        if(w[i] >= a) ans = max(ans, h[i]);
    }
    cout << ans << endl;
}

T3 接龙

题目大意

给定两个字符串 $s_1, s_2$ , 如果 $s_1$ 的最后一个字符, 恰好为 $s_2$ 的第一个字符的话，那么我们称 $s_1$ 和 $s_2$ 可以进行接龙。

尝试将第 $2$ 到第 $n$ 个字符串接龙到第 $1$ 个串后面，如果可以的话就进行接龙，不可以的话就舍弃掉。请问经过所有的接龙尝试后，最终第一个字符串是什么样子的？

题解思路

从第 $2$ 个串开始，每次将第一个字符和第一个串的末尾字符作对比，如果能符合的话就进行接龙拼接，最后输出第一个字符串即可。

参考代码

#include <iostream>
using namespace std;
int w[1000010], h[100010];
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i = 2; i <= n; i++) {
        string x;
        cin >> x;
        if(x[0] == s.back()) { //当前串的第一个字符 和第一个串的最后一个字符相等
            for(int j = 1; j < x.size(); j++) s += x[j];
        }
    }
    cout << s << endl;
}

T4 小明的等腰三角形计数

题目大意

给定 $n$ 个数字，请问在所有的三元组 ${i, j , k}$ 里 $(1\le i < j < k \le n)$ , 一共有多少种选择可以拼出一个等腰三角形。

题解思路

等腰三角形需要满足两个条件：

1：是一个三角形

2：存在两条边相等

因此本题可以三重循环枚举所有的三元组 $i, j, k$ ，然后判断对应的三条边是否可以组成一个等腰三角形

参考代码

#include <iostream>
using namespace std;
int len[1010];
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> len[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) 
        for(int j = i + 1; j <= n; j++)
            for(int k = j + 1; k <= n; k++) {
                int a = len[i], b = len[j], c = len[k];
                if(a + b > c && b + c > a && a + c > b && (a == b || a == c || b == c)) ans++;
            }
    
    cout << ans << endl;
}

T5 逃离丛林

题目大意

在一个二维矩阵里，每走到一个点上就可以获得对应的灵力值。矩阵是循环的，也就是第 $n$ 行再往下走就到了第一行，第 $m$ 列往右走就到了第一列。现在从 $(x, y)$ 出发向右一直走或者向下一直走，问走几步之后积攒的灵气值可以大于等于 $k$ 。

题解思路

注意到 $k \le 10^{18}$ ，也就是当 $k$ 的值足够大的情况下，暴力的模拟运算会超时。

因此可以统计一下第 $x$ 行的灵气总数，第 $y$ 列的灵气总数。

当我们尝试出发向右一直走的情况下，那么可以直接做除法操作得到我们会在第 $x$ 行完整的走几圈，剩余的灵气值直接模拟求还需要几步就好。

出发向下一直走的情况同样是做除法操作，得到我们会在第 $$ 列完整的走几圈，剩余的部分直接模拟求解。

参考代码

#include <iostream>
using namespace std;
int a[1010][1010];
long long n, m, x, y, k;
long long row[1010], col[1010];
int main() {
    cin >> n >> m >> x >> y >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
    //向右走
    long long rounds = k / row[x]; //计算圈数
    long long kk = k % row[x]; // 剩余的量
    long long cnt = 0, xx = x, yy = y;
    while(kk > 0) { //不断向右走直到凑齐kk灵力值
        yy++;
        if(yy > m) yy = 1;
        kk -= a[xx][yy];
        cnt++;
    }
    cout << rounds * m + cnt<< ' ';
    rounds = k / col[y];
    kk = k % col[y];
    cnt = 0, xx = x, yy = y;
    while(kk > 0) {
        xx++;
        if(xx > n) xx = 1;
        kk -= a[xx][yy];
        cnt++;
    }
    cout << rounds * n + cnt;
}

T6 小明的字符串排序

题目大意

小明把他的积木仓库是一个 $n \times n$ 的网格，他计划从中抓一把。小明可以选择一个点 $(x, y)$ 并且获得和该点的曼哈顿距离在 $D$ 以内的所有零件。

当前的机器人模型需要的零件一共有 $m$ 种，编号从 $1$ 到 $m$ ，各需要一个。编号为 $0$ 的零件是万能零件，可以替代任何一种零件。

现在小明希望抓一把零件之后可以拼出最多的机器人。

题解思路

本题中我们可以先枚举所有的点，并且把该点抓一把之后能够拼出的机器人数量计算出来。

我们遍历整个二维数组，然后对于当前的点 $(i, j)$ ，直接遍历所有点，并且记录下曼哈顿距离在 $D$ 以内的所有的零件种类出现次数。

而后求解一下最大可以拼装的机器人个数

此时我们可以直接从小到大枚举机器人的个数，假设当前的个数为 $t$ , 那么计算一下各种材料的数量缺口，如果缺口的总和数量小于等于万能零件的个数，说明可以拼出 $t$ 个机器人，如果不行的话，那么我们可以得到的最大的机器人数量就是 $t - 1$ ;

最后我们知道了每个店可以拼装的机器人最大个数，遍历找到最大值并且输出对应的个数和坐标即可。

参考代码

#include <iostream>
using namespace std;
int cnt[15];
int a[55][55];
int ans[55][55];
int main() {
    int n, m, d;
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) cin >> a[i][j];
  
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            for(int t = 0; t <= m; t++) cnt[t] = 0;
            for(int t = 1; t <= n; t++)
                for(int k = 1; k <= n; k++) {
                    if(abs(t - i) + abs(k - j) <= d && a[t][k] <= m) cnt[a[t][k]]++;
                }
            //  对于cnt数组  计算下最多可以拼几套
            int num = 0;
            for(int t = 1; ; t++) { //假设t套  看能否完成
                int need = 0; //看需要几个万能零件
                for(int k = 1; k <= m; k++) need += max(0, t - cnt[k]);
                if(need > cnt[0]) {
                    num = t - 1;
                    break;
                }
            }
            ans[i][j] = num;

        }
   
    int ma = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) ma = max(ma, ans[i][j]);
    int Cnt = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) if(ans[i][j] == ma) Cnt++;
        cout << Cnt << endl;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) if(ans[i][j] == ma) cout << i << ' ' << j << endl;


}