牛客春招刷题训练营-2025.3.12题解

w 活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 进制转换

手动枚举最高位到最低位。
因为字符串有0x前缀，所以从字符串第 位开始枚举。
使用 isdigit() 判断是否为数字字符。
注意字母字符的特殊处理。

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

int main() {
    string s;
    cin >> s;
    long long x = 0;
    for (int i = 2; i < s.length(); i++) {
        x *= 16;
        if (isdigit(s[i]))x += s[i] - '0';
        else x += s[i] - 'A' + 10;
    }
    cout << x;
    return 0;
}

中等题 合并表记录

开一个map，记录索引及其对应的值。

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

int main() {
    map<int, int> mp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        mp[x] += y;
    }
    for (auto [x, y] : mp)
        cout << x << ' ' << y << '\n';
    return 0;
}

当然也可以开数组，当值不为 时就输出。
这种方法时间复杂度高，并且很多空间没有利用上。

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

int a[11111112];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[x] += y;
    }
    for (int i = 0; i <= 11111111; i++)
        if (a[i] != 0)
            cout << i << ' ' << a[i] << '\n';
    return 0;
}

困难题 称砝码

砝码数量不多，可以用set维护重量。
对于某个重量为 的砝码，都需要遍历一遍set中的元素，假设遍历到 ，并且 不在set中，那 就是新增加的一个重量。
但是我们不能马上把这个数插入set。因为 这个数已经是加完砝码 的，不能重复加，应该暂存起来等待遍历结束后再插入。
这里用vector存储需要插入set中的元素，遍历结束后一并插入set。
最后输出set中有几个元素即可。

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

int main() {
    set<int> st;
    st.insert(0);
    int n;
    cin >> n;
    vector<int> m(n), x(n);
    for (int i = 0; i < n; i++)cin >> m[i];
    for (int i = 0; i < n; i++)cin >> x[i];
    for (int i = 0; i < n; i++) {
        while (x[i]--) {
            vector<int> ins;
            for (auto it : st) {
                if (!st.count(it + m[i])) {
                    ins.push_back(it + m[i]);
                }
            }
            for (auto it : ins) {
                st.insert(it);
            }
        }
    }
    cout << st.size() << '\n';
    return 0;
}