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?

考情解析

考慮從前往后貪心，首先假設每個塔最下面的數(shù)都是負無窮，然后從小到大把每一個數(shù)加入塔中。考慮加入塔中的過程，每一次我們都把這個數(shù)加入到之前塔頂數(shù)最小的位置，如果此時不能插入，說明這個數(shù)沒法繼續(xù)插入了。由于每種數(shù)有很多個，一個個插入時間復雜度會過大，考慮將每種數(shù)作為一個整體插入。在當前這種數(shù)插入在另一種數(shù)的上方的時候，要么另一種數(shù)完全覆蓋，要么當前這種數(shù)被用完，所以每種數(shù)最多被考慮一次。

時間復雜度：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最多有多少元素相同其實就是看兩個環(huán)最多能有多少個位置能匹配。

匹配的定義是：環(huán)A和環(huán)B按某種順序按位匹配后相同數(shù)字最多是多少個。

我們可以考慮讓A環(huán)不動，B環(huán)循環(huán)右移，對于每一種字符計算出需要將環(huán)循環(huán)右移多少步得到，最終查詢哪個步數(shù)出現(xiàn)次數(shù)最多即可。

注意我們還要考慮環(huán)外點最多有多少匹配：這個比較簡單，我們只需要統(tǒng)計剩下元素里有多少種類A與B是相同的即可。

時間復雜度：O(n)

知識點：環(huán)，計數(shù)

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之前已經(jīng)固定，i改變以后，能擊中多少次;

這樣求完以后只需要把第i位固定帶來的影響，更新到change和hit里就可以了。

i從左往右固定過程中，如果這一位是L和R只影響位置p;

但如果這一位是F，那么固定以后，就要更新hit里的次數(shù)。因為它-2 -1 +1 +2都不可能發(fā)生了。

所以更新了兩部分內(nèi)容。

1. 當前位置p，如果之后的F因為-2 -1 +1 +2擊中過它，現(xiàn)在應該i已經(jīng)固定，它一定會被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0，change對應更新。

2. 當前位置p，-2 -1 +1 +2以后的位置的hit數(shù)減少1次，如果減到0就更新change

最終就是，確定會擊中的數(shù)量cnt，和change數(shù)組維護的i之后的-2 -1 +1 +2以后的4種不同擊中數(shù)量，根據(jù)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路徑為奇數(shù)，說明i到i+1有邊，反之沒有。

考慮任意點i和j的時候，只需要利用區(qū)間dp的思想計算出i到j除了直接到達的路徑有多少條，看一下是否滿足奇偶性即可。

時間復雜度:   O(n^3)

知識點：區(qū)間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)$

為了優(yōu)化比較過程，我們希望能夠快速得到兩個最長路相同的點他們之間的字典序關系。

所以我們可以動態(tài)地對最長路相同的點的內(nèi)部做一個排序，比較的時候就只需要拿出之前維護好的排序結果去做判斷，判斷時間復雜度就可以做到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：查詢的次數(shù)很多，可以考慮預處理，由于不需要頻繁修改區(qū)間，使用前綴和即可。

觀察2：題目保證數(shù)軸x1...xN上存在一個極小值點y，通過等式變形/反證法可以證明y必定為x1...xN中的一點，同時路徑總和f(y)是一個兩邊往中間遞減的單峰函數(shù)，可以使用三分法快速逼近y的最優(yōu)值，三分法模板。

時間復雜度: O(Tlogn)

知識點：三分