【总结】USACO2017 - 2022 P

本来打算 2022 赛季结束后再写,还是先写了免得以后麻烦(

题目按难度递增(个人感觉

[USACO19DEC]Greedy Pie Eaters P

区间 DP,一个小 trick 是预处理在被区间 \([l,r]\) 包含的经过点 \(k\) 的最大值。

[USACO20FEB]Equilateral Triangles P

曼哈顿距离转切比雪夫距离,然后简单统计一下即可

[USACO20JAN]Non-Decreasing Subsequences P

解法较多。可以直接分治合并答案,复杂度 \(\mathcal{O}(NK\log N + QK)\)。

直接写成矩阵形式,然后求矩阵乘法前缀和和逆矩阵的前缀和就可以做到 \(\mathcal{O}(NK^3+QK)\)

[USACO20JAN]Cave Paintings P

连通块 DP,以连通块为状态,用并查集维护连通块,在合并的时候归并答案。

这题我们将水平面从低到高枚举,然后每次合并连通块即可。最后剩下连通块的答案的乘积就是答案。

[USACO19DEC]Bessie's Snow Cow P

有意思的树上 DS。

首先我们先求出 DFS 序。对于每个颜色,我们维护一个 set 记录有哪些点的子树被染色了,注意一个 set 里不存在祖先后代的关系。然后开一个树状数组维护每个点的值,用以回答询问。

对于修改操作,我们要先判断对应颜色的 set 里是否有 \(x\) 的祖先,显然如果存在,一定是 \(dfn[x]\) 在 set 的前驱(不难反证)。存在我们直接忽略这次询问,否则我们在 set 里删除 \(x\) 的后代,在 set 求后继即可。

[USACO21DEC] HILO P

直接 DP,定义状态 \(f_{i,j,0/1}\) 表示 \(x\) 前面到了 \(i\),\(x\) 后面到了 \(j\) 的排列数,上一个数在 \(x\) 前面/后面的方案数。直接转移是 \(\mathcal{O}(N^3)\),可以前缀和优化到 \(\mathcal{O}(N^2)\)。

事实上,求所有排列的权值和,等价于求排列的期望然后 \(\times N!\),这两类问题本质上是等价的。对于本题来说,求期望 DP 会简单很多,复杂度也是 \(\mathcal{O}(N^2)\)。

[USACO22JAN] Minimizing Haybales P

我们从 \(1\) 到 \(N\) 枚举每一位,求出能移过来的最小的数。一个数能移过来的充要条件是前面不存在一个数和 \(h_i\) 的差 \(>k\)。

所以我们可以对每个 \(i\) 扫一遍求得最优的位置 \(x\),删除 \(x\) 后继续求下一位。这样我们就得到一个 \(\mathcal{O}(N^2)\) 的算法。

考虑用 数据结构优化这个算法,我们开线段树维护区间最大值和最小值,然后维护集合 \(S\) 表示在当前区间中能移动到最前面的集合,维护集合 \(T\) 表示不能移动到最前面的集合。注意这里 \(S,T\) 并不互补,\(T\) 表示的是子区间中能移动到最前面,但当前区间不行的集合。

每个数最多进入 \(S,T\) \(\log N\) 次,总的时间复杂度 \(\mathcal{O}(N\log^2 N)\)。

[USACO20FEB]Delegation P

题面中既有最大,又有至少,首先考虑二分答案。

二分之后我们看是否存在一种划分链的方案。

细节上的贪心比较毒瘤,不注意的话自己哪里错了都不知道

[USACO18OPEN]Disruption P

给定一个树,\(m\) 次操作每次将链上所有边对给定值 \(w_i\) 取 \(\max\),最后求树上每条边的权值。

直接树剖可以 \(\mathcal{O}(N\log ^2 N)\)。由于是静态问题,树上差分后线段树合并可以做到 \(\mathcal{O}(N\log N)\)。

[USACO19JAN] Train Tracking 2 P

显然,如果 \(c_i < c_{i + 1}\),那么第 \(i\) 个区间的左端点一定是 \(c_i\),同理如果 \(c_{i}>c_{i+1}\),那么第 \(i + 1\) 个区间的右端点一定是 \(c_{i + 1}\)。

对于每一个 \(c_{i}\) 相等的段,得到一个子问题:区间 \([1,n]\) 中每个数为 \([c_i,10^9]\),每个位置的 \(K\) 的范围内至少有一个 \(c_i\),直接 DP 即可 \(\mathcal{O}(N)\) 求得答案。

[USACO18FEB]New Barns P

经典结论,我们只用维护每个连通块的直径的两端即可。查询就是比较到直径两端的距离,加点就是求得新的直径两端,一定是原来两个端点和新点中的两个。

所以我们的问题就是快速求两点的距离,直接树上倍增。时间复杂度 \(\mathcal{O}(N\log N)\)。

[USACO18FEB]Cow Gymnasts P

数数思维题。

我们不妨将序列中的最大值记作 \(X\),如果位置 \(i\) 为 \(X\),那么位置 \(i - X + 1\) 也必须是 \(X\)。因为只有它前面的 \(X - 1\) 个数能到达位置 \(i\),所以它前面的 \(X - 1\) 都必须到达位置 \(i\),同时我们也发现 \(i - X + 1\) 和 \(X\) 之间的数都至少为 \(X - 1\)。

所以我们枚举最大值,计算 \(\gcd (X, N)\),得到有多少个位置必须为 \(X\),剩下的数可以 \(X\) 和 \(X - 1\) 任选,但是必须是循环的。

一番推导后简化为求 \(\sum \limits_{i = 1} ^ {n - 1}2 ^{\gcd(n, i)}\),经典欧拉函数题,直接 \(\mathcal{O}(\sqrt{N})\) 计算即可。

[USACO18FEB]Slingshot P

经典二维偏序,离线后线段树,时间复杂度 \(\mathcal{O}(N\log N)\)。

[USACO18JAN]Sprinklers P

经典单调栈,先单调栈求出可行的格子的范围,再单调栈扫一遍求出答案。

[USACO18DEC]The Cow Gathering P

树上思维题。

判断 \(x\) 是否能最后一个删,就是以 \(x\) 为根建一颗内向树,然后连边 \(a_i\to b_i\),判断是否有环即可。

所以如果 \(a_i\) 是 \(b_i\) 祖先则无解。所以我们先将所有 \(a_i\) 一侧的子树上的点标记为无解。

关键结论:对于没有标记的节点,要么全部有解,要么全部无解。

首先,没有被标记的点一定连通,因为我们每次标记的是一颗子树。

现在我们假设有一个点有解,那么与之相邻的点一定有解,这两个点记作 \(s, t\)。

假设原先解的序列是 \(A tB s\),那么将 \(t\) 移动到最后得到 \(AB st\) 也是合法序列。两个序列中相对顺序变化的只有 \(t\) 和 \(Bs\),因为 \(t\) 没有被标记,所以不存在限制条件 \(t\) 比某个点先删,所以 \(ABst\) 也是合法序列。

[USACO19JAN]Exercise Route P

本质上是给定若干路径,问有多少对路径有交。

我们将所有路径按 \(lca\) 分类,然后讨论 \(lca\) 相同和不同的两种情况即可,时间复杂度 \(\mathcal{O}(N\log N)\)。

[USACO19FEB]Cow Dating P

很厉害的结论题。

直接写出区间 \([l,r]\) 的答案为 \(\sum\limits_{i = l }^{r} \dfrac{p_i}{1-p_i}\prod\limits_{i = l}^r (1 - p_i)\),大概就是 \(\sum a_i \times \prod b_i\) 的形式。

这玩意看起来就非常难优化。

结论,对于固定的左端点 \(l\),随着右端点 \(r\) 的变化,区间 \([l,r]\) 的答案是关于 \(r\) 的单峰函数。

我们假设区间 \([l,r + 1]\) 的答案比 \([l,r]\) 的答案更优,可以求得 \(\sum \limits_{i = l}^r\dfrac{p_i}{1 - p_i} < 1\),所以只要 \(\sum a < 1\) 我们一直将右端点向右移动即可。时间复杂度 \(\mathcal{O}(N)\)。

其实也不用这么强的结论,我们猜测它有决策单调性,直接 1d1d 优化可以做到 \(\mathcal{O}(N\log N)\)。

[USACO18JAN]Lifeguards P

如果区间 \([l_i,r_i]\) 被另一个区间包含,那么当前区间可以直接去掉。这样预处理后,我们可以得到一个 \(l_i\) 和 \(r_i\) 都递增的序列。

这样我们就可以直接设计状态 \(f_{i,j}\) 表示选到了 \(i\) 且选择了第 \(i\) 个区间,去除了 \(j\) 个区间的答案。

直接转移是 \(\mathcal{O}(NK^2)\) 勉强能过。也可以单调队列一下就是 \(\mathcal{O}(NK)\)。

[USACO20FEB]Help Yourself P

先将所有区间按右端点排序。考虑依次加入每个区间。

\(f_i\) 表示覆盖的最后一个点为 \(i\) 的答案。对于当前区间 \([l,r]\),直接继承 \(l \le i \le r\) 的 \(f_{i}\),

对于 \(i<l\),答案由 \(\sum x ^ k\) 变成 \(\sum (x +1)^k\),直接二项式定理强拆即可。

对于 \(i<l\) 的条件我们用线段树维护,时间复杂度 \(\mathcal{O}(NK\log N + NK^2)\)。

[USACO20JAN]Falling Portals P

把每个世界写成一条直线,显然我们就是在直线交点传送,每次走的肯定是凸包。

所以我们维护凸包,然后倍增优化转移即可,时间复杂度 \(\mathcal{O}(N\log N)\)。

细节蛮多的,需要一点耐心。

[USACO18OPEN]Out of Sorts P

经典算贡献题。

不难发现 quickish_sort 函数里面的 do_while 是无效的,因为冒泡一次后最后一位一定会还原。

所以我们要求的等价于递归层数。我们考虑计算每一位递归了多少层,这等价于求每个位置 \(i,i+1\) 之间什么时候出现分隔点。

对于第 \(i\) 个分隔点,我们看在 \(1\sim i\) 中最后面的数前面有多少个 \(>i\) 的数,这就是断点出现的时间。

[USACO21OPEN] United Cows of Farmer John P

求有多少三元组 \((l,k,r)\),满足 \(l < k < r\) 且 \(b_l, b_k,b_r\) 在区间 \([l,r]\) 只出现了一次。

考虑枚举右端点 \(r\),左端点的取值为 \([pre_r + 1,r - 2]\)。

同时对于每个 \(x\),对于 \([pre_x + 1,x - 1]\) 的左端点产生 \(1\) 的贡献,用线段树维护即可。

条件很多,维护的标记需要一些思考。

[USACO21OPEN] Balanced Subsets P

观察到满足条件的子集,左边界先减后增,右边界先增后减。所以我们设计状态 \(f_{i,l,r,0/1,0/1}\) 表示到了第 \(i\) 行,第 \(i\) 行选的是区间 \([l,r]\),左边界减/增,右边界增/减的方案,直接转移是 \(\mathcal{O}(N^5)\),可以二维前缀和优化至 \(\mathcal{O}(N^3)\)。

[USACO21DEC] Tickets P

答案肯定是分别从 \(1,n\) 跑最短路的和,但是边数是 \(NK\) 级别的,可以线段树优化至 \(\mathcal{O}(K\log N)\) 然后跑最短路。

[USACO19JAN]Redistricting P

基础 DS 优化 DP,直接写出状态 \(f_i\) 表示前 \(i\) 个位置的最小答案,然后线段树优化一下即可 \(\mathcal{O}(N\log N)\)。

[USACO20DEC] Sleeping Cows P

非常腻害的 DP,首先对牛和牛棚按权值排序,对于一个牛棚可以匹配牛序列的一个前缀。

因此如果有一头牛没有匹配,它后面的牛棚必须全部匹配,所以我们只关心第一头没有匹配的牛位置。

为了简化状态,我们把牛和牛棚放到一起排序,然后定义状态 \(f_{i,j,0/1}\) 表示考虑到第 \(i\) 个位置,有 \(j\) 头牛等待匹配,前面是否有牛放弃匹配的方案数。

本质思想就是把牛和牛棚的匹配分开,先将牛加入候选集合,然后再用牛棚在集合里匹配。

[USACO21DEC] Paired Up P

有点类似的题目,求最大的和最小的极大匹配。

最大的极大匹配一定是最大匹配,直接 \(\mathcal{O}(N^2)\) DP 即可。

最小的极大匹配,我们只关心最近的没有匹配的牛的位置,所以可以先设计状态 \(f_{i,j,k}\) 表示 \(H\) 匹配到了 \(i\) 且 \(G\) 匹配到了 \(j\),上一头没有匹配的牛是第 \(k\) 头,直接转移即可做到 \(\mathcal{O}(N^3)\)。

事实上我们可以只关心最后放弃匹配的牛是 \(H/G\),这样我们得到状态 \(f_{i,j,H/G}\),可以直接在后面再放弃一个相同的牛。

但是我们需要考虑 \(f_{i,j,H/G} \to f_{i',j',G/H}\),先预处理 \(i,j\) 后面能连续匹配多少个,如果将这些匹配之后的位置超出了和 \(i/j\) 的匹配范围,那么我们就可以转换颜色。

转移是 \(\mathcal{O}(1)\) 的,总的时间复杂度 \(\mathcal{O}(N^2)\),细节比较多。

[USACO22JAN] Counting Haybales P

对于两个位置 \(i,j\),如果 \(|a_i - a_j| >1\),那么它们的相对位置一定不会改变,所以我们可以拆出奇数序列和偶数序列,然后将两个序列归并求出答案。

虽然解法很简单,但是思维难度不低。

[USACO22JAN] Multiple Choice Test P

闵可夫斯基和模板题,将所有凸包合并后即为答案。

闵可夫斯基和的定义是两个凸包对应的向量两两相加,得到一个新的凸包。可以直接归并两个凸包求得。

[USACO21FEB] No Time to Dry P

模拟一下,如果 \(i\) 和 \(pre_i\) 之间不存在更浅的颜色,那么可以少用一种颜色。所以预处理区间最小值,将询问按右端点大小排序,扫一遍即可。

[USACO18DEC]Balance Beam P

结论题,答案是所有点构成的凸包。

感性证明一下。我们可以写出转移式子 \(E(x) = \max\{f(x), \dfrac{E(x + 1) + E(x - 1)}{2}\}\)。

所以有 \(E(x) \ge f(x)\),我们将 \(f(x)\) 带入式子就有 \(E(x) \ge \max\{f(x), \dfrac{f(x + 1) + f(x - 1)}{2}\}\) 。

所以我们可以令 \(f(x) = \max\{f(x), \dfrac{f(x + 1) + f(x - 1)}{2}\}\),这相当于迭代,经过无数次迭代,原图不存在下凸壳,即为凸包。

[USACO19FEB] Mowing Mischief P

两问,先求出最多能选多少个点,然后在最多个点的基础上使面积最小。

第一问就是求 \(LIS\),我们先按求出的 \(f\) 大小分层。

然后对每一层 DP 求出最小面积,直接转移时间复杂度 \(\mathcal{O}(N^2)\)。

不难发现 DP 的转移是有决策单调性的,可以优化至 \(\mathcal{O}(N\log N)\)。

但是两层之间并不是所有点对都能转移,每个点对应上一层中的一个连续区间,所以将区间拆成线段树若干个区间,然后跑 DP,时间复杂度是 \(\mathcal{O}(N\log ^ 2 N)\)。

[USACO18DEC]Sort It Out P

选出排序的集合 \(S\),对于不在 \(S\) 中的点的相对顺序一定不会改变,所以不在 \(S\) 中的点必须是升序。

在 \(S\) 中的点,因为我们可以无数次 check,所以一定会归位,题目转化为求第 \(K\) 大的 LIS。

直接先跑 LIS 计数,然后枚举每一位即可。但是 LIS 数量可能非常巨大,我们需要对 \(K\) 取 \(\min\)。所以我们需要不适用减法求出方案,可以用树状数组维护。

[USACO19OPEN]Valleys P

按高度依次加入每个点,我们要求的就是没有洞的连通块的大小之和。

连通块非常简单,但难点在于如何判断一个连通块是否有洞。

事实上我们可以维护正反角的个数,对于没有洞的连通块 正角 \(-\) 反角 \(= 4\)。

下面分别是正角和反角,\(0\) 表示空,\(1\) 表示山。

?0 11
01 10

可以旋转 \(0/90/180/270\) °。

并查集维护正角反角和 size,时间复杂度 \(\mathcal{O}(NM\log)\)。

[USACO19FEB]Moorio Kart P

对于每个棵树求出所有路径长度,然后直接跑背包即可。

背包总和大于 \(Y\) 直接对 \(Y\) 取 \(\min\) 即可。

[USACO18JAN]Cow at Large P

对于每个点预处理离它最近的叶子的距离为 \(f_x\)。

求点 \(x\) 的答案,我们以 \(x\) 为树根,对于所有 \(d_x \ge f_x\) 且所有祖先节点都不产生贡献的点会产生贡献 \(1\)。

同时一棵子树的所有点的 \(deg\) 之和等于 \(2(sz - 1) + 1\),所以 \(\sum 2 -deg = 1\),等价于对于所有 \(d_x \ge f_x\) 的所有点产生 \(2 - deg\) 的贡献。转化为树上求所有二元组 \((u,v)\) 的贡献,直接点分治。

[USACO21JAN] Sum of Distances P

新图的一条路径等价与每一张原图都有 \(1 \to v_i\) 的距离为 \(x\) 的路径。

所以对于没一张原图,我们只关心奇偶最短路。

我们要求的是奇偶最短路中较短的一条,就是 \(\min\{\max\{d_0,v_i\},\max\{d_1,v_i\}\}\)。

\(\min\) 套 \(\max\) 不方便计数,将 \(\min\max\) 转化,\(min\{a,b\} = a + b - \max\{a,b\}\) 即可。

[USACO21FEB] Minimizing Edges P

比较类似,对于一张图,我们只关心奇偶最短路。我们将每个点记为 \((a,b)\) 表示两条最短路的长度。

那么每个点必须同时与 \((a - 1, b + 1),(a + 1, b - 1)\) 或者与 \((a - 1, b - 1)\) 相连。贪心的和 \((a - 1, b - 1)\) 连,如果必须和 \((a-1, b+ 1)\) 连则优先连 \((a +1, b-1)\)。

[USACO21FEB] Counting Graphs P

难度很高的数数题。同上题我们先求出每个点 \((a,b)\)。

定义状态 \(f_{i,j}\) 表示选到了 \((a_i,b_i)\),后面必须有 \(j\) 条边连过来。

然后分两步转移,首先考虑向 \((a-1,b+1)\) 连,求出 \(g_{i,j}\) 表示选到了 \((a_i,b_i)\) ,有 \(j\) 条边和 \((a-1, b+1)\) 相连。然后转移 \(g_{i,j}\to f_{i,k}\)。

[USACO21OPEN] Routing Schemes P

BEST 定理,求欧拉回路的路径数量。

定理:对于图 \(G\),求出以 \(x\) 为根的内向树数量(矩阵树定理),然后答案 \(\times deg_{x}\times \prod (deg_i-1)!\) 即为答案。

[USACO20DEC] Spaceship P

高维 DP。我们定义状态 \(f_{x,y,z}\) 表示从路径 \(x \to y\),最大的数 \(\le z\) 的方案。直接转移可以做到 \(\mathcal{O}(QN^4)\)。

考虑对询问拆点,将每个询问拆成一个入点一个出点,然后跑 DP,可以做到 \(\mathcal{O}((Q+N)^2N^2)\)。

[USACO19DEC]Tree Depth P

一道不简单的数数思维题。

我们要统计对于所有排列的深度之和,直接做非常不方便。而数数题一般将条件化简,或找到等价的容易处理的条件。

这里求深度,等价于枚举一个点的祖先,它的祖先个数 \(+1\) 就是它的深度。这样问题转化为求数对 \((u,v)\) 的贡献,即有多少排列使得 \(v\) 是 \(u\) 的祖先。

如果 \(v\) 是 \(u\) 的祖先,等价于 \(a_v < a_u\),且 \(u,v\) 之间没有小于 \(a_v\) 的数。

如果不考虑其它限制条件,先求有多少个排列恰好有 \(K\) 个逆序对。这是一个经典题目,直接定义状态 \(f_{i,j}\) 表示长度为 \(i\) 的逆序对数为 \(j\) 的排列个数。枚举最后一位的 \(i\) 种选择,分别是逆序对增加 \(x\in[0,i - 1]\) 个,典型的背包模型,可以前缀和优化至 \(\mathcal{O}(N^3)\)。

现在有 \((u,v)\) 的限制条件,我们可以先固定 \(u,v\) 之间的数,再固定 \(u,v\),最后固定外面的数。不难发现除了位置 \(v\),其余的数可以随便填,和上面的转移一模一样。对于位置 \(v\),如果在 \(u\) 后面,一定会产生 \(v-u\) 个逆序对,否则一定不产生逆序对。

所以我们先跑 DP 求出 \(f\)。然后枚举 \(v-u\),然后在背包中撤销 \((v-u)\),撤销后的 \(f_{n - 1,K-\max(0,v-u)}\) 就是我们要求的贡献。

时间复杂度 \(\mathcal{O}(N^3)\),代码没有一次乘法和取模,跑的飞快。

[USACO21JAN] Minimum Cost Paths P

\(L_2\) 问题模板,偏序集为单链。

这里的 \(y_i\) 表示第 \(i\) 列移动到第 \(i + 1\) 列时的行号,因为行号和列号不减,所以 \(y_i\) 不减,即偏序集为单链。

\(L_2\) 均值是加权平均数

[USACO20DEC] Cowmistry P

异或问题,先建立 Trie 树。问题转化为求树上三个点使之满足条件。

大力讨论即可,由于值域很大,我们不可能开这么多点,可以将满二叉树缩成一个点。

[USACO21JAN] Paint by Letters P

求子矩阵的同色连通块数。

对于相邻同色的格子连边,等价于求连通块数。

由于是平面图,有定理 \(F=E-V+C+1\)。

\(F,E,V,C\) 分别为面数,边数,点数和连通块数。

唯一不好求的是 \(F\),我们将每个面标号,然后枚举边界将不满足的面减掉。

时间复杂度 \(\mathcal{O}(NM + Q(N + M))\)。

上一篇:Git入门学习(二)基础操作


下一篇:信息熵 交叉熵 KL散度