A #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define fi first…

$\text{Solution}$ 贪心一下，不为了完成任务，我们不会打卡。 容易得出一个 DP。设 $f(i)$ 为最后一次不打卡是在第 $i$ 天时，最高的能量值大小。 转移枚举上一次不打卡的时间 $j$，有 $$f(i)=\max_{j \in [i-k,i-1] } \Big\{f(j) + w(j+1,i-1) \; - \; (i-j-…

A 略。 #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define fi fi…

link $\texttt{Solution}$ 较为复杂的计数直接考虑 DP。 区间相关的题目排了序才能做，就是按照左端点还是右端点排的问题。 我们考虑当前区间 $i$，如果要选它，那么我们需要保证与其异色的区间右端点小于 $l_i$。 这个就是后效性的源头，把它加入状态即可。 设 $f_k,0/1$ 为选出的最后一个区间右端点为 $k$，颜色为…

ABC137D Summer Vacation 错解：扫时间，维护当前可以做的事件集合，贪心选取收益最大的。 正解：把事件以收益为第一关键字，时长为第二关键字递增排序，每次选取收益最大的，找到能使其产生收益的最晚的那天安排这个事件。用并查集维护。 #include<bits/stdc++.h> using namespace std; …

树上差分 从抽象代数的角度讲，树上差分可以维护所有群上信息。 换句话说，满足结合律，存在「可减性」。 通过差分我们能将一个高纬问题以常数代价转化为低维问题，而问题低一维往往会简单非常多 —— lxl 太 $\textit{Trivial}$ 的我们就不提了。 下文成「前缀」为根到节点的路径。 luogu8201 [yLOI2021] 生活在树上（h…

线段树上二分 用形式化的语言讲，线段树上二分求解的是这一类问题。 给定 $L$，找到一个 $R \in [L,n]$ 满足$$f \Big( op\big([L,R-1]\big) \Big) = 1$$$$f\Big( op\big(R\big) \Big)=0$$ 其中 $f$ 为某种合法性函数，$op$ 是将区间信息合并为 $f$ 能处理的信…