USACO竞赛第一场月赛题目解析

第一题 糖果盛宴

题目描述:

农夫约翰的奶牛很爱吃甜食，它们特别喜欢吃甘蔗糖！FJ有N头牛，每头牛都有一定的初始身高，他想喂它们M每根也有不同高度（1≤N，M≤2·10^5)。

按照它们在输入中的顺序，FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖，他会把甘蔗糖挂起来，这样甘蔗糖一开始就刚好碰到地面。然后，奶牛将按照输入的顺序一头接一头地排队，走到甘蔗糖前，每头牛都吃到自己的高度（因为它们不能再高了）。即使在奶牛吃掉糖果棒的底部后，糖果棒也会悬挂在最初设置的位置，不会下降到地面。如果甘蔗的底部已经超过奶牛的高度，那么奶牛在轮到它的时候可能什么都不吃。轮到每头牛后，奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加，农民约翰挂上下一根甘蔗糖，奶牛再次重复这个过程（第一头牛再次成为第一个开始吃下一根拐杖糖的人）。

第一题 Bovine Acrobatics

题目描述:

农场主约翰决定让他的奶牛表演一些杂技！首先，约翰称了一下他的奶牛，发现它们有 N（1≤N≤2⋅10*5）个不同的重量。特别是，对于每个 i∈[1,N]，他的牛中有 ai 重量为 wi（1≤ai≤10**9,1≤wi≤109）。

他最受欢迎的绝技是让奶牛组成平衡塔。塔是一连串的奶牛，每头奶牛都叠在下一头奶牛的上面。如果每头牛与正上方的牛的重量至少比正上方牛的重量大 K（1≤K≤10**9），那么这个塔就是平衡的。任何一头牛最多只能成为一个平衡塔的一部分。

如果 FJ 想创建最多 M 个（1≤M≤10**9）平衡的牛塔，那么最多有多少头牛可以成为某个牛塔的一部分？

第二题 Cycle Correspondence

题目描述:

农场主约翰有 N 个谷仓（3 <= N <= 5.10**5），其中有 K（3 <= K <= N）对不同的谷仓相连。

首先，安娜贝尔给每个谷仓分配一个范围为[1，N]的不同整数标签，并观察到标签为 a1...ak 的谷仓依次循环连接。也就是说，在所有 1 <= i < K 的情况下，谷仓 ai 和 a(i+1) 是相连的，谷仓 ak 和 a1 也是相连的。接下来，贝西还为每个谷仓分配了一个范围为[1，N]的不同整数标签，并观察到标签为 b1，...bk 的谷仓依次连接成一个循环。所有 bi 都是不同的。

安娜贝尔和贝西给某些（可能没有或全部）谷仓分配了相同的标签。计算被安娜贝尔和贝西赋予相同标签的谷仓的最大可能数目。

第一题 飞行路线

题意:

给定n个机场，编号1-n，约定只有小的数字到大的数字有航班，而且两点之间最多只有一趟航班。告知每两个机场之间总航班数量的奇偶性（奇数个航班用1表示，偶数个用0表示），计算两点之间有直达航班的数量。 

第二题 Cycle Correspondence

题意:

给定一个n个点m条边的有向无环图（DAG)，计算从每个点出发最长的链的长度和总长度。如果有多个路径长度都最大，取路径上边长序列字典序最小的链。