专栏文章

题解：CF2023D Many Games

PPengzt
CF2023D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqj3axk
此快照首次捕获于
2025/12/04 05:37
3 个月前
此快照最后确认于
2025/12/04 05:37
3 个月前
查看原文

Many Games

题目链接。cnblogs。

Problem

给你 nn 个物品，每个物品有一个概率 pip_i 和权值 wiw_i。如果选中某个物品 ii，那么有 pi% (1≤pi≤100)p_i\%~(1\le p_i\le 100) 的概率中奖并获得 wiw_i， 然后假设你选了一个集合 SS，当且仅当集合内的物品都中奖了，才能获得集合内的 ∑i∈Swi\displaystyle\sum_{i\in S} w_i。定义一个集合的价值 f(S)f(S) 为
∀i∈S,(∏ipi100)⋅(∑iwi)\forall i\in S, \Big(\prod_i\frac{p_i}{100}\Big)\cdot\Big(\sum_{i}w_i\Big)
求 f(S)f(S) 的最大值。
数据范围：1≤n≤2×1051 \le n \le 2 \times 10^5，1≤wi,pi⋅wi≤2×1051 \le w_i, p_i\cdot w_i \le 2 \times 10^5。

Sol

首先 pi=100p_i = 100 的点是一定会选的。然后如果 pip_i 相同的话，我一定是从大到小的选择 wiw_i。然后感觉一下，如果 wiw_i 相差不大的话，概率越小的数选的个数也会越少，不然一定不优。考虑具体的分析一下这个东西。不妨令当前的物品的概率为 pp（此时 p∈(0,1)p \in (0, 1)），物品的价值为 wmax100p\large\frac{w_{max}}{100p}（更小肯定更劣），集合中暂时没有数（有数的话影响会更大，因为它会使之前的值变小）。设这类物品选了 xx 个，则 ff 为 px⋅x⋅wmax⁡100p=px−1xwmax⁡100p^x \cdot x \cdot \frac{w_{\max}}{100p} = p^{x - 1}x\frac{w_{\max}}{100}。于是这个东西就只和 px−1xp^{x - 1}x 有关。不妨令 g(x)=px−1xg(x) = p^{x - 1}x，则 g′(x)=px−1ln⁡(p)x+px−1g'(x) = p^{x - 1}\ln(p)x + p^{x - 1}。当 px−1+xpx−1ln⁡p=0p^{x - 1} + xp^{x - 1} \ln p = 0 时 g(x)g(x) 有最大值。px−1=−px−1×xln⁡pp^{x - 1} = -p^{x - 1}\times x\ln p。xln⁡p=−1x \ln p = -1 时有最小值。则 x=1ln⁡1px = \frac{1}{\ln \frac{1}{p}}。当 p=0.99p = 0.99 时有最大值 100100。最后直接把每个 pp 对应的元素全部拉出来跑一遍背包即可。然后这个东西的个数只有五百个左右就做完了。
这道题 double 是够用的，long double 可能会比较卡时间。

Code

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template <typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
typedef double ld;
int n;
int w[200005];
ld f[300005];
vector<int> p[105];
int main() {
	scanf("%d", &n);
	for (int i = 1, x; i <= n; ++i) {
		scanf("%d%d", &x, w + i);
		p[x].emplace_back(w[i]);
	}
	f[0] = 1;
	for (int i = 1; i < 100; ++i) {
		sort(p[i].begin(), p[i].end(), greater<int> ());
		int lim = ceil(1 / log((ld) 100 / i));
		while ((int) p[i].size() > lim)
			p[i].pop_back();
		for (int j : p[i])
			for (int k = 300000; k >= j; --k)
				f[k] = max(f[k], f[k - j] * i / 100);
	}
	ll s = 0;
	for (int i : p[100]) s += i;
	ld ans = 0;
	for (int i = 0; i <= 300000; ++i)
		ans = max(ans, f[i] * (i + s));
	printf("%.8lf\n", ans);
	return 0;
}

评论

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

正在加载评论...