日记

大输特输。

Median Splits# Link to

如果有 $a_i \le k$，就把 $a_i$ 置为 $1$，反之置为 $-1$。这样，如果一段区间 $[l,r]$ 的中位数 $\le k$ 的充要条件就是 $\sum_{i = l}^{r}a_i \ge 0$。如何使三段区间的中位数的中位数 $\le k$ 呢？显然是有两个区间的中位数 $\le k$ 就行。直接大力分讨哪两个区间的中位数 $\le k$。

• 左边的和中间的区间
  维护一个前缀和 $sum_i$。如果 $sum_i \ge 0$，就看看有没有小于等于 $sum_i$ 的非负数出现在 $sum$ 里比 $i$ 靠前的地方 $j$。如果有，那么 $[1,j],[j + 1,i],[i + 1,n]$ 就是一组解。直接上权值线段树维护。
• 右边的和中间的区间
  reverse 一下 $a$，然后同上。
• 左边的和右边的区间
  在上面的两次计算中，记录一个 $x,y$ 分别表示两次计算中 $sum_i$ 最早非负的位置。如果 $x + y < n$，就说明两个区间中间还能再夹一个区间，就是可行的。

submission

Local Construction# Link to

大力分讨 + 差分约束。

好像神明知道我的码力不行，天天给我发大力分讨题。

Soldier Game# Link to

考虑枚举最小值。设 $dp_{l,r,i,j}$ 表示在区间 $[l,r]$ 中，$l$ 是否和 $l - 1$ 配对，$r$ 是否和 $r + 1$ 配对的最小的最大值。用线段树维护。转移就是 $dp_{i,j} = \min\{\max(dp_{l,mid,i,k},dp_{mid + 1,r,k,j})\}$，表示在诸多 $\max(dp_{l,mid,i,k},dp_{mid + 1,r,k,j})$ 里取最小值。用线段树维护。将每种配对方式的战力从小到大排序。每次记录完答案就把值小于当前值的地方置为 $\inf$。

小 A 的卡牌游戏# Link to

考虑只有两种牌怎么做。把牌按照 $b_i - a_i$ 排序，然后按照排完序的顺序，先取 $B$ 个再取 $A$ 个。想想多加一个怎么做。

我们设 $dp_{i,j}$ 表示在前 $i$ 个 3pick 里取了 $j$ 个 C。转移是显然的。如果我们不选 c，就按照上面的贪心策略转移：如果 $i - j \le B$，就取 B，反之取 A。

后日谈 # Link to 后日谈

今天中午午觉没睡好。下午听 AC 自动机烧烤过度，还去打了个球。晚上回机房直接获得 debuff：疲惫；效果：智力 $- \inf$，理解能力 $- \inf$，记忆力 $- \inf$。然后晚上硬生生的把 KMP 和 AC 自动机搞懂了。

AC 自动机学习笔记 is coming soon.