2023-2024年USACO比赛金级真题公布！

2023-2024年USACO比赛金级真题公布！大家一起来看看，12月份的USACO比赛到此结束，大家努力冲刺下一场比赛。

USACO报名及冲刺奖项/免费领真题请扫码【翰林提供报名服务】

USACO最新试题

P1 Flight Routes

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.

INPUT FORMAT (pipe stdin):

The first line contains N. Then follow N−1 lines. The i-th line contains N−i integers. The j-th integer of the i-th line is equal to the parity of the number of flight routes from i to i+j.

OUTPUT FORMAT (pipe stdout):

Output the number of pairs of cities with direct flights between them.

SAMPLE INPUT:3

11

1

SAMPLE OUTPUT:2

There are two direct flights: 1→2 and 2→3. There is one flight route from 1 to 2 and 2 to 3, each consisting of a single direct flight. There is one flight route from 1 to 3 (1→2→3).

SAMPLE INPUT:

5

1111

101

01

1

SAMPLE OUTPUT:6

There are six direct flights 1→2,1→4,1→5,2→3,3→5,4→5. These result in the following numbers of flight routes:

Flight Route Counts:  dest

1 2 3 4 5

1  0 1 1 1 3

2  0 0 1 0 1

source 3  0 0 0 0 1

4  0 0 0 0 1

5  0 0 0 0 0

which is equivalent to the sample input after taking all the numbers(mod2).

SCORING:Inputs 3-4: N≤6

Inputs 5-12: N≤100

Inputs 13-22: No additional constraints.

P2Minimum Longest Trip

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.

INPUT FORMAT (pipe stdin):The first line contains N and M.

The next M lines each contain three integers ai, bi, and li, denoting a road from ai to bi with label li.

OUTPUT FORMAT (pipe stdout):Output N lines. The i-th should contain two space-separated integers, the length and sum of road labels of Bessie's preferred trip starting at town i.

SAMPLE INPUT:4 5

4 3 10

4 2 10

3 1 10

2 1 10

4 1 10

SAMPLE OUTPUT:0 0

1 10

1 10

2 20

SAMPLE INPUT:4 5

4 3 4

4 2 2

3 1 5

2 1 10

4 1 1

SAMPLE OUTPUT:0 0

1 10

1 5

2 12

SAMPLE INPUT:4 5

4 3 2

4 2 2

3 1 5

2 1 10

4 1 1

SAMPLE OUTPUT:0 0

1 10

1 5

2 7

SAMPLE INPUT:4 5

4 3 2

4 2 2

3 1 10

2 1 5

4 1 1

SAMPLE OUTPUT:0 0

1 5

1 10

2 7

SCORING:Inputs 5-6: All labels are the same.

Inputs 7-8: All labels are distinct.

Inputs 9-10: N,M≤5000

Inputs 11-20: No additional constraints.

P3 Haybale Distribution

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 byGiven 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.

INPUT FORMAT（pipe stdin）：The first line contains N. The next line contains x1…xN.

The next line contains Q.

The next Q lines each contain two integers ai and bi.

OUTPUT FORMAT (pipe stdout):Output Q lines, the i-th line containing the answer for the i-th query.SAMPLE INPUT:5

1 4 2 3 10

4

1 1

2 1

1 2

1 4

SAMPLE OUTPUT:11

13

18

30

For example, to answer the second query, it is optimal to select y=2. Then the number of wasted haybales is equal to 2(2−1)+2(2−2)+1(3−2)+1(4−2)+1(10−2)=1+0+1+2+8=13.

SCORING:Input 2: N,Q≤10

Input 3: N,Q≤500

Inputs 4-6: N,Q≤5000

Inputs 7-16: No additional constraints.