专栏文章

题解：P12519 「MSTOI-R1」热开水

cc_y_y
P12519题解参与者 9已保存评论 11

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@mip9sm3e
此快照首次捕获于
2025/12/03 08:29
3 个月前
此快照最后确认于
2025/12/03 08:29
3 个月前
查看原文

P12519 「MSTOI-R1」热开水 题解

题面的一切指向了某 P 开头的音游~
注意到 bib_i 是个正数，
因此第二天一个曲目的 rksrks 一定不小于第一天。因此发现总 rksrks 随天数增加而单调不降。本题具有单调性，考虑二分。
如何实现 check() 函数呢？按题意模拟就好了~
但是有以下几个细节：
  • 一个曲目的 acc≤70%acc \le 70\% 时，该区 rksrks 应为 00。
  • 对于所有的计算结果后，都应保留两位小数。
  • 记得初始化！！！
同时对于本题，笔者有以下的小优化可以使实现更简单：
  • 记 b0b_0 为所有 acc=100%acc = 100\% 的曲目中 rksrks 的最大值，bi(1≤i≤4)b_i (1 \le i \le 4) 为最大的四个 rksrks。
    先将 bi(1≤i≤4)b_i (1 \le i \le 4) 升序排列。当我们计算出一个新的 rksrks 时，如果其 rks>b1rks > b_1 就将其替换，并在最后像插入排序一样保持 bb 数组升序。注意 b0b_0 不参与排序。
  • 由于 bb 的长度很小，因此计算总 rksrks 时，可直接暴力求解；

Code

CPP
const int N = 1e5 + 10, mod = 998244353;
double rt2(double x) {
	int y;
	double z;
	x *= 100, y = x;
	z = y / 100.0;
	return z;
}
struct node {
	double a, b, c, rks;
}a[N];
double b[6], tb[6], m;
int n;
bool check(int k) {
	double rks = 0;
	memcpy(b, tb, sizeof tb);
	for (int i = 1; i <= n; i++) {
		double acc = min(100.0, a[i].a + (k-1) * a[i].b);
		if(acc <= 70) a[i].rks = 0;
		else {
			a[i].rks = rt2((acc-55.0) / 45.0);
			a[i].rks = rt2(a[i].rks * a[i].rks * a[i].c);
		}
		if(a[i].rks > b[1]) b[1] = a[i].rks;
		
		if(acc == 100.0) b[0] = max(b[0], a[i].rks);
		double rks = rt2((b[0] + b[1] + b[2] + b[3] + b[4]) / 5.0);
		if(rks >= m) return true;
		for (int j = 1; j <= 3; j++) {
			if(b[j] > b[j + 1]) swap(b[j], b[j + 1]);
			else break;
		}
	}
	return false;
}
int main() {
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a >> a[i].b >> a[i].c;
	}
	cin >> b[1] >> b[2] >> b[3] >> b[4] >> b[0];
	sort(b + 1, b + 5);
	for (int i = 0; i <= 4; i++) tb[i] = b[i];
	
	int l = 0, r = 10010, ans = -1;
	while(l <= r) {
		int mid = l + r >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

Others

本题暴力有 9595 分。
Phi 好玩，都给我去打 Phi！

评论

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

正在加载评论...