作者： chenchen

Bessie is helping Elsie with her upcoming vocabulary quiz. The words to be tested will be drawn from a bank of M distinct words, where no word in the bank is a prefix of another word in the bank.

While the bank is nonempty, Bessie will select a word from the bank, remove it from the bank, and read it to Elsie one character at a time from left to right. Elsie's task is to tell Bessie once she can uniquely identify it, after which Bessie will stop reading.

Bessie has already decided to read the words from the word bank in the order w₁,w₂,…,w_M. If Elsie answers as quickly as possible, how many characters of each word will Bessie read?

The words are given in a compressed format. We will first define N+1 (1≤N≤ 10⁶ ) distinct words, and then the word bank will consist of all those words that are not a prefix of another word. The words are defined as follows:

Initially, the 0th word will be the empty string.

Then for each 1≤i≤N, the ith word will be equal to the p_ith word plus an additional character at the end (0≤p_i<i). The characters are chosen such that all N+1 words are distinct.

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

The first line contains N, where N+1 is the number of words given in the  compressed format.

The next line contains p₁,p₂,…,p_N where p_i represents that the i-th word is formed by taking the pi-th word and adding a single character to the end.

Let M be the number of words that are not a prefix of some other word. The next M lines will contain w₁,w₂,…,w_M, meaning that the w_ith word will be the ith to be read. It is guaranteed that the words to be read form a permutation of the words in the word bank.

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

Output M lines, where the ith line contains the number of characters of the ith word that Bessie reads.

SAMPLE INPUT:

5
0 1 2 3 4
5

SAMPLE OUTPUT:

0

There are 6words labeled 0…5. Word 5 is the only one that is not a prefix of another word, so it is the only one in the bank. In general, once only one word is left in the bank, Elsie won't need any characters to identify it.

SAMPLE INPUT:

4
0 0 1 1
4
3
2

SAMPLE OUTPUT:

2
1
0

The bank consists of words 2, 3, and 4.

Elsie needs two characters to identify word 4 since words 3 and 4 share their first character in common.

Once Bessie reads the first character of word 3 , Elsie has enough characters to uniquely identify it, since word 4 was already read.

SAMPLE INPUT:

4
0 0 1 1
2
3
4

SAMPLE OUTPUT:

1
2
0

SCORING:

Inputs 4-5: No word has length greater than 20.
Inputs 6-10: The sum of the lengths of all words in the word bank does not exceed 10⁷.
Inputs 11-18: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Farmer John has N (1≤N≤2⋅10⁵) cows in a line a. The i'th cow from the front of line a is labeled an integer a_i (1≤a_i ≤N). Multiple cows may be labeled the same integer.

FJ will construct another line b in the following manner:

Initially, b is empty.
While a is nonempty, remove the cow at the front of a and potentially add that cow to the back of b.

FJ wants to construct line b such that the sequence of labels in b from front to back is lexicographically greatest (see the footnote).

Before FJ constructs line b, he can perform the following operation at most once:

Choose a cow in line a and move it anywhere before its current position.

Given that FJ optimally performs the aforementioned operation at most once, output the lexicographically greatest label sequence of b he can achieve.

Each input will consist of T (1≤T≤100) independent test cases.

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

The first line contains T.

The first line of each test case contains N.

The second line of each test case contains N space-separated integers a₁,a₂,…,a_N.

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

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

For each test case, output the lexicographically greatest b on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

In the first test case, FJ can move the fifth cow to directly after the second cow. Now, a=[4,3,3,2,1]. It can be shown [4,3,3,2,1] is also the lexicographically greatest b.

In the second test case, FJ can move the fourth cow to the front of the line.

In the third test case, FJ does not need to perform any operations. He can construct b by adding each cow beside the second cow to the back of b. It can be shown this results in the lexicographically greatest b.

SCORING:

Inputs 2-4: N≤100
Inputs 5-8: N≤750
Inputs 9-18: No additional constraints

FOOTNOTE:

Recall that a sequence s is lexicographically greater than a sequence t if and only if one of the following holds:

At the first position i where s_i≠t_i, s_i>s_i.
If no such i exists, s is longer than t.

Problem credits: Chongtian Ma, Haokai Ma, Andrew Li

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

咨询一对一备赛规划

Farmer John's N cows are labeled 1 to N(2≤N≤16). The friendship relationships between the cows can be modeled as an undirected graph with M (0≤M≤N(N−1)/2) edges. Two cows are friends if and only if there is an edge between them in the graph.

In one operation, you can add or remove a single edge from the graph. Count the minimum number of operations required to ensure that the following property holds: If cows a and b are friends, then for every other cow c, at least one of a
and b is friends with c.

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

The first line contains N and M.

The next M lines each contain a pair of friends a and b (1≤a<b≤N). No pair of friends appears more than once.

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

The number of edges you need to add or remove.

SAMPLE INPUT:

3 1
1 2

SAMPLE OUTPUT:

1

The network violates the property. We can add one of edges (2,3)
or (1,3), or remove edge (1,2)to fix this.

SAMPLE INPUT:

3 2
1 2
2 3

SAMPLE OUTPUT:

0
No changes are necessary.

SAMPLE INPUT:

4 4
1 2
1 3
1 4
2 3

SAMPLE OUTPUT:

1

SCORING:

Inputs 4-13: One input for each N∈[6,15] in increasing order.
Inputs 14-18: N=16

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Farmer John has a binary string of length N (1≤N≤10⁹), initially all zeros.

He will first perform M(1≤M≤2⋅10⁵) updates on the string, in order. Each update flips every character from l to r. Specifically, flipping a character changes it from 0 to 1, or vice versa.

Then, he asks you Q (1≤Q≤2⋅10⁵) queries. For each query, he asks you to output the lexicographically greatest subsequence of length k comprised of characters from the substring from l to r. If your answer is a binary string s₁s₂…s_k, then output (that is, its value when interpreted as a binary number) modulo 10⁹+7.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Recall that string A is lexicographically greater than string B of equal length if and only if at the first position i, if it exists, where A_i≠B_i, we have A_i>B_i.

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

The first line contains N, M, and Q.

The next M lines contain two integers, l and r (1≤l≤r≤N) — the endpoints of each update.

The next Q lines contain three integers, l, r, and k (1≤l≤r≤N,1≤k≤r−l+1) — the endpoints of each query and the length of the subsequence.

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

Output Q lines. The ith line should contain the answer for the ith query.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

21
13
7
3
1
5
5
3
1

After performing the M operations, the string is 10101.

For the first query, there is only one subsequence of length 5, 10101, which is interpreted as 1⋅2⁴+0⋅2³+1⋅2²+0⋅2¹+1⋅2⁰=21.

For the second query, there are 5 unique subsequences of length 4: 0101, 1101, 1001, 1011, 1010. The lexicographically largest subsequence is 1101, which is interpreted as 1⋅2³+1⋅2²+0⋅2¹+1⋅2⁰=13.

For the third query, the lexicographically largest sequence is 111, which is interpreted as 7.

SAMPLE INPUT:

9 1 1
7 9
1 8 8

SAMPLE OUTPUT:

3

SAMPLE INPUT:

30 1 1
1 30
1 30 30

SAMPLE OUTPUT:

73741816

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

SCORING:

Input 4: N≤10,Q≤1000
Input 5: M≤10
Inputs 6-7: N,Q≤1000
Inputs 8-12: N≤2⋅10⁵ 
Inputs 13-20: No additional constraints.

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

Bessie has a special function f(x) that takes as input an integer in [1,N]
and returns an integer in [1,N] (1≤N≤2⋅10⁵). Her function f(x) is defined by N
integers a₁…a_N where f(x)=a_x (1≤a_i≤N).

Bessie wants this function to be idempotent. In other words, it should satisfy f(f(x))=f(x)for all integers x∈[1,N].

For a cost of c_i, Bessie can change the value of a_i to any integer in [1,N] (1≤c_i≤10⁹). Determine the minimum total cost Bessie needs to make f(x)
idempotent.

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

The first line contains N.

The second line contains N

space-separated integers a₁,a₂,…,a_N.

The third line contains N space-separated integers c₁,c₂,…,c_N.

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

Output the minimum total cost Bessie needs to make f(x) idempotent.

SAMPLE INPUT:

5
2 4 4 5 3
1 1 1 1 1

SAMPLE OUTPUT:

3

We can change a₁=4, a₄=4, a₅=4. Since all c_i equal one, the total cost is equal to 3
, the number of changes. It can be shown that there is no solution with only 2
or fewer changes.

SAMPLE INPUT:

8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9

SAMPLE OUTPUT:

7

We change a₃=3 and a₄=4. The total cost is 2+5=7.

SCORING:

Subtasks:

Input 3: N≤20
Inputs 4-9:a_i≥i
Inputs 10-15: All a_iare distinct.
Inputs 16-21: No additional constraints.
Additionally, in each of the last three subtasks, the first half of tests will satisfy c_i=1 for all i.

Problem credits: Avnith Vijayram

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

咨询一对一备赛规划

Bessie is taking an N-question true or false test (1≤N≤2⋅10⁵). For the i-th question, she will gain a_i  points if she gets it correct, lose b_i points if she gets it incorrect, or remain even if she does not answer it (0<a_i,b_i ≤10⁹).

Bessie knows all the answers because she is a smart cow, but worries that Elsie (who is administering the test) will retroactively change up to k of the questions after the test such that Bessie does not get those questions correct.

Given Q (1≤Q≤N+1) candidate values of k (0≤k≤N), determine the number of points Bessie can guarantee for each k, given that she must answer at least k questions.

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

The first line contains N and Q.

The next N lines each contain a_i and b_i.

The next Q lines each contain a value of k. No value of k appears more than once.

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

The answer for each k on a separate line.

SAMPLE INPUT:

2 3
3 1
4 2
2
1
0

SAMPLE OUTPUT:

-3
1
7

For each value of k, it is optimal for Bessie to answer all of the questions.

SCORING:

Inputs 2-4: N≤100
Inputs 5-7: Q≤10, N≤2⋅10⁵ 
Inputs 7-20: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Answer Q(1≤Q≤10⁵) independent queries each of the following form:

You are given four integers a,b,c,d(−1018≤a,b,c,d≤10¹⁸). In one operation you can either do a+=b, or b+=a. Determine the minimum number of operations to transform (a,b) into (c,d), or if it is impossible to do so, output −1.

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

The first line contains Q.

The next Q lines each contain four integers a,b,c,d.

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

The answer for each query on a separate line.

SAMPLE INPUT:

4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3

SAMPLE OUTPUT:

2
-1
3
0

First query: (5,−3)→(2,−3)→(−1,−3)

Second query: Impossible.

Third query: (5,3)→(8,3)→(8,11)→(8,19)

Fourth query: No operations necessary.

SCORING:

Input 2: |a|,|b|,|c|,|d|≤10
Input 3: a,b≥0
Input 4: a≥0≥b
Input 5: a≤0≤b
Input 6: a,b≤0
Input 7: c,d≥0
Input 8: c≥0≥d
Input 9: c≤0≤d
Input 10: c,d≤0
Inputs 11-14: Q≤10³
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

注意：此问题的时限为 3 秒，是默认值的 1.5 倍。

You are given a length-N integer array a₁,a₂,…,a_N (2≤N≤10⁶,1≤a_i≤N
). Output the sum of the answers for the subproblem below over all N(N+1)/2
contiguous subarrays of a.

Given a nonempty list of integers, alternate the following operations (starting with the first operation) until the list has size exactly one.

1.Replace two consecutive integers in the list with their minimum.
2.Replace two consecutive integers in the list with their maximum.

Determine the maximum possible value of the final remaining integer.

For example,

[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]

In the first array, (10,3) is replaced by min(10,3)=3 and (4,3) is replaced by max(4,3)=4.

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

The first line contains N.

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

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

The sum of the answer to the subproblem over all subarrays.

SAMPLE INPUT:

2
2 1

SAMPLE OUTPUT:

4

The answer for [2] is 2, the answer for [1] is 1, and the answer for [2,1] is 1.

Thus, our output should be 2+1+1=4.

SAMPLE INPUT:

3
3 1 3

SAMPLE OUTPUT:

12

SAMPLE INPUT:

4
2 4 1 3

SAMPLE OUTPUT:

22

Consider the subarray [2,4,1,3].

1.Applying the first operation on (1, 3), our new array is [2,4,1].
2.Applying the second operation on (4, 1), our new array is [2,4].
3.Applying the third operation on (2, 4), our final number is 2.

It can be proven that 2 is the maximum possible value of the final number.

SCORING:

Inputs 4-5: N≤100
Inputs 6-7: N≤5000
Inputs 8-9: max(a)≤10
Inputs 10-13: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划