作者： chenchen

USACO 2024 年 12 月的比赛以算法编程问题为特色，涵盖广泛的技术和难度级别。

在为期 4 天的比赛中，共有 15564 名不同的用户登录了比赛。共有 12170 名参与者提交了至少一个解决方案，来自 100+ 个国家/地区。4940 名参与者来自美国，其中来自中国、加拿大、韩国、罗马尼亚、马来西亚和印度的参与人数也很高。 总共有 32484 篇评分的提交，按语言细分如下：

18801 C++17
5079 C++11
4910 Python-3.6.9
3344 Java
230 C
120 Python-2.7.17

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

USACO 2024 年 12 月竞赛，白金奖

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

1 All Pairs Similarity
查看问题 | 测试数据 | 解决方案
2 It's Mooin' Time
查看问题 | 测试数据 | 解决方案
3 Maximize Minimum Difference
查看问题 | 测试数据 | 解决方案

USACO 2024 年 12 月比赛，金奖

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

1 Cowdependence
查看问题 | 测试数据 | 解决方案
2 Interstellar Intervals
查看问题 | 测试数据 | 解决方案
3 Job Completion
查看问题 | 测试数据 | 解决方案

USACO 2024 年 12 月比赛，银奖

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

1 Cake Game
查看问题 | 测试数据 | 解决方案
2 Deforestation
查看问题 | 测试数据 | 解决方案
3 2D Conveyor Belt
查看问题 | 测试数据 | 解决方案

USACO 2024 年 12 月比赛，铜奖

铜牌组共有 11472 名参与者，其中 8373 名是大学预科生。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋升到银牌组。

1 Roundabout Rounding
查看问题 | 测试数据 | 解决方案
2 Farmer John's Cheese Block
查看问题 | 测试数据 | 解决方案
3 It's Mooin' Time
查看问题 | 测试数据 | 解决方案

结语

2024-25年USACO赛季开局良好！本次比赛的参赛人数众多，许多学生都获得了晋级（有些学生甚至晋级了多个组别）。对于那些尚未晋级的学生，请记住，练习得越多，你的算法编码技能就会越强——请坚持下去！USACO比赛旨在挑战最优秀的学生，要想脱颖而出，需要付出大量努力。为了帮助你修复代码中的任何错误，你现在可以使用“分析模式”重新提交你的解决方案，并从评判服务器获取反馈。

提醒大家注意我们竞赛中学术诚信的重要性——请记住，我们对作弊采取零容忍政策。为了减少作弊的诱因，同时保持我们的竞赛对所有人开放以供练习，我们现在只报告晋升为白金组的美国学生的金牌组成绩（我们仍会向询问美国和非美国学生成绩的大学招生官核实USACO成绩，但如果学生因作弊被取消资格，也会报告）。

众多人士为USACO竞赛的质量和成功做出了贡献。本次竞赛的协助人员包括周伟明， 马崇天， 梁伟霖， 苏哈斯纳加尔， 齐本杰明， Linda Zhao， Agastya Goel， Gavin Ye， Tina Wang， Jiahe Lu， Nick Wu， Brandon Wang， Andi Qu， 钱继超， Daniel Zhang， William Lin， Larry 邢， Michelle Wei， Thomas Liu， Richard Qi， Benjamin Chen， Austin 耿和 Eric Yang。还要感谢我们的翻译人员帮助我们扩大了竞赛的影响范围。最后，我们非常 感谢 USACO 赞助商的慷慨支持：Citadel， Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech 和 跳跃交易。

我们期待着2025年1月比赛时再次与大家相聚。

祝您编码愉快！

Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest."

Elsie still doesn't understand so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as a string of lowercase letters of length N (3≤N≤20000). A moo is generally defined as the substring cicjcj where some character ci followed directly by 2 occurrences of some character c_j where c_i≠c_j. According to Farmer John, Bessie moos a lot, so if some moo appears at least F(1≤F≤N) times in the contest, that might be from Bessie.

However, Farmer John's download might have been corrupted, and the text file might have up to one character that differs from the original file. Print all possible moos that Bessie could have made taking the potential error into account, sorted in alphabetical order.

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

The first line contains N and F, representing the length of the string and the frequency threshold for a moo by Bessie.

The second line contains a string of lowercase letters of length N, representing the contest.

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

Print out the number of possible moos that Bessie makes, followed by a lexicographically sorted list of the moos. Each moo should appear on a separate line.

SAMPLE INPUT:

10 2
zzmoozzmoo

SAMPLE OUTPUT:

1
moo

In this case, no character change affects the answer. The only moo Bessie made was "moo".

SAMPLE INPUT:

17 2
momoobaaaaaqqqcqq

SAMPLE OUTPUT:

3
aqq
baa
cqq

In this case, the a at position 8 (zero-indexed) could have been corrupted from a b which would have resulted in "baa" being a moo that Bessie made twice. Alternatively, the q at position 11 could have been corrupted from a c which would have resulted in "cqq" being a possible moo that Bessie made. "aqq" can be made by swapping the c with an a.

SAMPLE INPUT:

3 1
ooo

SAMPLE OUTPUT:

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

SCORING:

Inputs 4-8: N≤100
Inputs 9-13: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John has a block of cheese in the shape of a cube. It lies on the 3-dimensional coordinate plane, extending from (0,0,0)to (N,N,N) (2≤N≤1000). Farmer John will perform a series of Q (1≤Q≤2⋅10⁵) update operations to his cheese block.

For each update operation, FJ will carve out the 1 by 1 by 1 block of cheese extending from integer coordinates (x,y,z) to (x+1,y+1,z+1), where 0≤x,y,z<N. It is guaranteed that there will exist a 1 by 1 by 1block of cheese at the location FJ carves. Since FJ is playing Moocraft, gravity does not cause parts of the cheese to fall if cheese below is carved.

After each update, output the number of distinct configurations that FJ can stick a 1 by 1 by N brick in the cheese block such that no part of the brick overlaps with any remaining cheese. Every vertex of the brick must have integer coordinates in the range [0,N] for all three axes. FJ may rotate the brick however he wants.

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

The first line contains N and Q.

The following Q lines contain x, y, and z, the coordinates to be carved.

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

After each update operation, output an integer, the number of configurations.

SAMPLE INPUT:

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

SAMPLE OUTPUT:

0
0
1
2
5

After the first three updates, the 1×2×1brick spanning [0,1]×[0,2]×[0,1] does not overlap with the remaining cheese, so it contributes toward the answer.

SCORING:

Inputs 2-4: N≤10 and Q≤1000
Inputs 5-7: N≤100 and Q≤1000
Inputs 8-16: No additional constraints

Problem credits: Chongtian Ma, Alex Liang

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

咨询一对一备赛规划

Bessie the cow is back in school! She has started doing her math homework in which she is tasked to round positive integers to powers of 10.

To round a positive integer a to the nearest 10^b, where b is a positive integer, Bessie first locates the b'th digit from the right. Let x denote this digit.

If x ≥5, Bessie adds 10^b to a.

Then, Bessie sets all the digits including and to the right of the b'th digit from the right to be 0.

For instance, if Bessie wanted to round 456 to the nearest 10² (hundred), Bessie would first locate the 2nd digit from the right which is 5. This means x=5. Then since x≥5, Bessie adds 100 to a. Finally, Bessie sets all the digits in a to the right of and including the 2nd digit from the right to be 0, resulting in 500.

However, if Bessie were to round 446 to the nearest 102, she would end up with 400.

After looking at Bessie's homework, Elsie thinks she has invented a new type of rounding: chain rounding. To chain round to the nearest 10^b, Elsie will first round to the nearest 101, then the nearest 102, and so on until the nearest 10^b.

Bessie thinks Elsie is wrong, but is too busy with math homework to confirm her suspicions. She tasks you to count how many integers x at least 2 and at most N (1≤N≤10⁹) exist such that rounding x to the nearest 10^P is different than chain rounding to the nearest 10^P, where P is the smallest integer such that 10^P≥x.

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 and only line of input in every test case contains a single integer N. All N
within the same input file are guaranteed to be distinct.

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 how many integers at least 2 and at most N exist that are different when using the two rounding methods.

SAMPLE INPUT:

4
1
100
4567
3366

SAMPLE OUTPUT:

0
5
183
60

Consider the second test case in the sample. 48 should be counted because 48
chain rounded to the nearest 10² is 100(48→50→100), but 48rounded to the nearest 10² is 0.

In the third test case, two integers counted are 48 and 480. 48 chain rounds to 100 instead of to 0 and 480 chain rounds to 1000 instead of 0. However, 67 is not counted since it chain rounds to 100 which is 67rounded to the nearest 10².

SCORING:

Inputs 2-4: N≤10³
Inputs 5-7: N≤10⁶
Inputs 8-13: No additional constraints.

Problem credits: Weiming Zhou

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

咨询一对一备赛规划

Farmer John's milk factory can be described by an N by N (1≤N≤1000) grid of cells that contain conveyor belts. Position (a,b) describes the cell that is in the a-th row from the top and b-th column from the left. There are 5 types of cells:

1."L" — the cell is a leftward facing conveyor belt which moves all items on it 1 cell left every time unit.
2."R" — the cell is a rightward facing conveyor belt which moves all items on it 1 cell right every time unit.
3."U" — the cell is an upward facing conveyor belt which moves all items on it 1 cell up every time unit.
4."D" — the cell is a downward facing conveyor belt which moves all items on it 1 cell down every time unit.
5."?" — Farmer John has not built a conveyor belt at that cell yet.

Note that conveyor belts can also move items outside the grid. A cell c is unusable if an item placed at cell c will never exit the conveyor belt grid (i.e. it will move around in the grid forever).

Initially, Farmer John has not started building the factory so all cells start out as "?". For the next Q (1≤Q≤2⋅10⁵) days starting from day 1 and ending at day Q
, Farmer John will choose a cell that does not have a conveyor belt and build a conveyor belt at the cell.

Specifically, during the i-th day, Farmer John will build a conveyor belt of type t_i (t_i ∈{L,R,U,D}) at position (r_i,c_i) (1≤r_i,c_i≤N). It is guaranteed that there is no conveyor belt at position (r_i,c_i).

After each day, help Farmer John find the minimum number of unusable cells he can achieve by optimally building conveyor belts on all remaining cells without a conveyor belt.

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

The first line contains N and Q .

The i-th of the next Q lines contains r_i, c_i, and t_i in that order.

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

Q lines, the i-th of which describing the minimum number of unusable cells if Farmer John fills optimally builds conveyor belts on all remaining cells that do not currently have a conveyor belt.

SAMPLE INPUT:

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

SAMPLE OUTPUT:

0
0
0
2
3

The conveyor belt after the fifth day is shown below.
RL?
U??
?DL
One optimal way to build conveyor belts on the remaining cells is as follows.

RLR
URR
LDL

In this configuration, the cells at (1,1), (1,2), and (2,1) are unusable.

SAMPLE INPUT:

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

SAMPLE OUTPUT:

0
2
2
4
4
6
6
9

The conveyor belt after the eighth day is shown below.

RLD
D?U
URL

No matter what conveyor belt Farmer John can build at the center, all cells will be unusable.

SAMPLE INPUT:

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

SAMPLE OUTPUT:

0
0
0
0
0
0
0
0
11
11
11
11
13

SCORING:

Inputs 4-5: N≤10
Inputs 6-7: N≤40
Inputs 8-13: No additional constraints

Problem credits: Alex Liang

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

咨询一对一备赛规划

Farmer John is expanding his farm! He has identified the perfect location in the Red-Black Forest, which consists of N trees (1≤N≤10⁵  ) on a number line, with the i-th tree at position x_i (−109≤x_i ≤10⁹).

Environmental protection laws restrict which trees Farmer John can cut down to make space for his farm. There are K restrictions (1≤K≤10⁵ ) specifying that there must always be at least t_i trees (1≤t_i ≤N) in the line segment [l_i,r_i]
, including the endpoints (−109≤l_i≤r_i≤10⁹). It is guaranteed that the Red-Black Forest initially satisfies these restrictions.

Farmer John wants to make his farm as big as possible. Please help him compute the maximum number of trees he can cut down while still satisfying all the restrictions!

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

Each input consists of T (1≤T≤10) independent test cases. It is guaranteed that the sums of all N and of all K within an input each do not exceed 3⋅10⁵.

The first line of input contains T. Each test case is then formatted as follows:

The first line contains integers N and K.
The next line contains the N integers x₁,…,x_N.
Each of the next K lines contains three space-separated integers: l_i, r_i and t_i.

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

For each test case, output a single line with an integer denoting the maximum number of trees Farmer John can cut down.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
4
3

For the first test case, Farmer John can cut down the first 4 trees, leaving trees at

x_i = 2,6,7 to satisfy the restriction.

For the second test case, the additional restriction does not affect which trees Farmer John can cut down, so he can cut down the same trees and satisfy both restrictions.

For the third test case, Farmer John can only cut down at most 3 trees because there are initially 7 trees but the second restriction requires him to leave at least 4 trees uncut.

SCORING:

Input 2: N , K≤16
Inputs 3-5: N, K≤1000
Inputs 6-7:t_i=1 for all i=1,…,K.
Inputs 8-11: No additional constraints.

Problem credits: Tina Wang, Jiahe Lu, Benjamin Qi

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

咨询一对一备赛规划

Bessie and Elsie have discovered a row of N cakes (2≤N≤5⋅10⁵ ,N even)
cakes, with sizes a₁,a₂,…,a_N in that order (1≤a_i≤10⁹).

Each cow wants to eat as much as possible. However, being very civilized cows, they decided to play a game to split it! The game proceeds with both cows alternating turns. Each turn consists of one of the following:

1.Bessie chooses two adjacent cakes and stacks them, creating a new cake with the sum of the sizes.
2.Elsie chooses either the leftmost or rightmost cake and puts it in her stash.

When only one cake remains, Bessie eats it, and Elsie eats all cakes in her stash. If both cows play optimally to maximize the amount of cake they eat and Bessie plays first, how much cake will each cow eat?

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

Each input consists of T (1≤T≤10) independent test cases. It is guaranteed that the sum of all N within an input does not exceed 10⁶.

Each test case is formatted as follows. The first line contains N . The next line contains N space-separated integers, a₁,a₂,…,a_N.

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

For each test case, output a line containing b and e, representing the amounts of cake Bessie and Elsie respectively will consume if both cows play optimally.

SAMPLE INPUT:

2
4
40 30 20 10
4
10 20 30 40

SAMPLE OUTPUT:

60 40
60 40

For the first test case, under optimal play,

1.Bessie will stack the middle two cakes. The cakes now have sizes [40,50,10].
2.Elsie will eat the leftmost cake. The remaining cakes now have sizes [50,10].
3.Bessie stacks the remaining two cakes.

Bessie will eat 30+20+10=60 cake, while Elsie will eat 40 cake.

The second test case is the reverse of the first, so the answer is the same.

SCORING:

Input 2: All a_i  are equal.
Input 3: N≤10
Inputs 4-7: N≤5000
Inputs 8-11: No additional constraints.

Problem credits: Linda Zhao, Agastya Goel, Gavin Ye

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

咨询一对一备赛规划

Bessie the cow has N (1≤N≤2⋅10⁵) jobs for you to potentially complete. The i-th one, if you choose to complete it, must be started at or before time s_i and takes t_i time to complete (0≤s_i ≤10¹⁸,1≤t_i ≤10¹⁸).

What is the maximum number of jobs you can complete? Time starts at 0
, and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.

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

The first line contains T, the number of independent test cases (1≤T≤10). Each test case is formatted as follows.

The first line contains N.

Each of the next N lines contains two integers s_i and t_i . Row i+1 has the details for the ith job.

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

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

For each test case, the maximum number of jobs you can complete, on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
2
2

For the first test case, you can only complete one of the jobs. After completing one job, it will then be time 2 or later, so it is too late to start the other job, which must be started at time 1 or earlier.

For the second test case, you can start the second job at time 0 and finish at time 2, then start the first job at time 2 and finish at time 5.

SCORING:

Inputs 2: Within the same test case, all t_i  are equal.
Inputs 3-4: N≤2000, s_i ,t_i ≤2000
Inputs 5-8: N≤2000
Inputs 9-16: No additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划