专栏文章

题解：AT_abc417_d [ABC417D] Takahashi's Expectation

wweifengzhaomi
AT_abc417_d题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miok04u1
此快照首次捕获于
2025/12/02 20:27
3 个月前
此快照最后确认于
2025/12/02 20:27
3 个月前
查看原文
听说正解是动态规划，其实这道题暴力能过...
好像 E 题过得比 D 题还多...

暴力思路

直接按照题目模拟，时间复杂度：O(NQ)O(NQ)。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Info {
	int x,y,z;
} a[100010];
int n,x,t;
signed main(){
	scanf("%lld",&n);
	for (int i = 1;i <= n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
	scanf("%lld",&t);
	while (t--){
		scanf("%lld",&x);;
		for (int i = 1;i <= n;i++) if (a[i].x >= x) x += a[i].y; else x -= a[i].z,x = max(x,0LL);
		printf("%lld\n",x);
	}
}
TLE 了 2222 个点。

优化暴力

主播主播，我不想写动规，能不能在暴力上面改？
答案是有的，你直接在上面的代码中加一个特判：用 cntcnt 来记录所有 bib_i 的和，如果每次询问的 xx 严格大于 50000005000000，那就直接输出 x−cntx - cnt 即可。
主播主播，这是为什么？
我来解释一下。
这是因为，Atcoder 作为一个国际平台，其数据不容过水，所以，造数据肯定是造极限数据，而不是造水数据，所以，xx 不是 10910 ^ 9 就是 10810 ^ 8，我们把大于 50000005000000 给特判了，剩下的数据还会多吗？这就是为什么暴力加优化就能过的原因。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Info {
	int x,y,z;
} a[100010];
int n,x,t,cnt;
signed main(){
	scanf("%lld",&n);
	for (int i = 1;i <= n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z),cnt += a[i].z;
	scanf("%lld",&t);
	while (t--){
		scanf("%lld",&x);
		if (x > 5000000){
			printf("%lld\n",x - cnt);
			continue;
		}
		for (int i = 1;i <= n;i++) if (a[i].x >= x) x += a[i].y; else x -= a[i].z,x = max(x,0LL);
		printf("%lld\n",x);
	}
}

评论

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

正在加载评论...