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…

真身败名裂了。 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 …

$\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 操作 2 会让奇数-1，偶数+1。 不难发现只有当 $a$ 为奇数时，我们能让 $a$ 减小，且只能减少 $1$。 如果 $a > b$，那么当且仅当 $a \oplus 1 = b$ 有解。 下面讨论 $a < b$ 的情况。 如果 $x \le y$，那么我们全部使用操作 $1$ 即可。 否则我们肯定是两种操作交替使用。 关于第…

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…

身败名裂了。 luogu9556 [SDCPC 2023] Orders 货物按天排个序，求个和，找日期分界线，判一下够不够即可。 #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #defi…

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)$，右端点是 $…

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