专栏文章

挖矿！

mmk14_61
P12966题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min4y0vk
此快照首次捕获于
2025/12/01 20:38
3 个月前
此快照最后确认于
2025/12/01 20:38
3 个月前
查看原文
T1，感觉做法很巧妙啊，不知道是不是正解。

思路

首先背包板子过不了，这个质量范围隔壁小孩吓哭了当然不是我。
再看一眼任意质量间都存在倍数关系，小孩瞬间不哭了。
我们可以将质量从小到大排序再去个重设为 aa，由题得 ai+1=xiaia_{i + 1}=x_ia_i 其中 xx 是一个 ≥2\ge2 的正整数，于是数组大小是 log⁡V\log V 级别的，小孩笑了。
当然这个大小的性质并没有卵用，重要的是倍数关系。
我们可以想到一个简单的暴力：枚举每一种质量选取的个数并判断合法性更新答案，发现相同质量肯定可以贪心解决。
在暴力的过程中，发现每选 xix_i 个 aia_i 质量就等价于选择 11 个 ai+1a_{i + 1} 质量，又由上面的贪心启示我们将每 xix_i 个没被选中的质量为 aia_i 的物品打包为 ai+1a_{i+1} 质量，价值为 xix_i 个物品价值之和的物品。
背包容量的条件又如何转换呢？发现由上述转换后质量越大可以得到越多贡献，于是我们可以从大到小贪心类似进制转换的得到每个位置至多选择的个数 bib_i。
从小到大遍历到第 ii 位时就贪心选择前价值最大的 bib_i 个物品累加进答案，剩下的物品从按价值大到小依次类上的每 xix_i 个打包扔到第 i+1i+1 位即可。
写出来获得了 18pts。
但是有如下 hack：
CPP
7 8
9 1
9 1
9 1
9 1
9 1
9 1
7 8
输出为 77，答案肯定是 5454 啊。
发现剩下若不足 xix_i 个也要打包为一个物品，那么这样质量还等价于 ai+1a_{i+1} 吗？答案是肯定的，因为每一个质量只会出现一个这样的物品，选择此后肯定不能多选一个就等价了。

code

C
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 7;
int n, m, cnt, ans;
int tmp[N], o[N];
map<int, int> mp;
vector<int> w[41];//w[i]表示质量为tmp[i]的物品价值
struct node{
	int w, v;
}b[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> b[i].w >> b[i].v;
		if (!mp[b[i].v])
			mp[b[i].v] = 1, tmp[++ cnt] = b[i].v;
	}
	sort(tmp + 1, tmp + cnt + 1);
	for (int i = 1; i <= cnt; i ++)//离散化并去重
		mp[tmp[i]] = i;
	for (int i = cnt; i >= 1; i --) {
		o[i] = m / tmp[i];
		m -= m / tmp[i] * tmp[i];
	}
	for (int i = 1; i <= n; i ++)
		w[mp[b[i].v]].push_back(b[i].w);
	for (int i = 1; i <= cnt; i ++) {
		sort(w[i].begin(), w[i].end(), greater<int>());//从大往小排贪心
		int k = 0, sum = 0;
		for (int j : w[i]) {
			if (o[i])
				o[i] --, ans += j;
			else {
				k ++, sum += j;
				if (k == tmp[i + 1] / tmp[i]) {//题解中的x就是tmp[i + 1]/tmp[i]
					w[i + 1].push_back(sum);
					sum = k = 0;
				}
			}
		}
		if (k)//剩下的也要打包，没有这句话就是18pts了
			w[i + 1].push_back(sum);
	}
	cout << ans;
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...