非官方全题解|欢乐赛#49

Rachelzhang ♥

2025-06-08 22:18:44

发布于：北京

35阅读

0回复

0点赞

😊 感谢出题人你好精心准备的题目！废话不多说，让我们开始吧~

1. 除法 🍳

题目描述
给定正整数n，输出n除以2后向上取整的结果

解题思路
使用数学公式(n + 1) / 2实现高效计算：
当n为奇数时，如5→(5+1)/2=3
当n为偶数时，如12→(12+1)/2=6（实际等于6.5但整数除法取整为6）
该方法避免了条件判断，直接计算得到向上取整结果

代码实现

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 使用向上取整公式：(n+1)/2
    cout << (n + 1) / 2 << endl;
    return 0;
}

2. 买凤梨 🍍

题目描述
有R元钱买菠萝，每个菠萝有美味度k和价格p，求最大美味值总和

解题思路
预处理优化：对每种价格只保留最大美味度的菠萝
枚举计算：遍历1~100的价格区间
公式应用：美味值总和 = 最大美味度 × ⌊R/p⌋
时间复杂度O(100)，高效解决数据规模10⁶

代码实现

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // IO优化
    int n, R;
    cin >> n >> R;
    int best[101] = {0}; // 价格索引数组
    
    // 记录每种价格的最高美味度
    for (int i = 0; i < n; i++) {
        int k, p;
        cin >> k >> p;
        if (k > best[p]) best[p] = k;
    }
    
    long long max_total = 0;
    // 计算每种菠萝的最大美味值
    for (int p = 1; p <= 100; p++) {
        if (p > R) continue; // 跳过超出预算的价格
        long long total = (long long)best[p] * (R / p);
        if (total > max_total) max_total = total;
    }
    cout << max_total << endl;
    return 0;
}

3. 去重 🚫

题目描述
按输入顺序输出第一次出现的数字

解题思路
哈希标记：使用布尔数组记录数字首次出现
顺序扫描：遍历时遇到未标记数字立即输出
格式控制：动态管理空格分隔符
时间复杂度O(n)，空间复杂度O(10⁶)，完美匹配数据规模

代码实现

#include <iostream>
#include <vector>
using namespace std;

const int MAX_NUM = 1000001; // 10⁶+1

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<bool> visited(MAX_NUM, false); // 标记数组
    
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
    
    // 遍历输出首次出现的数字
    bool first = true;
    for (int num : arr) {
        if (!visited[num]) {
            visited[num] = true; // 标记已出现
            if (!first) cout << " ";
            cout << num;
            first = false;
        }
    }
    return 0;
}

4. 幸运数 🍀

题目描述
在区间[x,x+m]中是否存在数位和是t倍数的数？统计幸运数数量

解题思路
预处理优化：提前计算1~n+m所有数的数位和
滑动窗口：维护窗口[x,x+m]中满足条件的计数
动态更新：移动窗口时增删端点计数
时间复杂度O(n+m)，避免暴力检查节省时间

代码实现

#include <iostream>
using namespace std;

const int MAX = 100010 + 105; // n+m的最大值
int digitSum[MAX];
bool valid[MAX]; // 标记数位和是t的倍数

int main() {
    int n, m, t;
    cin >> n >> m >> t;
    
    // 预处理数位和
    for (int i = 1; i <= n+m; i++) {
        int sum = 0, num = i;
        while (num) {
            sum += num % 10;
            num /= 10;
        }
        valid[i] = (sum % t == 0);
    }
    
    // 初始化滑动窗口[1, m+1]
    int count = 0;
    for (int i = 1; i <= m+1; i++) 
        if (valid[i]) count++;
    
    // 滑动窗口判断幸运数
    int ans = 0;
    for (int x = 1; x <= n; x++) {
        if (count > 0) ans++; // 存在符合条件的数
        if (valid[x]) count--; // 移除左边界
        if (x+m+1 <= n+m && valid[x+m+1]) 
            count++; // 加入右边界
    }
    
    cout << ans << endl;
    return 0;
}

5. 菠萝排名 🥇

题目描述
筛选出甜度≥a且酸度≤b的菠萝，排序输出编号

解题思路
条件筛选：选择符合阈值条件的菠萝
三级排序：
主排序：甜度降序（高甜度在前）
次排序：酸度升序（低酸度在前）
终排序：编号升序（小编号在前）
稳定排序：使用lambda表达式确保排序稳定性

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Pineapple { int id, x, y; };

int main() {
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    vector<Pineapple> vec;
    
    // 筛选符合条件的菠萝
    for (int id = 1; id <= n; id++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x >= a && y <= b)
            vec.push_back({id, x, y});
    }
    
    // 三级排序
    sort(vec.begin(), vec.end(), [](auto& a, auto& b) {
        if (a.x != b.x) return a.x > b.x; // 甜度降序
        if (a.y != b.y) return a.y < b.y; // 酸度升序
        return a.id < b.id;               // 编号升序
    });
    
    // 输出排名结果
    for (int i = 0; i < vec.size(); i++) {
        if (i) printf(" ");
        printf("%d", vec[i].id);
    }
    return 0;
}

6. 矩阵旋转 🌀

题目描述
将矩阵最外层元素顺时针旋转90度

解题思路
元素提取：按上→右→下→左顺序提取外圈元素
循环移位：整体右移n-1位实现90°旋转
原位放回：按原顺序放回旋转后的元素
内层元素保持不变，仅处理外圈，节省计算资源

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<vector<int>> mat(n, vector<int>(n));
    
    // 读取矩阵
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &mat[i][j]);
    
    if (n == 1) {
        printf("%d\n", mat[0][0]);
        return 0;
    }
    
    // 提取外圈元素
    int cnt = 4*(n-1); // 外圈元素总数
    vector<int> temp(cnt), rotated(cnt);
    int idx = 0;
    
    for (int j = 0; j < n; j++) temp[idx++] = mat[0][j];        // 上边
    for (int i = 1; i < n-1; i++) temp[idx++] = mat[i][n-1];   // 右边
    for (int j = n-1; j >= 0; j--) temp[idx++] = mat[n-1][j]; // 下边
    for (int i = n-2; i >= 1; i--) temp[idx++] = mat[i][0];    // 左边
    
    // 循环右移n-1位（等价90°旋转）
    for (int i = 0; i < cnt; i++)
        rotated[(i + n - 1) % cnt] = temp[i];
    
    // 放回旋转后元素
    idx = 0;
    for (int j = 0; j < n; j++) mat[0][j] = rotated[idx++];      // 上边
    for (int i = 1; i < n-1; i++) mat[i][n-1] = rotated[idx++]; // 右边
    for (int j = n-1; j >= 0; j--) mat[n-1][j] = rotated[idx++]; // 下边
    for (int i = n-2; i >= 1; i--) mat[i][0] = rotated[idx++];   // 左边
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j) printf(" ");
            printf("%d", mat[i][j]);
        }
        printf("\n");
    }
    return 0;
}

🎉 刷题完毕！大家明白了吗？
如果对任何题解有疑问，欢迎在评论区留言交流~
（所有代码都经过严格测试，确保正确性！）

💡 提示：每个解法都针对题目特点进行优化
🚀 代码均满足时间和空间复杂度要求
👍 原创题解不易，欢迎点赞支持！

PS：@AC君写题解不容易，给个周边吧！求求了！

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论