D. For Gamers. By Gamers.

题意

你正在玩一个打怪游戏，游戏共有$m$个回合，在每个回合中，都会获得$C$枚硬币。

同时，你有$n$种随从可以选择，每种随从的数据如下

$c: 每个随从所花费的硬币数$

$d: 随从单位时间内造成的伤害$

$h: 随从的血量$

在每个回合中你都会面临一个怪物，怪物的数据如下

$D: 怪物单位时间内造成的伤害$

$H: 怪物的血量$

每个回合是独立的，回合之间没有继承关系；在每个回合中，你只能选择一种随并召唤；造成伤害是连续的，并不是每个单位时间发动一次伤害

现在给你上述数据，问在每个回合中，你能保证在打死怪物的同时不使自己的任何随从死亡的最少话费硬币数量，如果无论如何都不能做到，输出$-1$

数据范围

$1 \leq n, m \leq 3 \times 10^5$

$1 \leq C, c, d, h, D \leq 10^6$

$1 \leq H \leq 10^{12}$

题解

理论

假设我们在第$j$个回合中，选择第$i$种随从，并召唤$x$个，那么显然我们需要满足

$\frac{H_j}{x \times d_i} < \frac{h_i}{D_j}$

改写成

$x \times h_i \times d_i > H_j \times D_j$

从上式可以看出，在不考虑花费的情况下，对于每种随从和每个怪物，我们只关心他们血量和攻击力的乘积

错解

这是我一开始写的解法，会被hack

不难看出$x = \lfloor \frac{H_j \times D_j}{h_i \times d_i} \rfloor + 1$

那也就是说，对于每个怪物$j$，我们使用第$i$种随从的花费为$c_i \times \lfloor \frac{H_j \times D_j}{h_i \times d_i} \rfloor + c_i$

不那么严谨的，我们去掉下取整的符号，得到一个花费，我们姑且叫他预计花费吧，为$\frac{c_i}{h_i \times d_i} \times H_j \times D_j + c_i$，这里的$H_j \times D_j$是不变的，那么我们就优先选择$\frac{c_i}{h_i \times d_i} + c_i$更小的随从就可以了

但是注意，由于我们得到的预计花费过于不严谨，肯定不能直接取最小的，结合数据范围的话，排好序从前$100$个里面比较一下就可以了

投机取巧，会WA掉，即使再改进一下也会被hack

#include <iostream>
#include <cstdio>
#include <algorithm>

int n, m;
long long t;
struct Units
{
    long long c, d, h;

    bool operator < (Units tmp) const
    {
        double cp1 = (double)c / ((double)d * (double)h) + double(c), cp2 = (double)tmp.c / ((double)tmp.d * (double)tmp.h) + double(tmp.c);

        if(cp1 < cp2)
            return true;
        else if(cp1 > cp2)
            return false;
        else
            return c < tmp.c;
    }
} u[300005];

int main()
{
    scanf("%d%lld", &n, &t);
    for(int i = 1; i <= n; i ++) scanf("%lld%lld%lld", &u[i].c, &u[i].d, &u[i].h);

    std:: sort(u + 1, u + n + 1);

    scanf("%d", &m);
    for(int i = 1; i <= m; i ++)
    {
        long long md, mh;
        scanf("%lld%lld", &md, &mh);

        bool judge = false;
        long long ans = 1e18 + 1;

        for(int j = 1, ed = std:: min(n, 200); j <= ed; j ++)
        {
            long long use = (md * mh) / (u[j].h * u[j].d) + 1;

            if(use * u[j].c <= t)
            {
                judge = true;

                ans = std:: min(ans, use * u[j].c);
            }
        }

        if(judge)
            printf("%lld%c", ans, " \n"[i == m]);
        else
            printf("-1%c", " \n"[i == m]);
    }

    return 0;
}

正解

看一眼数据范围，发现$C$只有$10^6$大小，那我们就可以在$C$上做文章了

正解就是对$C$预处理加二分

对于每一个硬币数$C_i$，我们都可以预处理出最优的$x \times h_i \times d_i$，那么预处理后对于每个怪物$j$，我们二分硬币数量就可以了

真正令我感兴趣的是这里的预处理方法，之前从来没有见过，感性理解应该是基于整除分块的

官方的代码如下

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)

int main(){
	int n, C;
	scanf("%d%d", &n, &C);
	vector<long long> bst(C + 1);
	forn(i, n){
		int c, d, h;
		scanf("%d%d%d", &c, &d, &h);
		bst[c] = max(bst[c], d * 1ll * h);
	}
	for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c)
		bst[xc] = max(bst[xc], bst[c] * (xc / c));
	forn(c, C)
		bst[c + 1] = max(bst[c + 1], bst[c]);
	int m;
	scanf("%d", &m);
	forn(j, m){
		int D;
		long long H;
		scanf("%d%lld", &D, &H);
		int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin();
		if (mn > C) mn = -1;
		printf("%d ", mn);
	}
	puts("");
}

其中的bst[c]就是我之前提到的对于每个硬币数可以得到的最好的属性，这里对bst[c]的更新方法我觉得很巧妙：

第11到第17行的代码更新对于能正好全部拿来买随从的$C_i$的bst，很容易理解

但是第18和第19行的处理，应该就是基于下取整的整除分块性质进行更新，对于只有一个除数而言的话这显然是正确的，但是这个情形中牵扯到多个不同的除数，感性理解下来也是可以的，具体证明我还没有细想，只是觉得很巧妙

回头仔细想明白了可能会回来补这篇题解

Zth's Blog

Educational Codeforces Round 125

D. For Gamers. By Gamers.

题意

数据范围

题解

理论

错解

正解