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

咨询一对一备赛规划