10.18
T2 P14066
容易发现分成的三段按 $a_i$ 排序之后一定是连续的三段，否则可以通过交换两个人所在的集合使得限制更严格。
钦定最大的 $a_i$ 在第三组。按照 $a_i$ 从小到大的三段分别为 $123$ 还是 $213$ 分类。枚举第一段的长度，然后可以计算出第二段最少是多少，最后检查第三段长度是否符合要求。
T3 AT_joisc2015_f
首先把每个人进门出门看成一个事件，按照时间排序。设 $i$ 为触发一个事件的员工，$j$ 为下一个触发事件的员工。
考虑什么时候对答案有贡献，贡献即为两段时间的间隔。
- $i$ 进门，$j$ 进门：当且仅当 $j$ 有钥匙时，把贡献加到 $j$ 上。
- $i$ 出门，$j$ 出门：当且仅当 $i$ 有钥匙时，把贡献加到 $i$ 上。
- $i$ 进门，$j$ 出门：一定有贡献，直接加到答案上。
- $i$ 进门，$j$ 出门：当且仅当 $i, j$ 都有钥匙时，把贡献加到 $i \to j$ 的边上 。
此时答案构成了若干条链，我们把这些链连成一整条链，在链上做 dp。
设 $dp_{i, j, 0/1}$ 表示前 $i$ 个点，用了 $j$ 把钥匙，当前这个人用不用的最大贡献。转移是简单的。
$$ dp_{i, j, 0} = \max\{ dp_{i - 1, j, 0/1} \} \\ dp_{i, j + 1, 1} = \max\{ dp_{i - 1, j, 0} + val_i + adj_i \} $$
T4 P12554
咕咕咕
10.20
T3 P10794
咕咕咕
T4 AT_agc003_f
咕咕咕
10.23
C AT_joisc2016_j
注意到移动到相邻的格子需要 $2$ 步（先撞到冰再滑回来），移动到冰前面需要 $1$ 步，而移动到其他的格子都可以通过移动到这两种情况推出来，建图跑最短路。
D CF1733E
读完题发现因为每个史莱姆每秒都会往右或者往下走，所以不可能有相遇，所以那个合并是没用的。
第 $t$ 秒很不好考虑，可以转化成 前 $t$ 秒有没有史莱姆经过 $(x, y)$，比较第 $t$ 秒和第 $t - 1$ 秒。
那么前 $t$ 秒是好做的，考虑一个位置有 $x$ 个史莱姆经过时，因为方向是右下右下交替的，显然有 $\lceil \frac{x}{2} \rceil$ 个去了 $(x, y + 1)$，有 $\lfloor \frac{x}{2} \rfloor$ 个去了 $(x + 1, y)$。然后就可以递推模拟了，设 $f_{i, j}$ 是前 $t$ 秒有多少个点经过这个格子，$O(n ^ 2)$ 转移就行。
斜抛运动 · 2025-10-19 15:56
牛逼！
小粉兔 · 2025-10-19 16:02
Always continue; Never break;