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

你好

2026-08-10 11:30:39

发布于：浙江

86阅读

0回复

0点赞

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

赛纲介绍

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

题目编号	题目名称	题目难度
T1	皓仔的商场折扣	入门
T2	皓仔的周末活动	入门
T3	皓仔的极差筛选	入门
T4	皓仔的数字统计	入门
T5	皓仔的质数公约数	普及-
T6	皓仔的回文子串	普及-

T1 皓仔的商场折扣

题意简述

已知三件物品的价格分别为 $a$ 元、 $b$ 元、 $c$ 元，商场本次活动的折扣为 $d$ 折。

先计算三件物品的总价，再按照折扣计算最终需要支付的金额，并将结果保留 $2$ 位小数。

解题思路

三件物品的原价总和为：

$(a+b+c)$

$d$ 折表示按照原价的 $\dfrac{d}{10}$ 支付，因此最终需要支付的金额为：

$(a+b+c)\times\dfrac{d}{10}$

由于价格和折扣都可能包含小数，因此使用 double 类型存储。

最后使用 printf("%.2f", ans) 将答案保留 $2$ 位小数输出。

时间复杂度为 $O(1)$ ，空间复杂度为 $O(1)$ 。

参考代码

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

int main() {
    double a, b, c, d;
    cin >> a >> b >> c >> d;

    double ans = (a + b + c) * d / 10;

    printf("%.2f\n", ans);

    return 0;
}

T2 皓仔的周末活动

题意简述

皓仔需要在电影、篮球和阅读三个活动中选择一个。

每个活动的总时间等于交通时间加上活动时间。

分别计算三个活动的总时间，并输出其中最小的一个。

解题思路

三个活动的总时间分别为：

$a+b$

$c+d$

$e+f$

只需要分别计算这三个结果，再使用 min 求出最小值即可。

时间复杂度为 $O(1)$ ，空间复杂度为 $O(1)$ 。

参考代码

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

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b;
    cin >> c >> d;
    cin >> e >> f;

    int ans = min(a + b, min(c + d, e + f));

    cout << ans << endl;

    return 0;
}

T3 皓仔的极差筛选

题意简述

给定一个长度为 $n$ 的整数数组。

数组的极差定义为：

$\max(a)-\min(a)$

先求出数组的极差，然后按照原输入顺序输出所有严格小于极差的元素。

如果不存在满足条件的元素，则输出 -1。

解题思路

先遍历一遍数组，求出其中的最大值和最小值。

设极差为：

$range=maxn-minn$

然后再次按照原顺序遍历数组：

如果 a[i] < range，就输出该元素；
使用一个标记变量判断是否至少输出过一个元素。

如果最终一个满足条件的元素都没有找到，则输出 -1。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

参考代码

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

int a[100010];

int main() {
    int n;
    cin >> n;

    int maxn = -1;
    int minn = 1e9;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        maxn = max(maxn, a[i]);
        minn = min(minn, a[i]);
    }

    int range = maxn - minn;
    bool flag = false;

    for(int i = 1; i <= n; i++) {
        if(a[i] < range) {
            if(flag) {
                cout << " ";
            }
            cout << a[i];
            flag = true;
        }
    }

    if(!flag) {
        cout << -1;
    }

    cout << endl;

    return 0;
}

T4 皓仔的数字统计

题意简述

给定一个 $n$ 行 $m$ 列的二维整数数组。

对于每一个出现过的数字 $x$ ，如果它一共出现了 $c$ 次，那么它的统计结果为：

$x\times c$

求所有出现过的数字中，最大的统计结果。

解题思路

由于数组中的数字范围为 $0\sim1000$ ，可以直接使用数组 cnt 统计每个数字出现的次数。

读入每个元素 x 时：

执行 cnt[x]++，记录它的出现次数。

全部读入完成后，枚举 $0\sim1000$ 中的每个数字 $x$ ，计算：

$x\times cnt[x]$

并维护其中的最大值即可。

时间复杂度为 $O(nm+1000)$ ，空间复杂度为 $O(1000)$ 。

参考代码

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

int cnt[1010];

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
    }

    int ans = 0;

    for(int i = 0; i <= 1000; i++) {
        ans = max(ans, i * cnt[i]);
    }

    cout << ans << endl;

    return 0;
}

T5 皓仔的质数公约数

题意简述

给定 $n$ 个整数，需要找到一个最大的质数 $p$ ，使得这 $n$ 个整数都能被 $p$ 整除。

如果不存在这样的质数，则输出 -1。

解题思路

如果一个质数能够同时整除所有数字，那么它一定也是所有数字最大公约数的质因数。

因此可以先求出所有数字的最大公约数：

$g=\gcd(a_1,a_2,\ldots,a_n)$

然后对 $g$ 进行质因数分解。

从 $2$ 开始枚举因数，如果发现 $i$ 能整除 $g$ ，说明 $i$ 是一个质因数，将答案更新为 $i$ ，并不断除去这个质因数。

最后如果剩下的 $g>1$ ，说明剩余的 $g$ 本身也是一个质数，需要继续更新答案。

如果最终没有找到任何质因数，说明所有数字的最大公约数为 $1$ ，不存在质数公约数，输出 -1。

时间复杂度为 $O(n+\sqrt{g})$ ，空间复杂度为 $O(1)$ 。

参考代码

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

int main() {
    int n;
    cin >> n;

    int g = 0;

    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        g = __gcd(g, x);
    }

    int ans = -1;

    for(int i = 2; i * i <= g; i++) {
        if(g % i == 0) {
            ans = i;

            while(g % i == 0) {
                g /= i;
            }
        }
    }

    if(g > 1) {
        ans = g;
    }

    cout << ans << endl;

    return 0;
}

T6 皓仔的回文子串

题意简述

给定一个长度为 $n$ 的字符串 $s$ 。

对于每一个非空连续子串，可以修改其中至多 $k$ 个字符，使其变成回文串。

求一共有多少个子串满足条件。

解题思路

对于一个子串 $s[l\ldots r]$ ，想要将它变成回文串，只需要比较首尾对应位置的字符。

如果：

$s[l]=s[r]$

那么这一对字符不需要修改。

如果：

$s[l]\neq s[r]$

只需要修改其中一个字符，就可以让这一对字符相同，因此需要增加 $1$ 次修改。

设 dp[l][r] 表示子串 $s[l\ldots r]$ 变成回文串最少需要修改多少个字符。

则有：

$dp[l][r]=dp[l+1][r-1]+[s[l]\neq s[r]]$

其中，当 $l\geq r$ 时，子串长度不超过 $1$ ，本身就是回文串，需要修改 $0$ 次。

按照子串长度从小到大计算所有状态。每得到一个 dp[l][r]，如果：

$dp[l][r]\leq k$

说明这个子串可以在至多 $k$ 次修改后变成回文串，将答案加 $1$ 。

字符串长度最大只有 $200$ ，因此使用区间 DP 可以轻松通过。

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n^2)$ 。

参考代码

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

int dp[210][210];

int main() {
    string s;
    int k;

    cin >> s;
    cin >> k;

    int n = s.size();
    s = " " + s;

    long long ans = 0;

    for(int len = 1; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            if(len == 1) {
                dp[l][r] = 0;
            }
            else if(len == 2) {
                dp[l][r] = (s[l] != s[r]);
            }
            else {
                dp[l][r] = dp[l + 1][r - 1] + (s[l] != s[r]);
            }

            if(dp[l][r] <= k) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}