USACO 2024 Jan

这次直接从 Silver 打到 Platinum，非常高兴啊，来写一下。

Silver

开局先看个 T1。看了 T1 之后跑去蹲厕所了。

蹲到一半发现，限制 $(u_i, v_i)$ 相当于 $a_{u_i + 1 \sim v_i - 1}$ 一定都不是前缀最大值， $a_{v_i}$ 一定是前缀最大值。显然可以 $O(n)$ 判断是否矛盾并且求出一个位置的限制。

写了一下构造，结果过不去样例。后来发现可以调整，一发过了。

看 T2。显然每次选一个之前没选过的叶子来覆盖一个点。显然有决策包含性，直接贪即可。

T2 先放着，看 T3。T3 感觉非常 Hard，会不了一点。

发现 $a, b (a \ge b)$ 模 $m$ 相同的条件是 $m | a - b$ ，是 $O(d(v))$ 级别的。

且因为最多只能有三种取值，所以前四个数至少要有一对相同的。

于是枚举前四个数组成的每一对，将能够使这一对相同的 $m$ 都跑一遍暴力即可。

特判一下 $n \le 3$ ，交上去过了。

跑回去 5min 写完 T2，耗时 2h AK。

开局先看个 T1。看了 T1 之后又跑去蹲厕所了。

先手动走到交点上，然后发现每走奇数步会转向。预处理行和列下一个奇数步的位置，行列一起倍增即可。有点麻烦，先放着。

回来看 T2，发现是 Silver T1 Counting ver.。USACO 真会出题。

发现 $n$ 没有用，直接前缀和优化 dp 做到 $O(qv \log mod)$ ，写了一发过了。感觉比 Silver T1 Easy。

看 T3。发现确定 $k$ 之后，答案要么是 $\frac{k(k + 1)}2$ 要么是 $\max t_i$ 。且容易排序后 $O(n)$ check 答案能否达到前者。根据 check 的过程感性理解单调性。写了个二分发现过了，还是比较 Hard 的题。

现在已经开香槟了，自然跑回去 0.5h 写完 T1，耗时 3h AK。

开局所有题看了一遍，发现三个 $10^9 + 7$ ，比较高兴。

T1 仙人掌，T2 神秘期望，先跳掉。

发现 T3 容斥做到 $O(n^2)$ 是简单的，并且这个东西很好维护，感觉很有前途。

写了一个 $O(n^2)$ 确认正确性，然后成功了。发现优化也是 Easy 的，直接线段树 + 扫描线可以 $O(n \log n)$ ，但是写完之后已经过了 2h。

仔细想了一下 T2，发现可以 $O(n^3)$ 区间 dp。因为并没有出现卷积的形式，所以可以前缀和优化到 $O(n^2)$ 。写完之后已经是 3.5h 了。

最后手模了一下 T1，感觉应该也可以在圆方树上 dp，但是细节比较多，只能两个题遗憾离场了。