作者： chenchen

Elsie is trying to describe her favorite USACO contest to Bessie, but Bessie is having trouble understanding why Elsie likes it so much. Elsie says "And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO".

Bessie still doesn't understand, so she transcribes Elsie's description in a string of length N (3≤N≤10⁵ ) containing lowercase alphabetic characters s₁s₂…s_N. Elsie considers a string t containing three characters a moo if t₂=t₃ and t₂≠t₁.

A triplet (i,j,k) is valid if i<j<k and string sisjsk forms a moo. For the triplet, FJ performs the following to calculate its value:

FJ bends string s 90-degrees at index j
The value of the triplet is twice the area of Δijk.

In other words, the value of the triplet is (j−i)(k−j).

Bessie asks you Q(1≤Q≤3⋅10⁴) queries. In each query, she gives you two integers l and r (1≤l≤r≤N, r−l+1≥3) and ask you for the maximum value among valid triplets (i,j,k) such that l≤i and k≤r. If no valid triplet exists, output −1.

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++).

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

The first line contains two integers N and Q.

The following line contains s₁s₂,…s_N.

The following Q lines contain two integers l and r, denoting each query.

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

Output the answer for each query on a new line.

SAMPLE INPUT:

12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10

SAMPLE OUTPUT:

28
6
1
-1
12

For the first query, (i,j,k) must satisfy 1≤i<j<k≤12. It can be shown that the maximum area of Δijk for some valid (i,j,k) is achieved when i=1, j=8, and k=12. Note that s₁s₈s₁₂ is the string "acc" which is a moo according to the definitions above. Δijk will have legs of lengths 7 and 4 so two times the area of it will be 28.

For the third query, (i,j,k) must satisfy 4≤i<j<k≤8. It can be shown that the maximum area of Δijk for some valid (i,j,k) is achieved when i=4, j=5, and k=6.

For the fourth query, there exists no (i,j,k) satisfying 2≤i<j<k≤5 in which s_is_js_k is a moo so the output to that query is −1.

SCORING:

Inputs 2-3: N,Q≤50
Inputs 4-6: Q=1 and the singular query satisfies l=1 and r=N
Inputs 7-11: No additional constraints

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

The cows are in a particularly mischievous mood today! All Farmer John wants to do is take a photograph of the cows standing in a line, but they keep moving right before he has a chance to snap the picture.

Specifically, each of FJ's N cows (1≤N≤10⁵) has an integer height from 1 to N. FJ wants to take a picture of the cows standing in line in a very specific ordering. If the cows have heights h₁,…,h_K when lined up from left to right, he wants the cow heights to have the following three properties:

He wants the cow heights to increase and then decrease. Formally, there must exist an integer i such that h₁≤⋯≤h_i≥⋯≥h_K.

He does not want any cow standing next to another cow with exactly the same height. Formally, h_i≠h_i+1 for all 1≤i<K.

He wants the picture to be symmetric. Formally, if i+j=K+1, then h_i= h_j.

FJ wants the picture to contain as many cows as possible. Specifically, FJ can remove some cows and rearrange the remaining ones. Compute the maximum number of cows FJ can have in the picture satisfying his constraints.

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

You have to answer multiple test cases.

The first line of input contains a single integer T (1≤T≤10⁵) denoting the number of test cases. T test cases follow.

The first line of every test case contains a single integer N. The second line of every test case contains N integers, the heights of the N cows available. The cow heights will be between 1 and N.

It is guaranteed the sum of N over all test cases will not exceed 10⁶.

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

Output T lines, the i'th line containing the answer to the i'th test case. Each line should be an integer denoting the maximum number of cows FJ can include in the picture.

SAMPLE INPUT:

2
4
1 1 2 3
4
3 3 2 1

SAMPLE OUTPUT:

3
1

For the first test case, FJ can take the cows with heights 1, 1, and 3, and rearrange them into [1,3,1], which satisfies all the conditions. For the second test case, FJ can take the cow with height 3and form a valid photo.

SCORING:

Inputs 2-3: T≤100,N≤7
Inputs 4-5: T≤10⁴, all cows will have height at most 10.
Inputs 6-11: No additional constraints.

Problem credits: Nick Wu

**Note: The time limit for this problem is 3s, 1.5x the default.**

In a game of Hoof Paper Scissors, Bessie and Elsie can put out one of N (1≤N≤3000) different hoof symbols labeled 1…N, each corresponding to a different material. There is a complicated chart of how the different materials interact with one another, and based on that chart, either:

One symbol wins and the other loses.
The symbols draw against each other.

Hoof Paper Scissors Minus One works similarly, except Bessie and Elsie can each put out two symbols, one with each hoof. After observing all four symbols that they have all put out, they each choose one of their two symbols to play. The outcome is decided based on normal Hoof Paper Scissor conventions.

Given the M(1≤M≤3000) symbol combinations that Elsie plans to make across each game, Bessie wants to know how many different symbol combinations would result in a guaranteed win against Elsie. A symbol combination is defined as an ordered pair (L,R) where L is the symbol the cow plays with her left hoof and R is the symbol the cow plays with her right hoof. Can you compute this for each game?

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

The first line contains two space-separated integers N and M representing the number of hoof symbols and the number of games that Bessie and Elsie play.

Out of the following N lines of input, the ith line consists of i characters a_i,1a_i,2…a_i,i where each a_i,j∈{D,W,L}. If a_i,j=D, then symbol i draws against symbol j. If ai,j=W, then symbol i wins against symbol j. If a_i,j=L, then symbol i loses against symbol j. It is guaranteed that ai,i=D.

The next M lines contain two space separated integers s₁ and s₂ where 1≤s₁,s₂ ≤N. This represents Elsie's symbol combination for that game.

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

Output M lines where the i-th line contains the number of symbol combinations guaranteeing that Bessie can beat Elsie in the i-th game.

SAMPLE INPUT:

3 3
D
WD
LWD
1 2
2 3
1 1

SAMPLE OUTPUT:

0
0
5

In this example, this corresponds to the original Hoof Paper Scissors and we can let Hoof=1, Paper=2, and Scissors=3. Paper beats Hoof, Hoof beats Scissors, and Scissors beats Paper. There is no way for Bessie to guarantee a win against the combinations of Hoof+Paper or Paper+Scissors. However, if Elsie plays Hoof+Hoof, Bessie can counteract with any of the following combinations.

Paper+Paper
Paper+Scissors
Paper+Hoof
Hoof+Paper
Scissors+Paper

If Bessie plays any of these combinations, she can guarantee that she wins by putting forward Paper.

SCORING:

Inputs 2-6: N,M≤100
Inputs 7-12: No additional constraints.
Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Bessie is going on a ski trip with her friends. The mountain has N
waypoints (1≤N≤10⁵) labeled 1,2,…,N in increasing order of altitude (waypoint 1
is the bottom of the mountain).

For each waypoint i>1, there is a ski run starting from waypoint i and ending at waypoint p_i (1≤p_i <i). This run has difficulty di(0≤d_i≤10⁹ ) and enjoyment e_i (0≤e_i ≤10⁹ ).

Each of Bessie's M friends (1≤M≤10⁵) will do the following: They will pick some initial waypoint i to start at, and then follow the runs downward (to p_i , then to  p_pi, and so forth) until they get to waypoint 1.

The enjoyment each friend gets is equal to the sum of the enjoyments of the runs they follow. Each friend also has a different skill level s_j (0≤s_j≤10⁹ ) and courage level c_j (0≤c_j≤10), which limits them to selecting an initial waypoint that results in them taking at most c_j runs with difficulty greater than s_j.

For each friend, compute the maximum enjoyment they can get.

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

The first line contains N.

Then for each i from 2 to N, a line follows containing three space-separated integers p_i, d_i, and e_i.

The next line contains M.

The next M lines each contain two space-separated integers s_j and c_j.

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

Output M lines, with the answer for each friend on a separate line.

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:

4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0

SAMPLE OUTPUT:

0
300
500
300
500
500
300
500

1.The first friend cannot start any waypoint other than 1, since any other waypoint would cause them to take at least one run with difficulty greater than 19. Their total enjoyment is 0.
2.The second friend can start at waypoint 4 and take runs down to waypoint 2 and then 1. Their total enjoyment is 100+200=300. They take one run with difficulty greater than 19.
3.The third friend can start at waypoint 3 and take runs down to waypoint 2
and then 1. Their total enjoyment is 300+200=500. They take two runs with difficulty greater than 19.

SCORING:

Inputs 2-4: N,M≤1000
Inputs 5-7: All c_j=0
Inputs 8-17: No additional constraints.

Problem credits: Brandon Wang

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

咨询一对一备赛规划

Deep in the countryside, Farmer John’s cows aren’t just ordinary farm animals—they are part of a clandestine bovine intelligence network. Each cow carries an ID number, carefully assigned by the elite cow cryptographers. However, due to Farmer John's rather haphazard tagging system, some cows ended up with the same ID.

Farmer John noted that there are N(1≤N≤2⋅10⁵) unique ID numbers, and for each unique ID d_i (0≤d_i≤10⁹), there are ni(1≤n_i≤10⁹) cows who shared it.

The cows can only communicate in pairs, and their secret encryption method has one strict rule: two cows can only exchange information if they are not the same cow and the sum of their ID numbers equals either A or B(0≤A≤B≤2⋅10⁹). A cow can only engage in one conversation at a time (i.e., no cow can be part of more than one pair).

Farmer John would like to maximize the number of disjoint communication pairs to ensure the best information flow. Can you determine the largest number of conversations that can happen at once?

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

The first line contains N, A, B.

The next N lines each contain n_i and d_i. No two di are the same.

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

The maximum number of disjoint communicating pairs that can be formed at the same time.

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:

4 4 5
17 2
100 0
10 1
200 4

SAMPLE OUTPUT:

118

A cow with an ID of 0 can communicate with another cow with an ID of 4 because the sum of their IDs is 4. Since there are a total of 100 cows of ID 0
and 200 cows of ID 4, there can be up to 100 communicating pairs with this combination of IDs.

A cow with an ID of 4 can also communicate with another cow with an ID of 1
(sum to 5). There are 10 cows of ID 1 and 100 remaining unpaired cows of ID 4
, allowing for another 10 pairs.

Finally, a cow with an ID of 2 can communicate with another cow of the same ID. Since there are a total of 17 cows of ID 2, there can be up to 8 more pairs.

In total, there are 100+10+8=118 communicating pairs. It can be shown that this is the maximum possible number of pairs.

SAMPLE INPUT:

4 4 5
100 0
10 1
100 3
20 4

SAMPLE OUTPUT:

30

Pairing IDs 0 and 4 makes 20 pairs, while pairing IDs 1 and 3 makes 10 pairs. It can be shown that this is the optimal pairing, resulting in a total of 30
pairs.

SCORING:

Inputs 3-4: A=B
Inputs 5-7: N≤1000
Inputs 8-12: No additional constraints

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Lately, the cows on Farmer John's farm have been infatuated with watching the show Apothecowry Dairies. The show revolves around a clever bovine sleuth CowCow solving problems of various kinds. Bessie found a new problem from the show, but the solution won't be revealed until the next episode in a week! Please solve the problem for her.

You are given integers M and K (1≤M≤10⁹,1≤K≤31). Please choose a positive integer N and construct a sequence a of N non-negative integers such that the following conditions are satisfied:

1≤N≤100
a₁+a₂+⋯+a_N=M
popcount(a₁)⊕ popcount(a₂)⊕⋯⊕ popcount(a_N)=K
If no such sequence exists, print −1.

† popcount(x) is the number of bits equal to 1 in the binary representation of the integer x. For instance, the popcount of 11 is 3 and the popcount of 16 is 1.

†⊕is the bitwise xor operator.

The input will consist of T (1≤T≤5⋅10³) independent test cases.

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

The first line contains T.

The first and only line of each test case has M and K.

It is guaranteed that all test cases are unique.

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

Output the solutions for T test cases as follows:

If no answer exists, the only line for that test case should be −1.

Otherwise, the first line for that test case should be a single integer N, the length of the sequence -- (1≤N≤100).

The second line for that test case should contain N space-separated integers that satisfy the conditions -- (0≤a_i≤M).

SAMPLE INPUT:

3
2 1
33 5
10 5

SAMPLE OUTPUT:

2
2 0
3
3 23 7
-1

In the first test case, the elements in the array a=[2,0] sum to 2. The xor sum of popcounts is 1⊕0=1. Thus, all the conditions are satisfied.

In the second test case, the elements in the array a=[3,23,7] sum to 33. The xor sum of the popcounts is 2⊕4⊕3=5. Thus, all conditions are satisfied.

Other valid arrays are a=[4,2,15,5,7] and a=[1,4,0,27,1].

It can be shown that no valid arrays exist for the third test case.

SCORING:

Input 2: M≤8,K≤8
Inputs 3-5: M>2^K
Inputs 6-18: No additional constraints.

Problem credits: Aakash Gokhale

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

咨询一对一备赛规划

Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has N (1≤N≤10⁵) bottles that he is trying to fill. Each bottle initially contains some amount of milk mi (0≤m_i≤10⁹). Every day, he takes A (1≤A≤N)
bottles and fills each bottle with one unit of milk.

Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo Milk, knows about Farmer John's production processes and has a plan to curtail his business. Every day, after Farmer John fills his A bottles, Farmer Nhoj will sneakily steal one unit of milk from each of B (0≤B<A) different nonempty bottles. To remain sneaky, Farmer Nhoj chooses B so that it is strictly less than A, so that it is less likely for Farmer John to discover him.

After D(1≤D≤10⁹) days, Farmer John will sell his OohMoo Milk. If a bottle has M
units of milk, it will sell for M² moonies.

Let P be the unique profit such that FJ can guarantee that he makes at least P profit regardless of how FN behaves, and FN can guarantee that FJ makes at most P profit regardless of how FJ behaves. Output the value of P modulo 10⁹+7.

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

The first line of the input contains N and D, where N is the number of bottles and D is the number of days that take place.

The second line of the input contains A and B representing the number of units of milk that Farmer John fills and Farmer Nhoj steals respectively.

The third line of the input contains N space-separated integers m_i representing the initial amount of milk in each bottle.

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

Output the value of P modulo 10⁹+7.

SAMPLE INPUT:

5 4
4 2
4 10 8 10 10

SAMPLE OUTPUT:

546

On the first day, Farmer John could add milk to the second, third, fourth, and fifth bottles. Then, Farmer Nhoj could remove milk from the second and fourth bottles.

Thus, the new amount of milk in each bottle is

[4,10,8,10,10]→[4,11,9,11,11]→[4,10,9,10,11].

After four days, the amount of milk in each bottle could be

[4,10,8,10,10]→[4,10,9,10,11]→[4,10,10,11,11]→[4,11,11,11,11]→[4,11,11,12,12].

The total amount of moonies Farmer John would make in this situation is 4²+11²+11²+12²+12²=546. It can be shown that this is the value of P.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

777

SAMPLE INPUT:

5 1000000000
3 1
0 1 2 3 4

SAMPLE OUTPUT:

10

Make sure you output P modulo 10⁹+7.

SCORING:

Inputs 4-6: N,D≤1000.
Inputs 7-10: D≤10⁶.
Inputs 11-20: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

**Note: The time limit for this problem is 3s, 1.5x the default.**

Farmer John has N(2≤N≤2⋅10⁵) cows numbered from 1 to N. An election is being held in FJ's farm to determine the two new head cows in his farm. Initially, it is known that cow i will vote for cow a_i  (1≤a_i ≤N).

To determine the two head cows, FJ will hold his election in the following process:

Choose an arbitrary subset S of his cows that contains at least one cow but not all cows. FJ is able to choose cow x as the first head cow if its votes appear most frequently among all votes cast by cows in S.
FJ is able to choose cow y as the second head cow if its votes appear most frequently among votes cast by cows not in S.
For a fixed subset S, FJ denotes the diversity between his head cows as |x−y|. As FJ does not like having leaders with similar numbers, he wants to choose S
such that the diversity is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is 0.

However, some cows keep changing their minds, and FJ may have to rerun the election many times! Therefore, he asks you Q (1≤Q≤10⁵) queries. In each query, a cow changes their vote. After each query, he asks you for the maximum possible diversity among his new head cows.

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

The first line contains N and Q.

The following line contains a₁,a₂,…,a_N.

The following Q lines contain two integers i and x, representing the update a_i=x
(1≤i,x≤N).

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

Output Q lines, the i'th of which is the maximum possible diversity after the first i
queries.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
3
2

After the first query, a=[1,2,4,4,5]. At the first step of the election, FJ can make S={1,3}. Here, cow 1 receives one vote and cow 4 receives one vote. Therefore, FJ can choose either cow 1 or cow 4 as its first head cow.

For all cows not in the election, cow 2 receives one vote, cow 4 receives one vote, and cow 5 also receives one vote. Therefore, FJ can choose any one of cows 2, 4,or 5 to be its second head cow.

To obtain the maximum diversity, FJ can choose cow 1 as the first head cow and cow 5 as the second head cow. Therefore, the diversity is |1−5|=4.

After the second query, a=[2,2,4,4,5] and FJ can make S={4,5}. Then, he can choose 5 as the first head cow and cow 2 as the second head cow. The maximum possible diversity is |5−2|=3.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
4
4
7
7

SCORING:

Inputs 3-4: N,Q≤100
Inputs 5-7: N,Q≤3000
Inputs 8-15: No additional constraints.
Problem credits: Chongtian Ma and Haokai Ma

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

咨询一对一备赛规划

You have a long string S of Ms and Os and an integer K≥1. Count the number of ways of ways to decompose S into subsequences such that each subsequence is MOOOO....O with exactly K Os, modulo 10⁹+7.

Since the string is very long, you are not given it explicitly. Instead, you are given an integer L (1≤L≤10¹⁸), and a string T of length N (1≤N≤10⁶). The string S is the concatenation of L copies of the string T.

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

The first line contains K, N, and L.
The second line contains the string T of length N. Every character is either an M or an O.

It is guaranteed that the number of decompositions of S is nonzero.

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

Output the number of decompositions of string S, modulo 10⁹+7.

SAMPLE INPUT:

2 6 1
MOOMOO

SAMPLE OUTPUT:

1

The only way to decompose S into MOOs is to let the first three characters form a MOO and the last three characters form another MOO.

SAMPLE INPUT:

2 6 1
MMOOOO

SAMPLE OUTPUT:

6

There are six distinct ways to decompose the string into subsequences (uppercase letters form one MOO, lowercase letters form another):

MmOOoo
MmOoOo
MmOooO
MmoOOo
MmoOoO
MmooOO

SAMPLE INPUT:

1 4 2
MMOO

SAMPLE OUTPUT:

4

SAMPLE INPUT:

1 4 100
MMOO

SAMPLE OUTPUT:

976371285

Make sure to take the answer modulo 10⁹+7.

SCORING:

Inputs 5-7: K=1, L=1
Inputs 8-10: K=2, N≤1000, L=1
Inputs 11-13: K=1
Inputs 14-19: L=1
Inputs 20-25: No additional constraints.

Problem credits: Dhruv Rohatgi

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

咨询一对一备赛规划