作者： chenchen

Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has N total cows, each with a certain initial height and he wants to feed them M candy canes, each also of varying height (1≤N,M≤2⋅10⁵).

FJ plans to feed the candy canes one by one to the cows, in the order they are given in the input. To feed a candy cane to his cows, he will hang the candy cane so that initially the candy cane is just touching the ground. The cows will then line up one by one, in the order given by the input, and go up to the candy cane, each eating up to their height (since they cannot reach any higher). The candy cane stays suspended in place where it is initially set up and is not lowered to the ground, even after cows eat the bottom of the candy cane. It is possible a cow may eat nothing during her turn, if the base of the candy cane is already above that cow's height. After every cow has had their turn, the cows grow in height by how many units of candy cane they ate, and Farmer John hangs the next candy cane and the cows repeat the process again (with cow 1 again being the first to start eating the next candy cane).

INPUT FORMAT (pipe stdin):

The first line contains N and M.

The next line contains the initial heights of the N cows, each in the range [1,109].

The next line contains the heights of the M candy canes, each in the range [1,109].

OUTPUT FORMAT (pipe stdout):

The final heights of each of the N cows on separate lines.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

3 2
3 2 5
6 1

SAMPLE OUTPUT:
7
2
7

The first candy cane is 6 units tall.

The first cow eats the portion of the first candy cane up to height 3, after which the remaining portion of the first candy cane occupies heights [3,6].
The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights [5,6], is not eaten.
Next, each cow grows by the amount she ate, so the heights of the cows become [3+3,2+0,5+2]=[6,2,7].

The second candy cane is 1 unit tall, and the first cow eats all of it.

SCORING:

Inputs 2-10: N,M≤10³
Inputs 11-14: No additional constraints.
Problem credits: Agastya Goel

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

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⁵) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10⁵) 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?

INPUT FORMAT (pipe stdin):

The first line contains T and C.

The next line contains the locations of the T targets, distinct integers in the range [−C,C].

The next line contains the command string of length C, containing only the characters F, L, and R.

OUTPUT FORMAT (pipe stdout):

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

SAMPLE INPUT:

3 7
0 -1 1
LFFRFRR

SAMPLE OUTPUT:

3

If you make no changes to the string, Bessie will hit two targets:

If you change the last command from R to F, Bessie will hit all three targets:

SAMPLE INPUT:

1 5
0
FFFFF

SAMPLE OUTPUT:

1

If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.

SAMPLE INPUT:

5 6
1 2 3 4 5
FFRFRF

SAMPLE OUTPUT:
3

SCORING:

Inputs 4-6: T,C≤1000
Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John has N barns (3≤N≤5⋅10⁵), 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 a₁,…,a_K are connected in a cycle, in that order. That is, barns a_i and a_i+1 are connected for all 1≤i<K, and barns a_K and a₁ are also connected. All a_i are distinct.

Next, Bessie also assigns each barn a distinct integer label in the range [1,N] and observes that the barns with labels b₁,…,b_K are connected in a cycle, in that order. All b_i are 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.

INPUT FORMAT (pipe stdin):

The first line contains N and K.

The next line contains a1,…,a_K.

The next line contains b₁,…,b_K.

OUTPUT FORMAT (pipe stdout):

The maximum number of fixed points.

SAMPLE INPUT:

6 3
1 2 3
2 3 1

SAMPLE OUTPUT:

6

Annabelle and Bessie could have assigned the same label to every barn.

SAMPLE INPUT:

6 3
1 2 3
4 5 6

SAMPLE OUTPUT:

0

Annabelle and Bessie could not have assigned the same label to any barn.

SAMPLE INPUT:

6 4
1 2 3 4
4 3 2 5

SAMPLE OUTPUT:

4

Annabelle and Bessie could have assigned labels 2,3,4,6 to the same barns.

SCORING:

Inputs 4-5: N≤8
Inputs 6-8: N≤5000
Inputs 9-15: No additional constraints
Problem credits: Benjamin Qi

扫码领取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⁵) distinct weights. In particular, for each i∈[1,N], a_i of his cows have a weight of w_i (1≤a_i≤10⁹,1≤w_i≤10⁹).

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⁹) 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⁹) balanced towers of cows, at most how many cows can be part of some tower?

INPUT FORMAT (pipe stdin):

The first line contains three space-separated integers, N, M, and K.
The next N lines contain two space-separated integers, wi and ai. It is guaranteed that all wi are distinct.

OUTPUT FORMAT (pipe stdout):

Output the maximum number of cows in balanced towers if FJ helps the cows form towers optimally.

SAMPLE INPUT:

3 5 2
9 4
7 6
5 5

SAMPLE OUTPUT:

14
FJ can create four balanced towers with cows of weights 5, 7, and 9, and one balanced tower with cows of weights 5 and 7.

SAMPLE INPUT:

3 5 3
5 5
7 6
9 4

SAMPLE OUTPUT:
9

FJ can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow of weight 7. Alternatively, he can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow of weight 5.

SCORING:

In inputs 3-5, M≤5000 and the total number of cows does not exceed 5000.
In inputs 6-11, the total number of cows does not exceed 2⋅10⁵.
Inputs 12-17 have no additional constraints.
Problem credits: Eric Hsu

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10⁵) barns, located at integer points x₁,…,x_N (0≤x_i≤10⁶) 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⁶) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some a_i and b_i (1≤a_i,b_i≤106), a_i haybales are wasted per unit of distance left each shipment is transported, and b_i 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⋅105) independent queries each consisting of possible values of (a_i ,b_i ), 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 a_i and b_i.

OUTPUT FORMAT (pipe stdout):

Output Q lines, the i th line containing the answer for the ith 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.
Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10⁵) towns numbered from 1 to N and M (1≤M≤4⋅10⁵) one-way roads. The ith road runs from town a_i
to town b_i and has label li (1≤a_{i ,} b_i≤N, 1≤l_i≤109).

A trip of length k starting at town x₀ is a sequence of towns x₀,x₁,…,x_k, such that there is a road from town x_i to town x_i+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 a_{i ,} b_i and l_i, denoting a road from a_i
to b_i with label l_i.

OUTPUT FORMAT (pipe stdout):

Output N lines. The ith 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

In the following explanation, we let represent the road from a_i to b_i with label l_i.

There are several trips starting from vertex 4, including and are the longest. These trips each have length 2, and their road label sequences are [4,5]
and [2,10], respectively. [2,10] is the lexicographically smaller sequence, and its sum is 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.
Problem credits: Claire Zhang and Spencer Compton

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

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 labeled 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=c₁<c₂<⋯<c_k=b such that for each 1≤i<k, there is a direct flight from city c_i to city c_i+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 ith 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.
Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie has taken on a new job as a train dispatcher! There are two train stations:A and B. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time t, then it will arrive at the other station at time t+T(1≤T≤10¹²).

There are N (1≤N≤5000) trains whose departure times need to be scheduled. The i th train must leave station s_i at time t_i or later (s_i∈{A,B},0≤t_i≤10¹²). It is not permitted to have trains going in opposite directions along the track at the same time (since they would crash). However, it is permitted to have many trains on the track going in the same direction at the same time (assume trains have negligible size).

Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train i is scheduled to leave at time a_i≥s_i, the total delay is defined as

INPUT FORMAT (pipe stdin):

The first line contains N and T.

Then N lines follow, where the ith line contains the station s_i,
and time t_i corresponding to the ith train.

OUTPUT FORMAT (pipe stdout):

The minimum possible total delay over all valid schedules.

SAMPLE INPUT:

1 95
B 63

SAMPLE OUTPUT:

0

The only train leaves on time.

SAMPLE INPUT:

4 1
B 3
B 2
A 1
A 3

SAMPLE OUTPUT:

1
There are two optimal schedules. One option is to have trains 2,3,4 leave on time and train 1 leave after a one-minute delay. Another is to have trains 1,2,3 leave on time and train 4 leave after a one-minute delay.

SAMPLE INPUT:

4 10
A 1
B 2
A 3
A 21

SAMPLE OUTPUT:

13
The optimal schedule is to have trains 1and 3 leave on time, train 2 leave at time 13, and train 4 leave at time 23. The total delay is 0+11+0+2=13.

SAMPLE INPUT:

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

SAMPLE OUTPUT:

548047356974

SCORING:

Inputs 5-6: N≤15
Inputs 7-10: N≤100
Inputs 11-14: N≤500
Inputs 15-18: N≤2000
Inputs 19-24: No additional constraints
Problem credits: Brandon Wang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

To improve her mathematical knowledge, Bessie has been taking a graph theory course and finds herself stumped by the following problem. Please help her!

You are given a connected, undirected graph with vertices labeled 1…N and edges labeled 1…M(2≤N≤2⋅10⁵, N−1≤M≤4⋅10⁵). For each vertex v in the graph, the following process is conducted:​

Let S={v}and h=0.

While |S|<N,​

1.Out of all edges with exactly one endpoint in S, let e be the edge with the minimum label.
2.Add the endpoint of e not in S to S.
3.Set h=10h+e.
​
Return h ( mod 10⁹+7).
​
Determine all the return values of this process.​

INPUT FORMAT (pipe stdin):

The first line contains N and M .​Then follow M lines, the eth containing the endpoints (a_e,b_e) of the eth edge (1≤a_e<b_e≤N). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.
​
OUTPUT FORMAT (pipe stdout):

Output N lines, where the ith line should contain the return value of the process starting at vertex i.

SAMPLE INPUT:

3 2
1 2
2 3

SAMPLE OUTPUT:

12
12
21

SAMPLE INPUT:

5 6
1 2
3 4
2 4
2 3
2 5
1 5

SAMPLE OUTPUT:

1325
1325
2315
2315
5132

Consider starting at i=3. First, we choose edge 2, after which S={3,4} and h=2.Second, we choose edge 3, after which S={2,3,4}and h=23. Third, we choose edge 1, after which S={1,2,3,4} and h=231. Finally, we choose edge 5, after which S={1,2,3,4,5}and h=2315. The answer for i=3 is therefore 2315.

SAMPLE INPUT:

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

SAMPLE OUTPUT:

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Make sure to output the answers modulo 109+7.

SCORING:

Input 4: N,M≤2000
Inputs 5-6: N≤2000
Inputs 7-10: N≤10000
Inputs 11-14: a_e+1=b_e
for all e
Inputs 15-23: No additional constraints.

Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John has N (2≤N≤10⁵) cows labeled 1…N, where the connections between cows are described by a tree. Unfortunately, there is a sickness spreading throughout.

Initially, some cows start off infected. Every night, an infected cow spreads the sickness to their neighbors. Once a cow is infected, she stays infected. After some amount of nights, Farmer John realizes that there is an issue so he tests his cows to determine who has the sickness.

You are given Q(1≤Q≤20) different values for the number of nights, each an integer in the range [0,N]
. For each number of nights, determine the minimum number of cows that could have started with the illness, or that the number of nights is inconsistent with the given information.

INPUT FORMAT (pipe stdin):

The first line contains N.

The next line contains a bit string of length N, where the ith bit is 1 if the ith cow is infected and 0 otherwise. At least one cow is infected.

The next N−1 lines contain the edges of the tree.

Then Q, followed by the Q values for the number of nights.

OUTPUT FORMAT (pipe stdout):

Q lines, the answers for each number of nights, or −1 if impossible.

SAMPLE INPUT:

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

SAMPLE OUTPUT:

1
1
1
1
2
5

For the first four queries, one possibility is that just cow 3 started with the illness. For the fifth query (1 night), one possibility is that cows 2 and 4 started with the illness. For the sixth query (0 nights), one possibility is that all five cows started with the illness.

SAMPLE INPUT:

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

SAMPLE OUTPUT:

10
3
2
1
1
1
1
1
1
1
1

For the first query (0 nights), one possibility is that all ten cows started with the illness. For the second query (1 night), one possibility is that cows 2, 7, and 9 started with the illness. For the third query (2 nights), one possibility is that cows 2 and 9 started with the illness. For the fourth to eleventh queries, one possibility is that just cow 7 started with the illness.

SAMPLE INPUT:

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

SAMPLE OUTPUT:

3
1
1
-1
-1
-1

For the first query (0 nights), one possibility is that cows 1, 2, and 3 started with the illness. For the second query (1 night), one possibility is that just cow 2 started with the illness. For the third query (2 nights), one possibility is that just cow 1 started with the illness. For the fourth through sixth queries, there is no consistent possibility.

SCORING:

Inputs 4-5: N≤10
Inputs 6-8: All cows are infected.
Inputs 9-11: N≤400
Inputs 12-23: No additional restrictions.
Problem credits: Suhas Nagar and Brandon Wang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划