日记

久蹲一定要慢起,我今天差点死在厕所。

T1 # Link to T1

神秘小唐题。

T2 # Link to T2

神秘小 dp。设 $dp_{i,x,y}$ 表示前 $i$ 轮取完剩下两个数是 $x,y$ 的最大答案，使用滚动数组优化，初始化 $dp_{a_1,a_2} = dp_{a_2,a_1} = 0$，其余全是 $-\inf$。设当前的三个数是 $u,v,w$，考虑转移：

做出贡献：

• $u = v = w$
  显然是贪心的取这三个数，$cnt$ 加上 $1$ 然后 continue。
• $u = v \lor v = w \lor u = w$
  我们把这三个数看做 $\{a,a,b\}$，有两种方式可以做出贡献：$\{b,b \mid a,a,b\},\{a,c \mid a,a,b\}$。前者可以 $O(1)$ 转移：$dp_{a,a} \gets dp_{b,b} + 1$。后者可以枚举 $c$ 做到 $O(n)$ 转移：$dp_{b,c} \gets dp_{a,c} + 1$。
• $\text{otherwised}.$
  有三种方式可以做出贡献：$\{u,d \mid u,v,w\},\{v,v \mid u,v,w\},\{w,w \mid u,v,w\}$，分别表现为 $dp_{v,w} \gets dp_{u,d} + 1,dp_{u,w} \gets dp_{v,v} + 1,dp_{u,v} \gets dp_{w,w} + 1$。

不做出贡献：

• 扔掉 $u,v,w$
  剩下的两个数没变，由于是滚动数组，所以不操作。
• 扔掉 $u,v,w$ 的其中两个
  我们可以枚举 $c,d$ 来从 $dp_{c,d}$ 来转移到 $dp_{c,d/v/w}$，但是转移的显然是 $\max_{d = 1}^{n}dp_{c,d}$，所以我们可以通过维护 $maxc_c = \max_{d = 1}^{n}dp_{c,d}$ 来转移。
• 扔掉 $u,v,w$ 其中一个：
  依然是枚举 $c,d$，从 $dp_{c,d}$ 转移。我们可以记录一个 $ans$ 表示整个 $dp$ 数组的最大值。

还有一个小妙招：由于转移的时候要同时更新 $ans$ 和 $maxc$，所以对于 $dp_{x,y} \gets z$，可以通过一个 vector<array<int,3>> 来记录 $\{x,y,z\}$，之后一起转移，复杂度 $O(n^2)$。

T3 # Link to T3

设 $dp_{l,r,d}$ 表示在左边界为 $l$，右边界为 $r$，下边界为 $d$ 的时候的最小（就是最上）的上边界在哪里。显然有 $ans = \max_{l = 1}^{m}\max_{r = 1}^{m}\max_{d = 1}^{n} (r - l + 1) \times (d - dp_{l,r,d})$。

考虑如何转移。我们发现一个 $[l,r]$ 区间非法，当且仅当 $[l + 1,r]$ 非法或者 $[l,r - 1]$ 非法或者 $l,r$ 这两列合起来非法。那么转移有 $dp_{l,r,d} = \max(dp_{l + 1,r,d},dp_{l,r - 1,d},f_{l,r,d})$。其中 $f_{l,r,d}$ 表示在下边界为 $d$ 时只看 $l,r$ 两列能延伸到哪，复杂度 $O(n^3)$。

T4 # Link to T4

没改。

GCD# Link to

我们直接开始推柿子：

设 $sum(n,k) = \sum_{i = 0}^{n}i^k$，我们有神秘小公式：$sum_{n,k} = \frac{(n + 1)^{k + 1} - \sum_{j = 0}^{k - 1}\binom{k + 1}{j}sum(n,j)}{k + 1}$，可以在 $O(k^2)$ 的复杂度内求出 $\sum_{i = 1}^{n}i^k$，对于 $k \le 5$ 完全够用。然后我们就可以数论分块了 + 杜教筛了，时间复杂度 $O(\text{能过})$。

后日谈 # Link to 后日谈

为啥你不会骗分？