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

简单题：进制转换

进制转换应该是属于计算机基础题了，把进制转换的过程用代码模拟一遍就行了。

值得注意的是，可以把16进制各个字符对应数值的映射写成一个函数，这样代码可以结构清楚一些。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int res = 0;
	// val函数为16进制的各个字符对应的数值大小
    auto val = [&](char x) {
        if(x >= '0' && x <= '9')
            return x - '0';
        return x - 'A' + 10;
    };
    int len = s.size();
    for(int i=2; i<len; i++) {
        res = res * 16 + val(s[i]);
    }
    cout << res << endl;
}

中等题：合并表记录

这题本质上就是一个运用桶思想的计数问题。

考虑到 0≦xi​≦11111111, 我们需要用一个STL的map来作为桶。

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

int main() {
    int n;
    cin >> n;
    map<int, int> cnt;
    for(int i=1; i<=n; i++) {
        int x, y;
        cin >> x >> y;
        cnt[x] += y;
    }
    for(auto [x, y]: cnt)
        cout << x << " " << y << endl;
}

困难题：称砝码

可以看做一个背包问题的DP模型。

每种物品最多用i次，也可以称之为“多重背包”（模版题：https://ac.nowcoder.com/acm/problem/235950）。

区别于经典背包模型的dp数组记录的是一个最优价值，我们这里的dp数组的意义是能否达到。

如果dp[i] 为 0就组合不出该重量，如果为1就能组合出来。

然后观察题目数据范围，发现最重不会超过2e5，就令N = 2e5作为“背包的最大容量”。

再计算一下时间复杂度，应该是O(N*n*x)，是10的7次方数量级，不会TLE，直接上手写多重背包模版就是了。

对于背包模型不熟悉的小伙伴们，可以先跳转 算法基础精选题 学习一下。（个人感觉对于找工作来说掌握前四种模型就ok了）

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5;
int main() {
    int n;
    cin >> n;
    vector<int> m(n+1), x(n+1);
    for(int i=1; i<=n; i++)
        cin >> m[i];
    for(int i=1; i<=n; i++)
        cin >> x[i];
    vector<int> dp(N+1);
    dp[0] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=x[i]; j++)
        for(int v=N; v>=m[i]; v--) {
            dp[v] |= dp[v-m[i]];
        }
    }
    int res = 0;
    for(int i=0; i<=N; i++)
        res += dp[i];
    cout << res <<endl;
    return 0;
}