作者： chenchen

2025年2月的比赛以算法编程问题为特色，涵盖了广泛的技术和难度水平。

在为期4天的比赛中，共有9339名不同的用户登录。来自100多个不同国家的7157名参与者提交了至少一个解决方案。3324名参与者来自美国，其中中国、加拿大、韩国、罗马尼亚、马来西亚、印度和新加坡的参与程度也很高。

总计有18455份已评级的提交材料，按语言细分如下：

11253 C++17
2750 Python-3.6.9
2194 C++11
2108 Java
128 C
22 Python-2.7.17

以下是白金、金牌、银牌和铜牌比赛的详细结果。您还可以找到每个问题的解决方案和测试数据。

USACO 2025年 2 月竞赛，白金奖

白金组共有 314 名参与者，其中 233 名是大学预科生。得分最高的成员的成绩在这里。祝贺所有最优秀的参赛者取得优异的成绩！

1 Min Max Subarrays
查看问题 | 测试数据 | 解决方案
2 Transforming Pairs
查看问题 | 测试数据 | 解决方案
3 True or False Test
查看问题 | 测试数据 | 解决方案

USACO 2025 年 2 月比赛，金奖

黄金组共有 1196 名参与者，其中 879 名是大学预科生。所有在本次比赛中获得 700 分或更高认证分数的参赛者将自动晋升到白金组。获得晋升的美国大学预科生名单在这里。

1 Bessie's Function
查看问题 | 测试数据 | 解决方案
2 The Best Subsequence
查看问题 | 测试数据 | 解决方案
3 Friendship Editing
查看问题 | 测试数据 | 解决方案

USACO 2025 年 2 月比赛，银奖

白银组共有 3185 名参与者，其中 2451 名是大学预科生。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋级金牌组。

1 The Best Lineup
查看问题 | 测试数据 | 解决方案
2 Vocabulary Quiz
查看问题 | 测试数据 | 解决方案
3 Transforming Pairs
查看问题 | 测试数据 | 解决方案

USACO 2025 年 2 月比赛，铜奖

白银组共有 4875 名参与者，其中 3712 名是大学预科生。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋级银奖组。

1 Reflection
查看问题 | 测试数据 | 解决方案
2 Making Mexes
查看问题 | 测试数据 | 解决方案
3 Printing Sequences
查看问题 | 测试数据 | 解决方案

结束语

2024-25赛季似乎转瞬即逝，又一场成功的比赛已经过去。我很高兴看到强劲的表现和大量晋升，以及比赛本身的顺利运作。

对于那些尚未晋升的人，请记住，你练习得越多，你的算法编码技能就会越好——请坚持下去！USACO竞赛旨在挑战即使是最优秀的学生，要想在他们身上脱颖而出，可能需要付出大量的努力。

大量的人为USACO竞赛的质量和成功做出了贡献。本次竞赛的协助人员包括Chongtian Ma, Alex Liang, Haokai Ma, Andrew Li, Avnith Vijayram, Michelle Wei, Nick Wu, Nathan Wang, Brandon Wang, Spencer Compton, Tina Wang, Jichao Qian, Suhas Nagar, Ho Tin Fan, Daniel Zhang, William Lin, Larry Xing, Weiming Zhou, Benjamin Chen, Andi Qu, Thomas Liu, and Benjamin Qi。也感谢我们的翻译帮助我们扩大比赛的范围。最后，我们非常感谢USACO赞助商的慷慨支持：Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech和Jump Trading。

我们期待着再次见到大家参加公开赛，我们的全国冠军！

编码愉快！

Bessie is learning to code using a simple programming language. She first defines a valid program, then executes it to produce some output sequence.

Defining:

A program is a nonempty sequence of statements.
A statement is either of the form "PRINT c" where c is an integer, or "REP o", followed by a program, followed by "END," where o is an integer that is at least 1.

Executing:

Executing a program executes its statements in sequence.
Executing the statement "PRINT c" appends c to the output sequence.
Executing a statement starting with "REP o" executes the inner program a total of o times in sequence.

An example of a program that Bessie knows how to write is as follows.

The program outputs the sequence [1,2,2,1,2,2,1,2,2].

Bessie wants to output a sequence of N (1≤N≤100) positive integers. Elsie challenges her to use no more than K (1≤K≤3) "PRINT" statements. Note that Bessie can use as many "REP" statements as she wants. Also note that each positive integer in the sequence is no greater than K.

For each of T (1≤T≤100) independent test cases, determine whether Bessie can write a program that outputs some given sequence using at most K "PRINT" statements.

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

The first line contains T.

The first line of each test case contains two space-separated integers, N and K.

The second line of each test case contains a sequence of N space-separated  positive integers, each at most K, which is the sequence that Bessie wants to produce.

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

For each test case, output "YES" or "NO" (case sensitive) on a separate line.

SAMPLE INPUT:

2
1 1
1
4 1
1 1 1 1

SAMPLE OUTPUT:

YES
YES

For the second test case, the following code outputs the sequence [1,1,1,1] with 1 "PRINT" statement.

SAMPLE INPUT:

11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

SAMPLE OUTPUT:

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

For the first test case, the following code outputs the sequence [1,2,2,2] with 2
"PRINT" statements.

For the second test case, the answer is "NO" because it is impossible to output the sequence [1,1,2,1] using at most 2 "PRINT" statements.

For the sixth test case, the following code outputs the sequence [3,3,1,2,2,1,2,2]
with 3 "PRINT" statements.

SCORING:

Input 3: K=1
Inputs 4-7: K≤2
Inputs 8-13: No additional constraints.

Problem credits: Alex Liang

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

咨询一对一备赛规划

You are given an array a of N non-negative integers a₁,a₂,…,a_N (1≤N≤2⋅10⁵,0≤a_i≤N). In one operation, you can change any element of a
to any non-negative integer.

The mex of an array is the minimum non-negative integer that it does not contain. For each i in the range 0 to N inclusive, compute the minimum number of operations you need in order to make the mex of a equal i.

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

The first line contains N.
The next line contains a₁,a₂,…,a_N.

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

For each i in the range 0 to N, output the minimum number of operations for i on a new line. Note that it is always possible to make the mex of a equal to any i in the range 0 to N.

SAMPLE INPUT:

4
2 2 2 0

SAMPLE OUTPUT:

1
0
3
1
2

• To make the mex of a equal to 0, we can change a4 to 3 (or any positive integer). In the resulting array, [2,2,2,3], 0 is the smallest non-negative integer that the array does not contain, so 0 is the mex of the array.
• To make the mex of a equal to 1, we don't need to make any changes since 1 is already the smallest non-negative integer that a=[2,2,2,0] does not contain.
• To make the mex of a equal to 2, we need to change the first three elements of a. For example, we can change a to be [3,1,1,0].

SCORING:

Inputs 2-6: N≤10³

Inputs 7-11: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Farmer John has a square canvas represented by an N by N grid of cells (2≤N≤2000, N is even). He paints the canvas according to the following steps:

1.First, he divides the canvas into four equal quadrants, separated by horizontal and vertical lines through the center of the canvas.
2.Next, he paints a lovely painting in the top-right quadrant of the canvas. Each cell of the top-right quadrant will either be painted (represented by '#') or unpainted (represented by '.').
3.Finally, since he is so proud of his painting, he reflects it across the previously mentioned horizontal and vertical lines into the other quadrants of the canvas.

For example, suppose N=8 and FJ painted the following painting in the top-right quadrant in step 2:

.#..
.#..
.##.
....

Then after reflecting across the horizontal and vertical lines into the other quadrants in step 3, the canvas would look as follows:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

However, while FJ was sleeping, Bessie broke into his barn and stole his precious canvas. She totally vandalized the canvas—removing some painted cells and adding more painted cells! Before FJ woke up, she returned the canvas to FJ.

FJ would like to modify his canvas so that it once again satisfies the reflective condition: that is, it is the result of reflecting the top-right quadrant into each of the other quadrants. Since he only has a limited number of resources, he would like to achieve this in as few operations as possible, where a single operation consists of either painting a cell or removing paint from a cell.

You are given the canvas after Bessie's vandalism, as well as a sequence of U
(0≤U≤10⁵) updates to the canvas, each toggling a single cell to '.' if it is '#', or vice versa. Before any updates, and after each update, output the minimum number of operations x FJ needs to perform so that the reflective condition is satisfied.

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

The first line contains integers N and U.

The next N lines each contain N characters representing the canvas after Bessie's vandalism. Every character is either '#' or '.'.

The following U lines each contain integers r and c, where 1≤r,c≤N, representing an update to the cell in the rth row from the top and cth column from the left of the canvas.

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

Output U+1 lines representing x before any updates and after each update.

SAMPLE INPUT:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

SAMPLE OUTPUT:

4
3
2
1
0
1

The following canvas satisfies the reflective condition and differs from the original canvas by 4 operations:

....
####
####
....

It is impossible to make the original canvas satisfy the reflective condition using fewer than 4 operations.

After updating (1,3), the canvas looks like this:

....
##.#
####
..##
It now takes 3 operations to make the canvas satisfy the reflective condition.

After updating (2,3), the canvas looks like this:

....
####
####
..##

It now takes 2 operations to make the canvas satisfy the reflective condition.

SCORING:

Inputs 2-3: N≤4
Inputs 4-6: U≤10
Inputs 7-16: No additional constraints.

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

Bessie the brilliant bovine has discovered a new fascination—mathematical magic! One day, while trotting through the fields of Farmer John’s ranch, she stumbles upon two enchanted piles of hay. The first pile contains a bales, and the second pile contains b bales (1≤a,b≤10¹⁸).

Next to the hay, half-buried in the dirt, she discovers an ancient scroll. As she unfurls it, glowing letters reveal a prophecy:

To fulfill the decree of the Great Grasslands, the chosen one must transform these two humble hay piles into exactly c and d bales—no more, no less.

Bessie realizes she can only perform the following two spells:

She can magically conjure new bales to increase the first pile’s size by the amount currently in the second pile.
She can magically conjure new bales to increase the second pile’s size by the amount currently in the first pile.

She must perform these operations sequentially, but she can perform them any number of times and in any order. She must reach exactly c bales in the first pile and d bales in the second pile (1≤c,d≤10¹⁸).

For each of T(1≤T≤10⁴) independent test cases, output the minimum number of operations needed to fulfill the prophecy, or if it is impossible to do so, output -1.

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

The first line contains T.

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

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

Output T lines, the answer to each test case.

SAMPLE INPUT:

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

SAMPLE OUTPUT:

-1
3
-1
0

In the first test case, it is impossible since b>d initially, but operations can only increase b.

In the second test case, initially the two piles have (5,3) bales. Bessie can first increase the first pile by the amount in the second pile, resulting in (8,3) bales. Bessie can then increase the second pile by the new amount in the first pile, and do this operation twice, resulting in (8,11) and finally (8,19) bales. This matches c and d and is the minimum number of operations to get there.

Note that the third test case has a different answer than the second because c and d are swapped (the order of the piles matters).

In the fourth test case, no operations are necessary.

SAMPLE INPUT:

1
1 1 1 1000000000000000000

SAMPLE OUTPUT:

999999999999999999

SCORING:

Inputs 3-4: max(c,d)≤20⋅min(a,b)
Inputs 5-7: T≤10 and a,b,c,d≤10⁶
Inputs 8-12: No additional constraints

Problem credits: Benjamin Qi

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

咨询一对一备赛规划

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

咨询一对一备赛规划