昨晚ABC D题解

复仇者_帅童

2025-08-03 09:07:53

发布于：浙江

31阅读

0回复

0点赞

题目翻译：给定 $n$ 次操作，每次操作会给定三个正整数 $P_i,A_i,B_i$ ，假设将要操作的数为 $x$ ，则：

如果 $x\le P_i$ ，则将 $x$ 的值加上 $A_i$ 。
如果 $x\gt P_i$ ，则将 $x$ 的值减去 $B_i$ 。

给定 $q$ 次询问，每次询问给定一个正整数 $X_i$ ，问经过这些操作后 $X_i$ 的值为多少。

注意到 $P_i,A_i,B_i$ 都很小，所以考虑从这里下手。

根据题意发现较大的 $X_i$ 会一直执行减 $B_i$ 的操作，所以考虑二分求出第一个使 $X_i\lt 500$ 的操作的位置和经过这些操作后 $X_i$ 的值。

然后我们枚举每个数在经过后面的若干次操作后最终变成什么，然后将 $X_i$ 一个一个带入即可。注意经过操作后的数可能到达 $1000$ ，所以应该枚举到 $1000$ 。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct Queries{//转离线
	int val, first, id;//经过前 first 个操作后的 X_i 为 val
	bool operator < (const Queries &b) const{
		if(first == b.first) return val < b.val;
		return first > b.first;
	}
}q[500005];
int a[100005], b[100005], c[100005];
int pre[100005];//前缀和，方便二分
int ans[500005];
int cur[1005], fin[1005];//滚动数组，节省空间
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i];//前缀和
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> q[i].val;
		q[i].id = i;
		int idx = upper_bound(pre + 1, pre + n + 1, q[i].val - 500) - pre - 1;//二分查询第一个使 X_i<=500 的操作
		q[i].first = idx + 1, q[i].val -= pre[idx];//直接执行这些操作
		if(idx >= n) ans[i] = q[i].val;//如果没有直接写答案
	}
	sort(q + 1, q + m + 1);
	for(int i = 1; i <= 1000; i++){
		fin[i] = i;
	}
	int l = 1;
	for(int i = n; i >= 1; i--){
		for(int j = 0; j <= 1000; j++){
			if(j <= a[i]) cur[j] = fin[j + b[i]];//计算每个数后i次操作的值
			else cur[j] = fin[max(0ll, j - c[i])];
		}
		for(int j = 0; j <= 1000; j++){
			fin[j] = cur[j];//滚动数组
		}
		while(l <= m && q[l].first > i) l++;
		while(l <= m && q[l].first == i) ans[q[l].id] = fin[q[l].val], l++;//双指针获取答案
	}
	for(int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}

	return 0;
}

时间复杂度： $O(nV+q\log q)$ ，其中 $V=1000$ 。

有帮助，赞一个

去预览

0/2000

全部评论 3

复仇者_澜（不处不加团队）
A，B，C的题解呢

3小时前来自广东
0
- 复仇者_帅童
  回复复仇者_澜（不处不加团队）
  懒得打，是个人都会
  
  3小时前来自浙江
  0
- 复仇者_澜（不处不加团队）
  回复复仇者_帅童
  o/
  /o
  
  3小时前来自广东
  0

LYB

附一个记忆化搜索解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n,q,p[N],a[N],b[N],sum[N],mem[N][505];
int dfs(int i,int x) {
	if(i > n) {
		return x;
	}
	if(x > 500) {
		return dfs(i + 1,x - b[i]);
	}
	else {
		if(mem[i][x]) {
			return mem[i][x];
		}
		else {
			if(p[i] >= x) {
				mem[i][x] = dfs(i + 1,x + a[i]);
			}
			else {
				if(x - b[i] > 0) mem[i][x] = dfs(i + 1,x - b[i]);
				else mem[i][x] = dfs(i + 1,0);
			}
			return mem[i][x];
		}
	}
}
int main() {
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> p[i] >> a[i] >> b[i];
		sum[i] = sum[i - 1] + b[i];
	}
	cin >> q;
	while(q--) {
		int x,cnt;
		cin >> x;
		if(x > 500) {
			cnt = lower_bound(sum+1,sum+1+n,x-500) - sum - 1;
			cout << dfs(cnt + 1,x - sum[cnt]) << '\n';
		}
		else cout << dfs(1,x) << '\n';
	}
	return 0;
}

2天前来自浙江

复仇者_帅童
回复LYB
%%%

2天前来自浙江
0

复仇者_帅童
d

2天前来自浙江
0

全部评论 3

热门讨论