USACO 2023 December Contest 银组题面

T1

农民约翰决定让他的牛表演一些杂技！首先，FJ称了一下他的牛，发现有N（1≤N≤2*10^5）种不同的体重。特别是，对于每个i∈[1,N]，有ai头牛的体重为wi（1≤ai≤10^9,1≤wi≤10^9）。 他最受欢迎的特技表演包括牛形成平衡的塔。一座塔是一系列牛，其中每头牛都堆叠在下一头牛的顶部。如果每头牛的体重至少比它正上方的牛的体重大K（1≤K≤10^9）倍，则这座塔是平衡的。任何一头牛最多只能参与一个平衡塔。 如果FJ想创建最多M（1≤M≤10^9）个平衡的牛塔，那么最多有多少头牛可以参与某个塔？

T2

农民约翰有N个谷仓（3≤N≤5×10^5），其中有K个（3≤K≤N）谷仓是相互连接的。 首先，安纳贝尔给每个谷仓分配一个在[1,N]范围内的不同整数标签，并观察到标签为a1，…，aK的谷仓是按此顺序连接的环。即谷仓ai和ai+1（对于所有1≤i接下来，贝茜也给每个谷仓分配一个在[1,N]范围内的不同整数标签，并观察到标签为b1，…，bK的谷仓是按此顺序连接的环。所有的bi都是不同的。 有些（可能没有或全部）谷仓被安纳贝尔和贝茜分配了相同的标签。计算被安纳贝尔和贝茜分配了相同标签的最大谷仓数。

T3

贝西是一只机器牛，也被称为牛形机器人。它在一个数轴上，试图射击一系列位于不同位置的目标。贝西从位置0开始，遵循长度为C（1≤C≤105）的命令字符串，每个命令为L，F或R： L：贝西向左移动一个单位。 R：贝西向右移动一个单位。 F：贝西开火。如果贝西的当前位置有目标，则击中并摧毁目标，目标不能再被击中。 如果在贝西开始遵循字符串之前，允许你将字符串中的最多一个命令更改为不同的命令，那么贝西最多可以击中多少个目标？