因为时间紧迫所以忽略所有时间复杂度的计算。 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$ 以外的实验没有意义，所以我们…