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

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

Easy 进制转换

简要题意

给定一个十六进制正数，将其转为十进制，保证数字在 int 范围内。

Solution

前两位的 0x 就不管它了，从第三位开始考虑。

每新添加一位数，数值相当于先前的数值乘上 ，再加上现在这位数，模拟这个过程就好。

Code

void R()
{
	string s;
	int x=0;
	cin>>s;
	for (int i=2;i<s.size();i++)
	{
		int p;
		if (s[i]>='A'&&s[i]<='F')
			p=10+(s[i]-'A');
		else p=s[i]-'0';
		x=x*16+p;
	}
	cout<<x;
	return;
}

Medium 合并表记录

简要题意

假定有一个初值为 的数组 （长度为 级别）。

给定 条指令 x y，表示让 加上 （其中 ）。

对每个 ，按 的顺序输出 。

Solution

注意到下标域的规模较大，但是操作次数较小。我们可以用 map 或者 unordered_map 维护这个“数组”。

而迭代器遍历 map 是有序的，遍历 unordered_map 是乱序的（因为其原理是 Hash），我们直接用 map 维护操作，之后迭代器遍历 map 输出答案即可。

Code

void R()
{
	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;
}

Hard 称砝码

简要题意

给定 种砝码，每种砝码有 个，重量为 。

求这些砝码能表示的不同的重量数。

其中， 。

Solution

经典的背包问题。

注意到砝码总重不超过 ，直接维护一下当前哪些重量可以表示，依次考虑每个砝码。

考虑重量为 的砝码，如果考虑这个砝码前 可以表示，则考虑这个砝码后 可以表示。

注意这里的 要倒序枚举，避免一个砝码被重复使用多次。

Code

void R()
{
	constexpr int MAXN=2e5+7;
	int n,ans=0;
	cin>>n;
	vector<int> m(n),x(n),dp(MAXN);
	dp[0]=1;
	for (int &t:m) cin>>t;
	for (int &t:x) cin>>t;
	for (int i=0;i<n;i++)
		for (int j=0;j<x[i];j++)
			for (int k=MAXN-1;k>=m[i];k--)
				dp[k]|=dp[k-m[i]];
	for (int i=0;i<MAXN;i++)
		ans+=dp[i];
	cout<<ans<<'\n';
	return;
}