杂题总结 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]\)
-
若有互相包含的区间则不存在
-
若有互相相交(可以共端点)则不合法。特别地,右端点是同一个值的情况是不算的。
-
对于右端点是同一个值的情况,保留最大的一个不影响答案
考虑采用反悔贪心,将右端点重复的区间去重之后按照左端点排序。考虑我们需要限制一个前缀的最大值的最小值,我们发现:
-
对于 \([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\)
考虑有贪心结论:
-
最小遍历次数为叶子数量。
-
最优药水数量可以这样构造:从下往上收集药水,优先消耗子树中叶子数量收集更深的药水。
考虑原因。由于越深的药水 \(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\)
有一个观察是:实际上奶牛遇到奇数长度的边的时候就会转向。
另一个观察是:奇数边都是一排一排一列一列出现的。
那么我们可以对每一个询问采用倍增。
标签:总结,端点,收集,Vol.4,USACO24JAN,text,药水,杂题,HD From: https://www.cnblogs.com/haozexu/p/18433542