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

赛纲介绍

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

题目编号	题目名称	题目难度
T1	皓仔的旗杆	入门
T2	皓仔和水	入门
T3	皓仔选数字	入门
T4	皓仔的数字朋友	入门
T5	皓仔的进制统计	普及-
T6	皓仔的字符串匹配	普及-

T1 皓仔的旗杆

题意简述

本题没有输入。

只需要严格按照题目给出的格式，输出指定的小旗杆图案。

解题思路

直接使用多次 cout 输出对应的星号 * 和空格即可。

参考代码

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

int main() {
    cout << "*****" << endl;
    cout << "*   *" << endl;
    cout << "*****" << endl;
    cout << "*" << endl;
    cout << "*" << endl;
    cout << "*" << endl;
    cout << "*" << endl;

    return 0;
}

T2 皓仔和水

题意简述

给定水的温度 $t$，根据温度判断水当前所处的状态。

共有 $5$ 种情况：

• 当 $t<0$ 时，输出 固体
• 当 $t=0$ 时，输出 固液共存
• 当 $0<t<100$ 时，输出 液体
• 当 $t=100$ 时，输出 液气共存
• 当 $t>100$ 时，输出 气体

解题思路

使用 if、else if 和 else 按照温度范围依次判断即可。

需要特别注意 $0$ 和 $100$ 这两个边界值，它们分别对应 固液共存 和 液气共存。

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

参考代码

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

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

    if(t < 0) {
        cout << "固体" << endl;
    }
    else if(t == 0) {
        cout << "固液共存" << endl;
    }
    else if(t < 100) {
        cout << "液体" << endl;
    }
    else if(t == 100) {
        cout << "液气共存" << endl;
    }
    else {
        cout << "气体" << endl;
    }

    return 0;
}

T3 皓仔选数字

题意简述

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

需要从数组中选择一个数字 $y$，使得 $x\times y$ 的值尽可能大。

输出能够得到的最大乘积。

注意，答案可能是负数。

解题思路

直接枚举数组中的每一个数字 $a_i$，计算 $x\times a_i$，并维护当前最大的乘积即可。

由于 $-2^{31}\leq x,a_i\leq 2^{31}-1$，两个数相乘后可能超过 int 的范围，因此需要使用 long long 存储。

另外，因为所有乘积都有可能是负数，所以不能把答案初始值设为 $0$，可以直接使用第一个乘积初始化答案。

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

参考代码

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

typedef long long ll;

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

    ll ans;

    for(int i = 1; i <= n; i++) {
        ll y;
        cin >> y;

        ll t = x * y;

        if(i == 1) {
            ans = t;
        }
        else {
            ans = max(ans, t);
        }
    }

    cout << ans << endl;

    return 0;
}

T4 皓仔的数字朋友

题意简述

给定一个 $n$ 行 $m$ 列的整数矩阵。

对于每个位置，只考虑它的上、下、左、右四个相邻位置。

如果某个相邻位置中的数字与当前位置相同，那么这个相邻位置就是它的一个好朋友。

要求输出矩阵中每个位置拥有的好朋友数量。

解题思路

直接枚举矩阵中的每一个位置 $(i,j)$。

对于当前位置，分别检查上、下、左、右四个方向：

• 如果相邻位置没有越界；
• 并且相邻位置的数字与当前数字相同；

那么当前格子的好朋友数量加 $1$。

因为每个位置最多只检查 $4$ 个方向，所以总时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。

参考代码

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

int n,m;
int a[1010][1010];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

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

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int cnt=0;

            for(int k=0;k<4;k++){
                int x=i+dx[k];
                int y=j+dy[k];

                if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]==a[i][j]){
                    cnt++;
                }
            }

            cout << cnt << " ";
        }
        cout << endl;
    }

    return 0;
}

T5 皓仔的进制统计

题意简述

给定一个长度为 $n$ 的非负整数数组，以及一个进制 $R$。

需要将数组中的每个数字转换成 $R$ 进制，并统计所有数位中数字 1 一共出现了多少次。

解题思路

对于每一个数字 $x$，可以使用短除法不断取出它在 $R$ 进制下的每一位。

每次计算 x % R，就可以得到当前最低位。

如果这一位等于 $1$，答案加 $1$。

然后令 x /= R，继续处理下一位，直到 $x=0$。

例如十进制数 $10$ 转换成 $3$ 进制：

• $10\bmod 3=1$
• $3\bmod 3=0$
• $1\bmod 3=1$

所以得到 $101$，其中有 $2$ 个数字 1。

需要注意，数字 $0$ 转换成任意进制仍然是 0，其中不会出现数字 1，因此不需要特殊处理。

由于 $a_i\leq 10^{18}$，需要使用 long long 存储。

时间复杂度为 $O(n\log_R A)$，其中 $A$ 表示数组中数字的最大值，空间复杂度为 $O(1)$。

参考代码

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

typedef long long ll;

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

    ll ans=0;

    for(int i=1;i<=n;i++){
        ll x;
        cin >> x;

        while(x){
            if(x%R==1){
                ans++;
            }
            x/=R;
        }
    }

    cout << ans << endl;

    return 0;
}

T6 皓仔的字符串匹配

题意简述

给定 $T$ 组字符串，每组包含两个字符串 $a$ 和 $b$。

对于两个字符串，都需要先进行以下处理：

• 删除所有数字；
• 将剩余字母全部转换成大写字母。

处理完成后，统计字符串 $a$ 在字符串 $b$ 中出现了多少次。

匹配允许重叠。

解题思路

先对两个字符串进行预处理。

对于字符串中的每一个字符：

• 如果字符满足 '0' <= c && c <= '9'，说明它是数字，直接跳过；
• 如果字符满足 'a' <= c && c <= 'z'，说明它是小写字母，可以通过 c -= 32 将其转换成对应的大写字母；
• 如果本身就是大写字母，则直接保留。

处理完成后，枚举字符串 $b$ 中每一个可能的匹配起点。

对于每个起点 $i$，逐个比较后面的字符是否与字符串 $a$ 相同。

如果全部相同，答案加 $1$。

因为每个位置都作为起点进行判断，所以可以正确统计重叠出现的情况。

时间复杂度为 $O(|a|\times|b|)$，空间复杂度为 $O(|a|+|b|)$。

参考代码

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

string change(string s){
    string t="";

    for(char c:s){
        if(c>='0'&&c<='9'){
            continue;
        }

        if(c>='a'&&c<='z'){
            c-=32;
        }

        t+=c;
    }

    return t;
}

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

    while(T--){
        string a,b;
        cin >> a >> b;

        a=change(a);
        b=change(b);

        int ans=0;

        for(int i=0;i+a.size()<=b.size();i++){
            bool ok=true;

            for(int j=0;j<a.size();j++){
                if(a[j]!=b[i+j]){
                    ok=false;
                    break;
                }
            }

            if(ok){
                ans++;
            }
        }

        cout << ans << endl;
    }

    return 0;
}