杂题总结 Vol.4

试题总结 2

Status: OPEN

\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单，10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等，能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难，独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难，独立思考只能想出 \(50\%\) 以下

USACO24JAN [2024-09-26]

P10134 [USACO24JAN] Cowmpetency S

\(\HD\)

细节较多的贪心题。但是仍然是一道非常不错的题目。

考虑要发现如下性质：以下“区间”均指代 \([a_i,h_i]\)

1. 若有互相包含的区间则不存在

2. 若有互相相交（可以共端点）则不合法。特别地，右端点是同一个值的情况是不算的。

3. 对于右端点是同一个值的情况，保留最大的一个不影响答案

考虑采用反悔贪心，将右端点重复的区间去重之后按照左端点排序。考虑我们需要限制一个前缀的最大值的最小值，我们发现：

• 对于 \([a_i,h_i]\) 若 \(a_i\) 前面没有可以调整的数（i.e. \(\forall j\le a_i,c_j\neq 0\)），则无解

• 否则如果 \(\max_{j\in[1,a_i]}<\max_{j\in(a_i,h_i)}c_j\) 只需要将最后一个 \(0\) 的下界以 \(\max_{j\in(a_i,h_i)}c_j\) 更新，记该下界为 \(req_j\)

然后你就会发现你 WA 了。。

重新观察以上步骤，如果之前已经限制过 \(c_i\ge req_i\)，那么这个限制值也要考虑在内，若当前扫描到第 \(i\) 个区间，记 \(s=\max_{j\in[1,a_i]}req_j\)，则当 \(\max\{s,\max_{j\in[1,a_i]}\}<\max_{j\in(a_i,h_i)}c_j\) 才将上一个 \(0\)（位置记作 \(x\) ）的 \(req_x\) 值以 \(\max_{j\in(a_i,h_i)}c_j\) 更新，然后令 \(s\leftarrow \max\{s,req_x\}\)。

P10135 [USACO24JAN] Potion Farming S

\(\EZ\)

考虑有贪心结论：

1. 最小遍历次数为叶子数量。

2. 最优药水数量可以这样构造：从下往上收集药水，优先消耗子树中叶子数量收集更深的药水。

考虑原因。由于越深的药水 \(y\) 就越少有叶子能够收集他，而若有药水 \(x\) 是 \(y\) 的祖先，那么显然能够收集 \(y\) 的叶子必然能够收集到 \(x\)，如果最优方案是放弃 \(y\) 而收集 \(x\)，那么用能够收集 \(y\) 的叶子改为收集 \(y\) 必然不劣，因为这样其他更浅的叶子就有了利用的机会。

P10136 [USACO24JAN] Cowlendar S

\(\HD^{+}\)

缺了一步，想到做差和枚举因数，但是没想到抽屉原理。

有一个巧妙的想法，那就是如果我们考察两个数的差值，那么应该把原序列能够分成三组，每一组当中两两的差都是可能的 \(L\) 的倍数。

但是，难蚌的是，你不可能枚举哪两个是可能的同余的数。

由于取模形成了一个有限的空间，我们常常要考虑抽屉原理。如果有四个不相同的数，那么在合法的方案下，一定有两个数是同余的，那么我们只需要尝试 \(6\) 个可能的差值然后用试除法枚举因数， \(\mathcal O(n)\) 检验即可。

其实难点主要在于第一步转化

P10137 [USACO24JAN] Walking in Manhattan G

\(\HD\)

有一个观察是：实际上奶牛遇到奇数长度的边的时候就会转向。

另一个观察是：奇数边都是一排一排一列一列出现的。

那么我们可以对每一个询问采用倍增。