当前位置:首页 > 数据结构 > 线段树 > 正文
洛谷P9871天天爱打卡(NOIP2023)
231+

题目大意:有m次活动,活动即在[x, y]天内每天跑步,完成后有奖励v,但主人公至多连续跑c天,跑步一天就消耗a,请问这种最大收获(v-a)是多少?

题目描述

小 T 同学非常热衷于跑步。为了让跑步更加有趣,他决定制作一款叫做《天天爱打卡》的软件,使得用户每天都可以进行跑步打卡。

开发完成后,小 T 同学计划进行试运行,他找了大 Y 同学来帮忙。试运行共 $n$ 天,编号为从 $1$ 到 $n$。

对大 Y 同学来说,如果某天他选择跑步打卡,那么他的能量值会减少 $d$。初始时,他的能量值是 $0$,并且试运行期间他的**能量值可以是负数**。

而且大 Y 不会**连续**跑步打卡**超过** $k$ 天;即不能存在 $1\le x\le n-k$,使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。

小 T 同学在软件中设计了 $m$ 个挑战,第 $i$($1\le i \le m$)个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述,表示如果在第 $x_i$ 天时,用户已经连续跑步打卡至少 $y_i$ 天(即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡),那么小 T 同学就会请用户吃饭,从而使用户的能量值提高 $v_i$。

现在大 Y 想知道,在软件试运行的 $n$ 天结束后,他的能量值**最高**可以达到多少?

输入输出格式

输入格式

**本题的测试点包含有多组测试数据。**

输入的第一行包含两个整数 $c$ 和 $t$,分别表示测试点编号和测试数据组数。对于样例,$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

接下来,对于每组测试数据:

– 输入的第一行包含四个正整数 $n,m,k,d$,分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
– 接下来 $m$ 行,每行包含三个正整数 $x_i,y_i,v_i$,表示一次挑战。

输出格式

输出一行一个整数表示对应的答案。

输入输出样例

输入样例 #1

1 1
3 2 2 1
2 2 4
3 2 3

输出样例 #1

2

说明

**【样例解释 #1】**

在第 $1,2$ 天跑步打卡,第 $3$ 天不跑步打卡,最终会获得 $(-1)+(-1)+4=2$ 的能量值。

**【样例解释 #2】**

该组样例满足测试点 $3$ 的条件。

**【样例解释 #3】**

该组样例满足测试点 $5$ 的条件。

**【样例解释 #4】**

该组样例满足测试点 $15$ 的条件。

**【样例解释 #5】**

该组样例满足测试点 $17$ 的条件。

**【样例解释 #6】**

该组样例满足测试点 $19$ 的条件。

**【数据范围】**

记 $l_i=x_i-y_i+1$,$r_i=x_i$​;

对于所有测试数据,保证:$1\le t\le 10$,$1\le k\le n\le 10^9$,$1\le m\le 10^5$,$1\le l_i\le r_i\le n$,$1\le d,v_i\le 10^9$。

|测试点编号|$n \le$|$m \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1, 2$|$18$|$10 ^ 2$|无|
|$3, 4$|$10 ^ 2$|$10 ^ 2$|无|
|$5 \sim 7$|$10 ^ 3$|$10 ^ 3$|无|
|$8, 9$|$10 ^ 3$|$10 ^ 5$|无|
|$10, 11$|$10 ^ 5$|$10 ^ 3$|无|
|$12 \sim 14$|$10 ^ 5$|$10 ^ 5$|无|
|$15, 16$|$10 ^ 9$|$10 ^ 5$|A|
|$17, 18$|$10 ^ 9$|$10 ^ 5$|B|
|$19 \sim 21$|$10 ^ 9$|$10 ^ 5$|C|
|$22 \sim 25$|$10 ^ 9$|$10 ^ 5$|无|

特殊性质 A:$k\le 10^2$;

特殊性质 B:$\forall 1\le i<m$,$r_i<l_{i+1}$;

特殊性质 C:$\forall 1\le i<j\le m$,$l_i<l_j$,$r_i<r_j$。

解题思路

这是一个线性DP,我们可以计算出f[i]表示前i天的最大值:如果第i天有跑步,开始跑步时间可以是i-c+1~i,上次结束跑步时间则是i-c+1-2~i-2;如果不跑步,那么f[i]=f[i-1],维护前缀最大值。

这样的话,转义时是O(c)的,而i的范围也很大。认真思考后发现,结束跑步时间(活动奖励)只有在活动最后一天,我们可以只计算那些天就行。转移时可以用数据结构优化,实现区间查询最大值即可。

在维护线段树的时候,遇到一个问题就是每天跑步的消耗处理,跑3天要减3a,跑5天减5a……前驱靠前的会多减一个a,那么我们一开始给每个位置加i个a即可,这样i+1的位置相当于多加1个a、后面少减1个a,因为抵消了所以可以之间比较最大值。如对于y结束跑步,前驱是1、2、3,分别需要减去y、y-1、y-2个a,分别已经加过1、2、3个a了,后面都是再减去y+1个a就行。

道理基本上讲完了,下面是细节。

1、前驱处理:跑步开始时间只可能是x,前驱只可能是x-2,x-1为不跑步的时间,此时f[x-1]=f[x-2]。对于每个前驱,只放入线段树一次,因此需要去重。放入线段树时,他的值要加上x个a,还要加上前缀最大值——前面获得的最高奖励。(单点增加)

2、后继处理:跑步结束的时间只可能是y,前面可以能有很多开跑时间,上次结束跑步时间范围是[y-c+1-2, y-2]。(区间查询最大值)

3、获得奖励处理:对于每个奖励[x, y],他只对x-2之前的前驱有效,x-1是不可能获得这个奖励的,因为x-1也跑步不合规矩。(区间增加)

程序实现

查询中x已经减2;加入快读满分。

离散化后,线段树结点少很多,不受评测机影响,稳过。注意,离散化少用STL,否则更慢。

报歉!评论已关闭.