作者： chenchen

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

After years of hosting games and watching Bessie get first place over and over, Farmer John has realized that this can't be accidental. Instead, he concludes that Bessie must have winning coded into her DNA so he sets out to find this "winning" gene.

He devises a process to identify possible candidates for this "winning" gene. He takes Bessie's genome, which is a string S of length N where 1≤N≤3000. He picks some pair (K,L) where 1≤L≤K≤N representing that the "winning" gene candidates will have length L and will be found within a larger K length substring. To identify the gene, he takes all K length substrings from S
which we will call a k-mer. For a given k-mer, he takes all length L substrings, identifies the lexicographically minimal substring as a winning gene candidate (choosing the leftmost such substring if there is a tie), and then writes down the 0 -indexed position p_i where that substring starts in S to a set P.

Since he hasn't picked K and L yet, he wants to know how many candidates there will be for every pair of (K,L).

For each v in 1…N, help him determine the number of (K,L) pairs with |P|=v.

INPUT FORMAT (input arrives from the terminal / stdin):

N representing the length of the string. S representing the given string. All characters are guaranteed to be uppercase characters where si∈A−Z since bovine genetics are far more advanced than ours.

OUTPUT FORMAT (print output to the terminal / stdout):

For each v in 1…N, output the number of (K,L) pairs with |P|=v, with each number on a separate line.

SAMPLE INPUT:

8
AGTCAACG

SAMPLE OUTPUT:

11
10
5
4
2
2
1
1

In this test case, the third line of the output is 5 because we see that there are exactly 5 pairs of K and L that allow for three "winning" gene candidates. These candidates are (where p_i is 0-indexed):

(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]

To see how (4,2) leads to these results, we take all 4-mers

AGTC
GTCA
TCAA
CAAC
AACG

For each 4-mer, we identify the lexicographically minimal length 2 substring

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

We take the positions of all these substrings in the original string and add them to a set P to get P=[0,3,4].

On the other hand, if we focus on the pair (4,1), we see that this only leads to 2 total "winning" gene candidates. If we take all 4-mers and identify the lexicographically minimum length 1 substring (using A and A' and A* to distinguish the different As), we get

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

While both A' and A* are lexicographically minimal in the last 3 cases, the leftmost substring takes precedence so A' is counted as the only candidate in all of these cases. This means that P=[0,4].

SCORING:

Inputs 2-4: N≤100
Inputs 5-7: N≤500
Inputs 8-16: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

**Note: The time limit and memory limit for this problem are 3s and 512MB, which are 1.5x and 2x the normal amount, respectively.**

Farmer John's N cows (1≤N≤10⁵) each like to take a daily walk around the fence enclosing his pasture. Unfortunately, whenever a cow walks past a fence post, she brushes up against it, requiring Farmer John to need to repaint the fence posts regularly.

The fence consists of P posts (4≤P≤2⋅10⁵, P even), the location of each being a different 2D point (x,y) on a map of FJ's farm (0≤x,y≤10⁹). Each post is connected to the two adjacent posts by fences that are either vertical or horizontal line segments, so the entire fence can be considered a polygon whose sides are parallel to the x or y axes (the last post connects back to the first post, ensuring the fence forms a closed loop that encloses the pasture). The fence polygon is "well-behaved" in that fence segments only potentially overlap at their endpoints, each post aligns with exactly two fence segment endpoints, and every two fence segments that meet at an endpoint are perpendicular.

Each cow has a preferred starting and ending position for her daily walk, each being points somewhere along the fence (possibly at posts, possibly not). Each cow walks along the fence for her daily walks, starting from her starting position and ending at her ending position. There are two routes that the cow could take, given that the fence forms a closed loop. Since cows are somewhat lazy creatures, each cow will walk in the direction around the fence that is shorter. Remarkably, this choice is always clear -- there are no ties!

A cow touches a fence post if she walks past it, or if the fence post is the starting or ending point of her walk. Please help FJ calculate the number of daily touches experienced by each fence post, so he knows which post to repaint next.

It can be shown that there is exactly one possibility for the fences given the locations of all of the posts.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N and P. Each of the next P lines contains two integers representing the positions of the fence posts in no particular order. Each of the next N lines contains four integers x₁ y₁ x₂ y₂ representing the starting position (x₁,y₁) and ending position (x₂,y₂)of a cow.

OUTPUT FORMAT (print output to the terminal / stdout):

Write P integers as output, giving the number of touches experienced by each fence post.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
2
2
1

The following posts are connected by fence segments:

(3,1)↔(3,5)↔(1,5)↔(1,1)↔(3,1)

The posts touched by each cow are as follows:

1.Posts 2 and 4.
2.Posts 2 and 3.
3.Posts 1 and 3.
4.No posts.
5.No posts.

SAMPLE INPUT:

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

SAMPLE OUTPUT:

1
0
0
0
1
1
1
2

SAMPLE INPUT:

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

SAMPLE OUTPUT:

1
1
1
1
1
0
0
0
0
0
0
0

SCORING:

Inputs 4-6: N,P≤1000
Inputs 7-9: All locations satisfy 0≤x,y≤1000.
Inputs 10-15: No additional constraints.
Problem credits: Brian Dean

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

咨询一对一备赛规划

Bessie is looking for a new job! Fortunately, K farmers are currently hiring and conducting interviews. Since jobs are highly competitive, the farmers have decided to number and interview cows in the order they applied. There are N cows that applied before Bessie, so her number is N+1(1≤K≤N≤3⋅10⁵).

The interview process will go as follows. At time 0, farmer i will start interviewing cow i for each 1≤i≤K. Once a farmer finishes an interview, he will immediately begin interviewing the next cow in line. If multiple farmers finish at the same time, the next cow may choose to be interviewed by any of the available farmers, according to her preference.

For each 1≤i≤N, Bessie already knows that cow i's interview will take exactly t_i minutes (1≤t_i ≤10⁹). However, she doesn't know each cow's preference of farmers.

Since this job is very important to Bessie, she wants to carefully prepare for her interview. To do this, she needs to know when she will be interviewed and which farmers could potentially interview her. Help her find this information!

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of the input will contain two integers N and K.

The second line will contain Nintegers t₁…t_N.

OUTPUT FORMAT (print output to the terminal / stdout):

On the first line, print the time Bessie's interview will begin.

On the second line, a bit string of length K, where the i-th bit is 1if farmer i could interview Bessie and 0 otherwise.

SAMPLE INPUT:

6 3
3 1 4159 2 6 5

SAMPLE OUTPUT:

8
110

There are 6 cows aside from Bessie and 3 farmers, and the interview process will go as follows:

1.At time t=0, farmer 1 interviews cow 1, farmer 2 interviews cow 2, and farmer 3 interviews cow 3.
2.At time t=1, farmer 2 finishes his interview with cow 2 and starts interviewing cow 4.
3.At time t=3, both farmer 1 and farmer 2 finish their interviews, and there are two possibilities:
Farmer 1 interviews cow 5 and farmer 2 interviews cow 6. In this case, farmer      2 would finish his interview at time t=8 and start interviewing Bessie.
Farmer 1 interviews cow 6 and farmer 2 interviews cow 5. In this case, farmer      1 would finish his interview at time t=8 and start interviewing Bessie.

Thus, Bessie's interview will begin at time t=8, and she could be interviewed by either farmer 1 or farmer 2.

SCORING:

Inputs 2-3: No two farmers finish at the same time.
Inputs 4-9: N≤3⋅10³ 
Inputs 10-21: No additional constraints.

Problem credits: Avnith Vijayram

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

咨询一对一备赛规划

Bessie has two arrays of length N(1≤N≤500). The i-th element of the first array is a_i (1≤a_i≤10⁶) and the i-th element of the second array is b_i (1≤b_i≤10⁶).

Bessie wants to split both arrays into non-empty subarrays such that the following is true.

1.Every element belongs in exactly 1 subarray.
2.Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be k (i.e. the first array is split into exactly k subarrays and the second array is split into exactly k subarrays).
3.For all 1≤i≤k, the average of the i-th subarray on the left of the first array is less than or equal to the average of the i-th subarray on the left of the second array.

Count how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo 109+7. Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The next line contains a_l,a₂,...,a_N.

The next line contains b₁,b₂,...,b_N.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo 10⁹+7.

SAMPLE INPUT:

2
1 2
2 2

SAMPLE OUTPUT:

2

The two valid ways are:

1.Split the first array into [1],[2] and the second array into [2],[2].
2.Split the first array into [1,2] and the second array into [2,2].

SAMPLE INPUT:

3
1 3 2
2 2 2

SAMPLE OUTPUT:

3

The three valid ways are:

1.Split the first array into [1,3],[2] and the second array into [2,2],[2].
2.Split the first array into [1,3],[2] and the second array into [2],[2,2].
3.Split the first array into [1,3,2] and the second array into [2,2,2].

SAMPLE INPUT:

5
2 5 1 3 2
2 1 5 2 2

SAMPLE OUTPUT:

1

The only valid way is to split the first array into [2],[5,1,3],[2] and the second array into [2],[1,5],[2,2].

SAMPLE INPUT:

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

SAMPLE OUTPUT:

140

SCORING:

Inputs 5-6: N≤10
Inputs 7-9: N≤80
Inputs 10-17: N≤300
Inputs 18-20: N≤500

Problem credits: Alex Liang

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

咨询一对一备赛规划

Bessie is planting some grass on the positive real line. She has N (2≤N≤2⋅10⁵) different cultivars of grass, and will plant the ith cultivar on the interval [ℓ_i,r_i](0<ℓ_i<r_i≤10⁹).

In addition, cultivar i grows better when there is some cultivar j (j≠i) such that cultivar j and cultivar i overlap with length at least k_i (0<k_i≤r_i−ℓ_i). Bessie wants to evaluate all of her cultivars. For each i, compute the number of j≠i such that j and ioverlap with length at least k_i.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next N lines each contain three space-separated integers ℓ_i, r_i, and k_i.

OUTPUT FORMAT (print output to the terminal / stdout):

The answers for all cultivars on separate lines.

SAMPLE INPUT:

2
3 6 3
4 7 2

SAMPLE OUTPUT:
0
1

The overlaps of the cultivars is [4,6], which has length 2, which is at least 2 but not at least 3.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3
3
2
2

SAMPLE INPUT:

5
8 10 2
4 9 2
3 7 4
5 7 1
2 7 1

SAMPLE OUTPUT:

0
3
1
3
3

SCORING:

Input 4-5: N≤5000
Inputs 6-11: k is the same for all intervals
Inputs 12-20: No additional constraints.
In addition, for Inputs 5, 7, ..., 19, r_i≤2N for all i.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

The cows have formed a dance team, and Farmer John is their choreographer! The team's latest and greatest dance involves N cows (2≤N≤10⁶ ) standing in a line. Each move in the dance involves two cows, up to K positions apart (1≤K<N
), gracefully jumping and landing in each other's position.

There are two types of cows in the line – Guernseys and Holsteins. As such, Farmer John has documented the dance as a sequence of length-N
binary strings, where a 0 represents a Guernsey, a 1 represents a Holstein, and the overall string represents how the cows are arranged in the line.

Unfortunately, Farmer Nhoj (who choreographs for a rival team) has sabotaged the dance and erased all but the first and last binary strings! With a big competition quickly approaching, Farmer John must waste no time in reconstructing the dance.

Given these two binary strings, help Farmer John find the minimum number of moves in the dance!

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and K.

The second line contains the first binary string.

The third line contains the last binary string.

It is guaranteed that both binary strings contain the same number of ones.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum number of moves in the dance.

SAMPLE INPUT:

4 1
0111
1110

SAMPLE OUTPUT:

3

One possible dance:

0111 -> 1011 -> 1101 -> 1110

SAMPLE INPUT:

5 2
11000
00011

SAMPLE OUTPUT:

3

One possible dance:

11000 -> 01100 -> 00110 -> 00011

SAMPLE INPUT:

5 4
11000
00011

SAMPLE OUTPUT:

2

One possible dance:

11000 -> 10010 -> 00011

SCORING:

Inputs 4-5: K=1
Inputs 6-7: Both strings have at most 8
ones.
Inputs 8-15: N≤5000
Inputs 16-23: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

You and a single robot are initially at point 0 on a circle with perimeter L
(1≤L≤10⁹). You can move either counterclockwise or clockwise along the circle at 1 unit per second. All movement in this problem is continuous.

Your goal is to place exactly R−1 robots such that at the end, every two consecutive robots are spaced L/R away from each other (2≤R≤20, R
divides L). There are N (1≤N≤10⁵) activation points, the ith of which is located a_i distance counterclockwise from 0(0≤a_i<L). If you are currently at an activation point, you can instantaneously place a robot at that point. All robots (including the original) move counterclockwise at a rate of 1 unit per K seconds (1≤K≤106).

Compute the minimum time required to achieve the goal.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains L, R, N, and K.
The next line contains N
space-separated integersa₁,a₂,…,a_N.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum time required to achieve the goal.

SAMPLE INPUT:

10 2 1 2
6

SAMPLE OUTPUT:

22

We can reach the activation point at 6 in 4 seconds by going clockwise. At this time, the initial robot will be located at 2. Wait an additional 18 seconds until the initial robot is located at 1. Now we can place a robot to immediately win.

SAMPLE INPUT:

10 2 1 2
7

SAMPLE OUTPUT:

4

We can reach the activation point at 7 in 3 seconds by going clockwise. At this time, the initial robot will be located at 1.5. Wait an additional second until the initial robot is located at 2. Now we can place a robot to immediately win.

SAMPLE INPUT:

32 4 5 2
0 23 12 5 11

SAMPLE OUTPUT:

48

SAMPLE INPUT:

24 3 1 2
16

SAMPLE OUTPUT:

48

SCORING:

Inputs 5-6: R=2
Inputs 7-12: R≤10,N≤80
Inputs 13-20: R≤16
Inputs 21-24: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has N( 1≤N≤2⋅10⁵) haybales sorted in non-increasing order, where the i-th haybale has aiunits of hay (2⋅10⁵≥a₁≥a₂≥⋯≥a_N≥1).

Farmer John is considering splitting a contiguous range of haybales a_l,…,a_r between Bessie and Elsie. He has decided to process the haybales in order from l
to r, and when processing the i-th haybale he will give it to the cow who currently has less hay (if it is a tie, he will give it to Bessie).

You are given Q(1≤Q≤2⋅10⁵) queries, each with three integers l,r,x(1≤l≤r≤N
, |x|≤10⁹). For each query, output how many more units of hay Bessie will have than Elsie after processing haybales l to r, if Bessie starts with x more units than Elsie. Note that this value is negative if Elsie ends up with more haybales than Bessie.

INPUT FORMAT (input arrives from the terminal / stdin):

First line contains N.

Second line contains a₁…a_N.

Third line contains Q.

Next Q lines contain l,r,x.

OUTPUT FORMAT (print output to the terminal / stdout):

Output Q lines, containing the answer for each query.

SAMPLE INPUT:

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

SAMPLE OUTPUT:

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

For the 1st query, Elsie starts with 2 more hay than Bessie. Then, after processing haybale 1, Bessie will receive 3 hay, and Bessie will have 1 more hay than Elsie.

For the 3rd query, Elsie and Bessie start with the same number of hay. After processing haybale 1, Bessie will receive 3 hay, and Bessie will have 3
more hay than Elsie.

For the 9th query, Bessie starts with 1 more hay than Elsie, then after processing the 1st haybale, has 2 less hay than Elsie, and after processing the 2nd haybale, has 1 less hay than Elsie.

SAMPLE INPUT:

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

SAMPLE OUTPUT:

16
12
7
4
1
2
1

In the 5th query, there are 5 haybales to process. Bessie receives 4 hay, then Elsie receives 4 hay, then Bessie receives 3 hay, then Elsie receives 1 hay, then Elsie receives 1 hay.

SCORING:

Input 3: Q≤100
Inputs 4-6: At most 100
distinct a_i
Inputs 7-22: No additional constraints.

Problem credits: Benjamin Q_i

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

咨询一对一备赛规划

**Note: The time limit and memory limit for this problem are 3s and 512MB, which are 1.5x and 2x the normal amount, respectively.**

Farmer John's N (1≤N≤10⁵) cows each have a Farm ID number in the form of a bitstring (a string consisting of the characters '0' and '1'). Bessie, the eldest cow, has the Farm ID numbers of all the cows memorized, and likes to go around and ask cows their ID numbers.

When a cow is asked their Farm ID number, they will start to say the correct bitstring, but may get confused and stop before finishing it. When Bessie hears the bitstring, if it is not the Farm ID number of any cow on the farm, then she will shrug and walk off. However, if it is the ID number of a different cow than the one she asked, then she will assume that identity theft has occurred and place the farm into lockdown. Note that this can happen even when the cow says their full Farm ID number.

Farmer John would like to prevent this from happening, and is willing to change the cows' Farm ID numbers by adding some more bits to them. In one second, he can add one bit to the end of the Farm ID number of any cow. Figure out the minimum amount of time it will take for him to prevent a lockdown from ever occurring.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N, the number of cows on Farmer John's farm.
Then N lines follow. The kth line contains a bitstring equal to the Farm ID number of the kth cow on Farmer John's farm.

No cow's Farm ID number is empty, and the total length of all Farm ID numbers is at most 10⁶.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum number of seconds Farmer John needs to spend to ensure that a lockdown will never occur.

SAMPLE INPUT:

3
1
1
1

SAMPLE OUTPUT:

5

This sample satisfies the constraints for the first subtask.

We can make a lockdown impossible in 5 seconds by adding '0' to the first Farm ID number, '10' to the second Farm ID number, and '11' to the third Farm ID number, making the Farm ID numbers '10', '110', and '111'.

You can prove that this cannot be done in 4 or fewer seconds. For example, if you leave the Farm ID numbers as they are, then all 3 cows have the same Farm ID number '1', so when Bessie hears it it will always be the Farm ID number of another cow.

As another example, if you spend just 2 seconds to add '0' to the second Farm ID number and '1' to the third Farm ID number, then the Farm ID numbers are '1', '10', and '11', and so the second and third cows, when saying their Farm ID numbers, might stop in the middle and just say '1', which would be the Farm ID number of the first cow.

SAMPLE INPUT:

3
1
11
111

SAMPLE OUTPUT:

2

We can make a lockdown impossible in 2 seconds by adding '0' to the first two Farm ID numbers, making the Farm ID numbers '10', '110', and '111' like before. You can prove that this cannot be done in 1 second.

SAMPLE INPUT:

3
1
1
11

SAMPLE OUTPUT:

4

We can make a lockdown impossible in 4 seconds by adding '00' to the first Farm ID number and '01' to the second Farm ID number. You can prove that this cannot be done in 3 or fewer seconds.

SAMPLE INPUT:

5
0
01
0011
010
01

SAMPLE OUTPUT:

6

SAMPLE INPUT:

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

SAMPLE OUTPUT:

41

This sample satisfies the constraints for the first subtask.

SCORING:

Inputs 6-7: All Farm ID numbers have length exactly 1.
Inputs 8-15: N≤10²and the total length of the Farm ID numbers does not exceed 10³.
Inputs 16-25: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划