USACO 2022 February Contest

发表于

USACO 2022 February Contest Silver and Gold.

Silver

Problem 1. Redistributing Gifts

题意

Farmer John有 $n$ 只奶牛，$n$ 个礼物，编号均为 $1\sim n$。现在要给每只奶牛分配一个礼物。

每只奶牛都有一个长度为 $n$ 的排列，表示她的愿望清单。其中第 $i$ 个值表示这只奶牛第 $i$ 想要的礼物。

Farmer John很懒，将第 $i$ 个礼物给了第 $i$ 只奶牛。现在奶牛聚在一起重新分配礼物。一个合法的分配当且仅当对于所有的 $i$，第 $i$ 只奶牛有且仅有一个礼物，且这个礼物的在这个奶牛心目中的排名需不低于这只奶牛原来的礼物（即编号为 $i$ 的礼物）的排名。

你需要对于所有的 $i$，求出所有可能的合法分配中，第 $i$ 只奶牛可能分配到的最想要的礼物。

$n\le 500$。

题解

我们先假设第 $i$ 个礼物给第 $i$ 只奶牛。

暴力枚举 $i,j$，假设第 $i$ 只奶牛想要第 $j$ 个礼物，如何判断是否可行呢？

我们将第 $j$ 个礼物给了 $i$，那么第 $j$ 只奶牛就没礼物了，他需要找另一个合法的礼物 $x_1$；

我们将第 $x_1$ 个礼物给了 $j$，那么第 $x_1$ 只奶牛就没礼物了，他需要找另一个合法的礼物 $x_2$；

这样一直下去，直到某一只奶牛拿回了礼物 $i$。这样就找到了一个满足条件的合法匹配了。

那么我们新建一个图，若奶牛 $i$ 的愿望清单中礼物 $j$ 的排名比礼物 $i$ 优，则 $i$ 向 $j$ 连一条有向边。

判断奶牛 $i$ 是否能要礼物 $j$ 相当于判断是否存在一条从 $j$ 到 $i$ 的路径。

Floyd传递闭包，时间复杂度 $O(n^3)$。

可以用bitset继续优化，但是没有必要。

Problem 2. Robot Instructions

题意

给定 $n$ 个向量 $(x_i,y_i)$。对于每个 $k$，问你有多少种从 $n$ 个向量中选出 $k$ 个向量的不同方案，使得这 $k$ 的向量的横纵坐标之和等于 $(x_g,y_g)$。

$n\le 40,|x_i|,|y_i|\le 10^9$。

时限4s，空间512MB。

题解

$n\le 40$，启发我们将向量尽量平均分成两部分。设分为 $[1,t],[t+1,n]$。

对于前面一半，设 $f_{i,P}$ 表示选择 $i$ 个向量后，坐标之和为 $(x_P,y_P)$ 的方案数。

$P$ 最后只有 $2^t$ 种不同的情况，将 $P$ 哈希即可。

对于后面一半，暴力枚举每个向量选择的情况，假设选了 $j$ 个向量，最终前半部分的坐标应为 $Q$（$Q$ 可以通过用终点坐标减去这 $j$ 个向量求出），那么枚举 $i$，将 $i+j$ 的答案加上 $f_{i,Q}$ 即可。

时间复杂度 $O(2^t+2^{n-t}t)$。

取 $t=\frac{n}{2}$ 就可以过了。

Problem 3. Email Filing

题意

Farmer John 要处理邮件。屏幕左侧是 $m$ 个文件夹，他需要将位于屏幕右侧的 $n$ 封邮件归类进左侧的文件夹中，其中，从上往下第 $i$ 封邮件需要进入左侧从上往下第 $f_i$ 个文件夹中。

由于屏幕大小有限，每次只能看到最多 $k$ 个文件夹，$k$ 封邮件。其中 $k\le \min{n,m}$。刚开始时，他看到的是编号为 $1\sim k$ 的文件夹和邮件。他需要上下滚动鼠标滚轮，每次滚动会将位于屏幕最上方的文件夹（或邮件）移出屏幕，而屏幕下方的下面第一个文件夹（或邮件）将出现在屏幕最下方。每个邮件移动完后，邮件的图标将消失，同时下一个（如果有的话）标号的邮件将出现在屏幕上。

不幸的是，这个鼠标的滚轮只能往下滚动。唯一能看到还未处理的邮件的方法是滚到最下面后整理完某个屏幕中的邮件，这时上面第一个未处理的将出现在屏幕中。

你需要告诉Farmer John 能否处理完这批邮件。

$n\le 10^5,m\le 10^4$。

题解

考虑贪心。设 $mx$ 表示 $f_i$ 的最大值，设当前文件夹的区间为 $[now,now+k-1]$。

首先，需要搞清楚的是，$now$ 是不能减小的，也就是左侧只能一直往下。

设当前在屏幕上方的第一个邮件为 $j$，如果 $f_j\in[mx-k+1,mx]$，则可以跳过 $j$，等最后搞。

否则，对于当前的情况，能整理则整理，也就是处理完当前所有满足 $f_k\in[now,now+k-1]$ 的邮件。

若当前没有一个能整理的，设当前显示的邮件中 $f$ 最小的为 $u$，则有三种情况：

  • 若 $f_u<now$，那就别想了，永远都搞不了这个 $u$。

  • 移动左侧文件夹，直至 $now+k-1=f_u$；如果这时移动，则必须满足剩下的还未处理的邮件的 $f$ 都必须大于新的 $now$（即 $f_u+1-k$），否则：

  • 先不处理，看看后面的情况，也就是将当前最上方的先去掉。

上述过程可以开若干个set去模拟，并用一个vector顺序记录上方还未处理的邮件。

当右侧到达底部时，只需类似上面的方法，判断能否消完即可。

时间复杂度 $O(n\log n)$。

Gold

Problem 1. Redistributing Gifts

设 $g(S)$ 表示在 $S$ 中形成一个合法环的方案数。

设 $f(S)$ 表示在 $S$ 中形成若干个合法环的方案数。

答案为 $f(S)\times f(\complement_US)$。

时间复杂度 $O(2^nn^2)$ 或 $O(3^n)$。

Problem 2. Cow Camp

每次出现恰好 $i$ 个的概率 $P(i)=\frac{\binom{n}{i}}{2^n}$。

考虑递推，设 $f_i$ 表示用 $i$ 次的最大期望，

则有：$f_k=\sum_{i=0}^nP(i)\times \max{i,f_{k-1}}$。初始条件 $f_0=0$。

记录 $P(i)$ 前缀和 $s_i$，$iP(i)$ 后缀和 $t_i$ 即可 $O(k)$ 解决。

可以发现，这个东西相当于 $f=s_if+t_{i+1}$ 迭代若干遍，其中 $i=\lfloor f\rfloor$。

而 $i$ 最多是 $n$，那么可以二分出最少迭代次数，使得迭代后 $i$ 将会变化。

迭代 $k$ 次后的 $f$ 为 $s^k\times f+\frac{1-s^k}{1-s}\times t$。

二分+快速幂即可。

时间复杂度 $O(n\log^2 k)$。

Problem 3. Moo Network

贪心可知，对于每个纵坐标，一个点只可能往左/右边第一个连边。

剩下的是最小生成树模板。

时间复杂度 $O(m\log m)$，其中 $m=20n$。