USACO竞赛冲刺班招生中~

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have N (1≤N≤2⋅10**5) distinct weights. In particular, for each i∈[1,N], ai of his cows have a weight of wi (1≤ai≤10**9,1≤wi≤109).

His most popular stunt involves the cows forming balanced towers. A tower is a sequence of cows where each cow is stacked on top of the next. A tower is balanced if every cow with a cow directly above it has weight at least K (1≤K≤10**9) greater than the weight of the cow directly above it. Any cow can be part of at most one balanced tower.

If FJ wants to create at most M (1≤M≤10**9) balanced towers of cows, at most how many cows can be part of some tower?

考情解析

考虑从前往后贪心，首先假设每个塔最下面的数都是负无穷，然后从小到大把每一个数加入塔中。考虑加入塔中的过程，每一次我们都把这个数加入到之前塔顶数最小的位置，如果此时不能插入，说明这个数没法继续插入了。由于每种数有很多个，一个个插入时间复杂度会过大，考虑将每种数作为一个整体插入。在当前这种数插入在另一种数的上方的时候，要么另一种数完全覆盖，要么当前这种数被用完，所以每种数最多被考虑一次。

时间复杂度：O(nlogn)

知识点：贪心，排序

Farmer John has N barns(3 <= N <= 5.10**5), of which K(3 <= K <= N) distinct pairs of barns are connected.

First, Annabelle assigns each barn a distinct integer label in the range[1, N], and observes that the barns with labels a1...ak are connected in a cycle, in that order. That is, barns ai and a(i+1) are connected for all 1 <= i < K, and barns ak and a1are also connected. All ai are distinct.Next, Bessie also assigns each barn a distinct integer label in the range[1, N] and observes that the barns with labels b1,...bk are connected in a cycle, in that order. All bi distinct.

Some (possibly none or all) barns are assigned the same label by Annabelle and Bessie. Compute the maximum possible number of barns that are assigned the same label by Annabelle and Bessie.

A与B最多有多少元素相同其实就是看两个环最多能有多少个位置能匹配。

匹配的定义是：环A和环B按某种顺序按位匹配后相同数字最多是多少个。

我们可以考虑让A环不动，B环循环右移，对于每一种字符计算出需要将环循环右移多少步得到，最终查询哪个步数出现次数最多即可。

注意我们还要考虑环外点最多有多少匹配：这个比较简单，我们只需要统计剩下元素里有多少种类A与B是相同的即可。

时间复杂度：O(n)

知识点：环，计数

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤10**5) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10**5) commands, each one of L, F, or R:

● L: Bessie moves one unit to the left.

● R: Bessie moves one unit to the right.

● F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

解析：

先求所有的步骤整体平移-2,-1,0,+1,+2时可以击中多少个目标。答案在change[1]-change[5]。再用hit[1-5][位置]记录每个位置被击中了多少次。

然后i从左往右一位位求i之前已经固定，i改变以后，能击中多少次;

这样求完以后只需要把第i位固定带来的影响，更新到change和hit里就可以了。

i从左往右固定过程中，如果这一位是L和R只影响位置p;

但如果这一位是F，那么固定以后，就要更新hit里的次数。因为它-2 -1 +1 +2都不可能发生了。

所以更新了两部分内容。

1. 当前位置p，如果之后的F因为-2 -1 +1 +2击中过它，现在应该i已经固定，它一定会被这一次射击击中。所以把-2 -1 +1 +2以后的p位置的hit数都清0，change对应更新。

2. 当前位置p，-2 -1 +1 +2以后的位置的hit数减少1次，如果减到0就更新change

最终就是，确定会击中的数量cnt，和change数组维护的i之后的-2 -1 +1 +2以后的4种不同击中数量，根据L->R R->L之类的变化情况相加。

时间复杂度: O(n)

知识点：思维难题

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N(2≤N≤750) cities labelled 1…N, and for each pair of cities (i,j) with i<j there either exists a single direct flight from i to j or not.

A flight route from city a to city b (a<b) is a sequence of k≥2 cities a=c1<c2<⋯<ck=b such that for each 1≤i<k, there is a direct flight from city ci to city ci+1. For every pair of cities (i,j) with i<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd).

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

考情分析

从相邻位置来考虑比较简单，如果i到i+1路径为奇数，说明i到i+1有边，反之没有。

考虑任意点i和j的时候，只需要利用区间dp的思想计算出i到j除了直接到达的路径有多少条，看一下是否满足奇偶性即可。

时间复杂度:   O(n^3)

知识点：区间dp

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10^5) towns numbered from 1 to N and M (1≤M≤4⋅10^5) one-way roads. The i-th road runs from town ai to town bi and has label li 

(1≤ai,bi≤N, 1≤li≤10^9).

A trip of length k starting at town x0 is a sequence of towns x0,x1,…,xk, such that there is a road from town xi to town xi+1 for all 0≤i<k. It is guaranteed that there are no trips of infinite length in Cowland, and that no two roads connect the same pair of towns.

For each town, Bessie wants to know the longest possible trip starting at it. For some starting towns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.

考情分析

首先题目保证给出图是DAG，那么我们要求最长路的话就可以利用拓扑排序/bfs来解决。

难点在于题目要求字典序最小，考虑如何快速比较两条出边的字典序大小

由于题目权值可以相同暴力走下去比较时间复杂度会被卡到$O(n^2)$

为了优化比较过程，我们希望能够快速得到两个最长路相同的点他们之间的字典序关系。

所以我们可以动态地对最长路相同的点的内部做一个排序，比较的时候就只需要拿出之前维护好的排序结果去做判断，判断时间复杂度就可以做到O(1)

总时间复杂度：O(nlogn)

知识点：拓扑排序，字典序

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10^5) barns, located at integer points x1,…,xN (0≤xi≤10^6) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10^6) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some ai and bi

(1≤ai,bi≤10^6), ai haybales are wasted per unit of distance left each shipment is transported, and bi haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by

Given Q (1≤Q≤2⋅10^5) independent queries each consisting of possible values of (ai,bi), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.

考情分析

观察1：查询的次数很多，可以考虑预处理，由于不需要频繁修改区间，使用前缀和即可。

观察2：题目保证数轴x1...xN上存在一个极小值点y，通过等式变形/反证法可以证明y必定为x1...xN中的一点，同时路径总和f(y)是一个两边往中间递减的单峰函数，可以使用三分法快速逼近y的最优值，三分法模板。

时间复杂度: O(Tlogn)

知识点：三分