官方题解 | 欢乐赛#49

你好

2025-06-14 18:05:10

发布于：浙江

201阅读

0回复

0点赞

官方题解 | 欢乐赛#49

赛纲介绍

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

题目编号	题目名称	题目难度
T1	除法	入门
T2	买凤梨	入门
T3	去重	入门
T4	幸运数	入门
T5	菠萝排名	入门
T6	矩阵旋转	普及-

T1 除法

题目大意

给定一个正整数 $n$ ，请输出 $n$ 除以 $2$ 向上取整的结果。

题解思路

想要求一个数字 $x$ 除 $2$ 上取整的结果，即是求 $(x + 1) / 2$ 的结果。

参考代码

#include <iostream>

using namespace std;
int main() {
  int n;
  cin >> n;
  cout << (n + 1) / 2;
}

T2 买凤梨

题目大意

一共有 $n$ 种凤梨，每种有美味度 $k$ 和价格 $p$ 。

小明现在有 $R$ 元钱，他会选择其中一种凤梨并且把身上的钱都拿去买该品种的凤梨。求这个条件下他能获得的最多的美味度总和。

题解思路

对于一种价格为 $p$ 的凤梨，最多可以买 $R / p$ 个，因此美味度总和为 $R / p * k$ 。

直接遍历每一个凤梨品种，求出其中最大的美味度总和即可。

参考代码

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


int main(){
    int n, R;
    cin >> n >> R;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int k, p;
        cin >> k >> p;
        ans = max(ans, R / p * k); 
    }
    cout << ans << endl;

}

T3 去重

题目大意

给定 $n$ 个数字，对于每个数字,只有第一次出现时候，对其输出一次。

题解思路

循环嵌套

注意到数据范围只有5000，本题可以不借助桶数组和哈希表等工具，直接使用复杂度为 $O(n^2)$ 的暴力解通过。

具体思路为：对于第 $i$ 个数字，遍历前面所有的数字，如果有出现相同的数字则不用再输出了。否则说明这是该数字第一次出现，直接输出即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
int a[5010], n;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) {
		bool flag = true; //默认这是第一次出现
		for(int j = 1; j < i; j++) {
			if(a[j] == a[i]) flag = false; //非第一次出现则不再输出 
		} 
		if(flag) cout << a[i] << ' '; 
	}  
}

T4 幸运数

题目大意

对于一个数字 $x$ 而言如果在 $[x, x + m]$ 范围内，存在一个数字他的数位和是 $t$ 的倍数，那么我们认为它是一个幸运数。

求在 $1$ 到 $n$ 里面幸运数的个数。

题解思路

按照题目要求将数字 $i$ 从 $1$ 遍历到 $n$ ，在 $[i, i + m]$ 中只要出现一个数字的数位和为 $t$ 的倍数，则数字 $i$ 为一个幸运数，最终计算幸运数的总数。

数位和的计算方式：使用 $while$ 循环每次 $\%10$ 获取最低位的数值，再 $/10$ 删去最低位。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, t;
bool check(int x) {

    for(int i = x; i <= x + m; i++) {
        int sum = 0;
        int b = i;
        while(b) {
            sum += b % 10;
            b /= 10;
        }
        if(sum % t == 0) return true;
    }
    return false; //以上所有数字全都不符合要求 则返回false


}
int main() {
    cin >> n >> m >> t;
    int ans = 0;
    for(int i = 1; i <= n; i++) ans += check(i);
    cout << ans << endl;

}

T5 菠萝排名

题目大意

给定 $n$ 个菠萝品种，编号从 $1$ 到 $n$ 。对于每一种菠萝都有一个甜度和酸度指标 $x$ 和 $y$ 。

需要对菠萝进行排名，排名规则为按照甜度从大到小排名，甜度一样的品种，按照酸度从小到大排名，对于甜度和酸度都一样的菠萝，按照编号从小到大排名。

只有甜度大于等于 $a$ 并且酸度小于等于 $b$ 的菠萝，才有资格参与排名，求最后的排名名单。

题解思路

本题每个菠萝有三个信息：甜度酸度编号。因此直接考虑使用结构体排序来给菠萝进行排名 (按照题目给定的规则：先按照甜度排序，再按照酸度排序，再按照编号排序)

由于只有甜度和酸度符合要求的菠萝才能参加排名，因此在按照排名从高到低输出的过程中，跳过没资格参与排名的菠萝品种即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
struct node{
    int x, y;
    int id;
    bool operator < (const node & w) { //重载操作符进行结构体排序， 也可以手写cmp函数
        if(x != w.x) return x > w.x;
        if(y != w.y) return y < w.y;
        return id < w.id;
    }
}a[1000010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, A, B;
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) {
        if(a[i].x >= A && a[i].y <= B) cout << a[i].id << ' '; //只有符合条件的菠萝品种才能输出
    }
}

T6 矩阵旋转

题目大意

对于给定的一个 $n \times n$ 的二维矩阵，请输出二维矩阵最外围一圈顺时针旋转 $90$ 度的结果。

最外围一圈即：第 $1$ 行或第 $n$ 行或第 $1$ 列或第 $n$ 列。

题解思路

可以手动寻找一下旋转 $90$ 度之前和之后点的坐标关系：旋转之后的 $a[i][j]$ ，他的原数值存在于原先的 $a[n + 1 - j][i]$ 这个位置。

因此可以按照这个规律，对于二维矩阵最外面一圈的数字直接输出旋转前所在位置的数字。对于不在最外面一圈的数字，直接输出即可。

参考代码

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

int n;
int a[1010][1010];
int main()
{
    cin >> n;
    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++) {
            if(i == 1 || j == 1 || i == n || j == n) { //判断是否在最外围一圈
                cout << a[n + 1 - j][i] <<' ';
            }
            else cout << a[i][j] << ' ';
        }
        cout << endl;
    }
       
}