作者： chenchen

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试题答案+详细解析

咨询一对一备赛规划