牛客春招刷题训练营-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;
}
