挖矿！

· · 题解

T1，感觉做法很巧妙啊，不知道是不是正解。

思路

首先背包板子过不了，这个质量范围隔壁小孩吓哭了当然不是我。

再看一眼任意质量间都存在倍数关系，小孩瞬间不哭了。

我们可以将质量从小到大排序再去个重设为 a，由题得 a_{i + 1}=x_ia_i 其中 x 是一个 \ge2 的正整数，于是数组大小是 \log V 级别的，小孩笑了。

当然这个大小的性质并没有卵用，重要的是倍数关系。

我们可以想到一个简单的暴力：枚举每一种质量选取的个数并判断合法性更新答案，发现相同质量肯定可以贪心解决。

在暴力的过程中，发现每选 x_i 个 a_i 质量就等价于选择 1 个 a_{i + 1} 质量，又由上面的贪心启示我们将每 x_i 个没被选中的质量为 a_i 的物品打包为 a_{i+1} 质量，价值为 x_i 个物品价值之和的物品。

背包容量的条件又如何转换呢？发现由上述转换后质量越大可以得到越多贡献，于是我们可以从大到小贪心类似进制转换的得到每个位置至多选择的个数 b_i。

从小到大遍历到第 i 位时就贪心选择前价值最大的 b_i 个物品累加进答案，剩下的物品从按价值大到小依次类上的每 x_i 个打包扔到第 i+1 位即可。

写出来获得了 18pts。

但是有如下 hack：

7 8
9 1
9 1
9 1
9 1
9 1
9 1
7 8

输出为 7，答案肯定是 54 啊。

发现剩下若不足 x_i 个也要打包为一个物品，那么这样质量还等价于 a_{i+1} 吗？答案是肯定的，因为每一个质量只会出现一个这样的物品，选择此后肯定不能多选一个就等价了。

code

#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;
}