失败者所做的一切，不过是增添笑料罢了。 一切又回到原来那样。

因为时间紧迫所以忽略所有时间复杂度的计算。 luogu2657 [SCOI2009] windy 数 板子。 #include<bits/stdc++.h> using namespace std; #define int long long #define uint unsigned long long #define PII pai…

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

贪心的基本思路是抹除后效性。 luogu9378 [THUPC 2023 决赛] 物理实验 尽可能保留编号小的实验一定是最优的。 考虑维护一个集合 $S$ 表示当前已经确定可以保留的实验集合，枚举实验 $i$ 尝试加入，这样原问题就转化为了 $n$ 轮判定问题。 考虑如何 check。由于确定了 $S$ 并且做 $S$ 以外的实验没有意义，所以我们…

先放题，有时间再整理。 其实也就那回事，理解了思想之后就没啥特殊性了。 luogu6647 [CCC2019] Tourism 不难发现 $t =\lceil \frac{n}{k} \rceil$，然而并没有什么用，我们只要在转移时对取值区间进行限制即可。 具体地，第 $i$ 天的取值左端点是 $L_i = \max(0,i-k)$，右端点是 $…

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

未完待续 CF1107E Vasya and Binary String 设 $f(i,j,t)$ 为删去区间 $[i,j]$，其中区间右边还有 $t$ 个与 $S[j]$ 相同的字符的最大收益。 $$f(i,j,t) = \max \begin{cases}f(i,j-1,0) + a_{t+1}\\max _{k=i}^{j-1} \Big\{…

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int …

欧拉路径 定义 从一个点出发，不重不漏地经过图中每一条边的一条路径，允许重复经过节点。 无向图 首先必须是连通图，其次是两种情况。 所有点的度数是偶数。 恰好存在两个点的度数是奇数。 有向图 要求连通。 所有点的入度等于出度。 恰好存在一个节点入度比出度多 $1$，一个节点入度比出度少 $1$。 欧拉回路 定义 起点和终点是一个点的欧拉路径。 无向…