专栏文章

题解：P13507 [OOI 2024] Three Arrays

AALANYQ
P13507题解参与者 1已保存评论 0

文章操作

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

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

P13507 [OOI 2024] Three Arrays 题解

子任务 3，5：

作者太菜了所以最开始只会 di=0d_i = 0 的解法。
注意到如果 di=0d_i=0 就相当于操作的第一步不执行，所以问题就转化为第 ii 次将 aa 赋值为 min⁡(a,li)\min(a,l_i) 或者是将 bb 赋值为 min⁡(b,ri)\min(b,r_i)。
那么只需要枚举 ana_n 的值就可以做了。将 nn 个二元组 (li,ri)(l_i,r_i) 按照 ll 排序，假如说 ana_n 的值为 lil_i，则 bnb_n 的值一定就是 min⁡(rj,b0)[1≤j<i]\min(r_j,b_0) [1\le j <i]。每一次维护 an+bna_n+b_n 的值，就做完了。

代码：

CPP
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const double eps=1e-4;
const int maxn=1e5+10;
const int maxm=5e5+10;
const int mod=1e9+7;
const int INF=1e18;
int n,d[maxn],l[maxn],r[maxn],a0,b0,ans;
pii p[maxn];
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i=1;i<=n;i++) cin >> d[i];
	for (int i=1;i<=n;i++) cin >> l[i];
	for (int i=1;i<=n;i++) cin >> r[i];
	cin >> a0 >> b0;
	for (int i=1;i<=n;i++) p[i]=mpi(l[i],r[i]);
	sort(p+1,p+n+1);
	int b=b0;
	for (int i=1;i<=n;i++) ans=max(ans,min(p[i].fi,a0)+b),b=min(b,p[i].se);
    ans=max(ans,b+a0);
	cout << ans;
	return 0;
}

正解：

发现 did_i 每次都很难维护，考虑强行去掉 did_i。
容易发现如果在第 ii 次时将 ljl_j 和 rjr_j 同时减去 di[i≤j]d_i [i \le j]，我们并不需要将 aia_i 加上 did_i，因为每个数的值都减去了 did_i，而我们只需在最后统计答案时加上 2di2d_i 就可以了！正解呼之欲出：预处理 dd 数组的前缀和数组 ss，并且将 lil_i 和 rir_i 减去 sis_i，采用子任务 3，5 的做法并且最后将答案加上 2sn2s_n 就得到了正解。

代码：

CPP
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const double eps=1e-4;
const int maxn=3e5+10;
const int maxm=5e5+10;
const int mod=1e9+7;
const int INF=1e18;
int n,d[maxn],l[maxn],r[maxn],a0,b0,ans=-INF;
pii p[maxn];
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i=1;i<=n;i++) cin >> d[i],d[i]+=d[i-1];
	for (int i=1;i<=n;i++) cin >> l[i],l[i]-=d[i];
	for (int i=1;i<=n;i++) cin >> r[i],r[i]-=d[i];
	cin >> a0 >> b0;
	for (int i=1;i<=n;i++) p[i]=mpi(l[i],r[i]);
	sort(p+1,p+n+1);
	int b=b0;
	for (int i=1;i<=n;i++) ans=max(ans,min(a0,p[i].fi)+b),b=min(b,p[i].se);
	ans=max(ans,a0+b);
	cout << ans+d[n]*2 << "\n";
	return 0;
}

评论

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

正在加载评论...