P9871 [NOIP2023] 天天爱打卡 题解
未来姚班zyl
·
·
题解
前言
本人在赛时可以说是按照出题人设计的部分分一步一步想到正解，思维过程应该算非常标准，且很多部分分的代码也在赛时打出来了。
所以这篇题解肯定能做到流畅，详细，具体。
题目大意
一共有 n 天，大 Y 可以花费 d 的能量在任何一天跑步，但大 Y 不能在连续的 k 天跑步。
此外，将给出 m 段任务区间 [l_i,r_i]。如果在这段区间的每一天都跑了步，则会获得 v_i 的能量。
大 Y 的初始能量为 0，请你最大化跑完步后大 Y 最终的能量。
题目分析
以下复杂度均省略了 T，即数据组数。
直接枚举每一天是否跑了步，然后计算贡献即可。
复杂度 O(2^n(n+m))，期望得分 8 分。
这一部分没什么太大用处，代码也很好写，故不给出代码。
如果我们知道了在一段区间内都跑了步，我们则可以直接枚举 m 个区间并计算出对答案的贡献。所以我们设计状态 dp_{i}，表示只考虑前 i 天的最大答案。首先有转移 dp_i=dp_{i-1}。其次，我们考虑右端点为 i 的区间。暴力枚举左端点 j（注意区间长度不能超过 k），则我们有转移：
其中 $w_{l,r}$ 表示任务区间对 $[l,r]$ 的贡献，可以 $O(m)$ 单次计算。加上 $O(n)$ 枚举左端点，可以做到 $O(nmk)$。
期望得分 $16$ 分。
这一部分代码如下：
```cpp
ll dp[N];
inline ll get(int l,int r){
ll ans=0;
rep(i,1,m)if(a[i].l>=l&&a[i].r<=r)ans+=a[i].k;
return ans;
}//计算贡献
inline ll got(int x){
//由于 j-2 可能越界，但并非无法转移，故我们额外写一个函数表示 dp 的值
if(x>=0)return dp[x];
return 0;
}
inline void subtask1(){
rep(i,0,n)dp[i]=0;
//初始化
rep(i,1,n){
rep(j,max(i-k+1,1),i)dp[i]=max(dp[i],get(j,i)+got(j-2)-1LL*d*(i-j+1));//状态转移
dp[i]=max(dp[i],dp[i-1]);
}
cout <<dp[n]<<'\n';
}
```
- 我会扫描线和树状数组！
我们考虑优化计算贡献的方式。
可以想到，对于枚举的区间 $[j,i]$，能够贡献答案的任务区间 $[l_k,r_k]$ 一定满足 $j\le l_k\le r_k\le i$。
那么我们按照右端点顺序把任务区间加入，则 $r_k\le i$ 的条件就能天然满足。计算贡献时，我们就只需要查询满足 $l_k\ge j$ 的任务区间的权值和即可，这个可以用树状数组维护，单次计算贡献的复杂度降至 $O(\log m)$。
复杂度 $O(nk \log m)$，期望得分 $36$ 分。
这一部分代码如下：
```cpp
vector<Pi >p[N];//这个存的任务区间
ll t[N];
inline void add(int x,int k){
x=n-x+1;//这里直接倒着存，写的时候就不用差分了，下面一样的道理
while(x<=n)t[x]+=k,x+=x&-x;
}
inline ll query(int x){
ll ans=0;
x=n-x+1;
while(x)ans+=t[x],x-=x&-x;
return ans;
}//树状数组
#define E(x) for(auto y:p[x])
inline void subtask2(){
rep(i,1,m)p[a[i].r].pb({a[i].l,a[i].k});
rep(i,0,n)dp[i]=0;//初始化
rep(i,1,n){
E(i)add(y.first,y.second);
rep(j,max(i-k+1,1),i)dp[i]=max(dp[i],query(j)+got(j-2)-1LL*d*(i-j+1));
dp[i]=max(dp[i],dp[i-1]);
}
rep(i,1,n)p[i].clear(),t[i]=0;//多测要清空哦！
cout <<dp[n]<<'\n';
}
```
- 我会离散化！
当 $n$ 变得特别大，有用的端点也就只有 $O(m)$ 个，所以直接把 $n$ 按照任务区间的端点离散化，计算贡献依旧正常，就是要注意离散化后相邻两个值是否相差 $1$。复杂度 $O(mk\log m)$。
期望得分 $52$ 分。
这一部分代码如下：
```cpp
//b 数组是离散化数组，ln 是离散化数组的长度，其它部分都一样
inline void subtask3(){
n=ln;
rep(i,1,m){
a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b;
a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b;
p[a[i].r].pb({a[i].l,a[i].k});
}
rep(i,0,ln)dp[i]=0;
rep(i,1,ln){
E(i)add(y.first,y.second);
for(int j=i;j>=1&&b[i]-b[j]+1<=k;j--){
int pos=j-2;
if(b[j-1]!=b[j]-1)pos=j-1;
dp[i]=max(dp[i],query(j)+got(pos)-1LL*(b[i]-b[j]+1)*d);
}
dp[i]=max(dp[i],dp[i-1]);
}
cout <<dp[ln]<<'\n';
rep(i,1,ln)t[i]=0,p[i].clear();
}
```
- 我会线段树！
考虑我们的复杂度始终无法摆脱一个类似 $O(n^2)$ 的瓶颈。显然在于我们每次转移都是暴力枚举左端点。而不难发现，每次枚举的左端点是一个区间，只要能够满足一个查询区间最大值的数据结构就能把复杂度降下去。但中途加入任务区间又会带来区间修改。等等，区间修改和区间最大值？这直接线段树不就行了！使用线段树来处理，每次二分最靠左的满足条件的 $j$（当然也可以双指针），复杂度 $O(m\log m)$，足以通过此题！
赛时满分代码如下（去掉文件输入输出）：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define Pi pair<int,int>
#define pb push_back
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57){if(c=='-')w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-'0',c=getchar();return s*w;}
const int N=2e5+5,M=1e6+5,inf=(1LL<<31)-1;
const ll llf=1e18;
using namespace std;
int n,m,k,d,lsh[N],b[N],ln,testid,T;//days,tasks,limits,costs
struct node{
int l,r,k;
}a[N];
inline void init(){
ln=0;
n=read(),m=read(),k=read(),d=read();
lsh[m*2+1]=0;
rep(i,1,m){
a[i].r=read(),a[i].l=a[i].r-read()+1,a[i].k=read();
lsh[(i<<1)-1]=a[i].l,lsh[i<<1]=a[i].r;
}
sort(lsh+1,lsh+m*2+1);
rep(i,2,m*2+1)if(lsh[i]^lsh[i-1])b[++ln]=lsh[i-1];//离散化
}
ll dp[N];
inline ll got(int x){
if(x>=0)return dp[x];
return 0;
}
vector<Pi >p[N];
#define E(x) for(auto y:p[x])
#define L x<<1
#define R L|1
#define lc L,l,mid
#define rc R,mid+1,r
#define OK Ll<=l&&r<=Rr
struct seg{
ll w,laz;
}xd[N<<2];
inline void insert(int x,ll k){
xd[x].w+=k,xd[x].laz+=k;
}
inline void pushdown(int x){
insert(L,xd[x].laz),insert(R,xd[x].laz),xd[x].laz=0;
}
inline void getup(int x){
xd[x].w=max(xd[L].w,xd[R].w);
}
inline void build(int x,int l,int r){
xd[x]={0,0};
if(l==r)return;
build(lc),build(rc);
}
inline void modify(int x,int l,int r,int Ll,int Rr,ll k){
if(OK)return insert(x,k),void();
pushdown(x);
if(Ll<=mid&&Rr>=l)modify(lc,Ll,Rr,k);
if(Ll<=r&&Rr>mid)modify(rc,Ll,Rr,k);
getup(x);
}
inline ll query(int x,int l,int r,int Ll,int Rr){
if(Ll>Rr)return 0;
if(OK)return xd[x].w;
pushdown(x);
if(Rr<=mid)return query(lc,Ll,Rr);
if(Ll>mid)return query(rc,Ll,Rr);
return max(query(lc,Ll,Rr),query(rc,Ll,Rr));
}
//线段树
#define Root 1,1,ln
inline int find(int x){
int l=1,r=ln,ans=r;
while(l<=r)if(b[mid]>=x)ans=mid,r=mid-1;
else l=mid+1;
return ans;
}//手写二分
inline void subtaskall(){
build(Root);
rep(i,0,ln)dp[i]=0;
rep(i,1,m){
a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b;
a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b;
p[a[i].r].pb({a[i].l,a[i].k});
}
rep(i,1,ln){
E(i)modify(Root,1,y.first,y.second);
int j=find(b[i]-k+1);
dp[i]=max(dp[i],query(Root,j,i-1))-1LL*b[i]*d-1LL*d;
int pos=i-2;
if(b[i-1]!=b[i]-1)pos=i-1;
dp[i]=max(dp[i],query(Root,i,i)+got(pos)-d);
dp[i]=max(dp[i],dp[i-1]);
modify(Root,i,i,got(pos)+1LL*b[i]*d);
}
cout <<dp[ln]<<'\n';
rep(i,1,ln)p[i].clear();
}//dp
inline void solve(){
subtaskall();
}
int main(){
testid=read(),T=read();
while(T--){
init();
solve();
}
return 0;
}
```
写的那么用心，点个赞再走吧 ！awa
#### update 2024/11/5：
- 修改了一处评论区指出的笔误。
- 一晃一年过去，又一年的 NOIP 又要开始了，如果在备战 NOIP 时感到迷茫，可以从[这篇专栏](https://www.luogu.com.cn/article/r244u201)获取一些建议，祝大家的 OI 生涯一帆风顺！