作者： chenchen

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

在为期 4 天的比赛中，共有 16732 名不同的用户登录了比赛。共有来自132个不同国家的14350名参与者提交了至少一个解决方案：

5794 USA 5763 CHN 483 CAN 377 KOR 151 ROU 139 IND 127 ISR
124 MYS 120 SGP 103 TWN 72 HKG 68 POL 63 DEU 58 VNM
53 IRN 46 AUS 44 GBR 40 EGY 37 JPN 33 BLR 31 FRA
29 ABW 28 GEO 23 UZB 21 ARM 20 SLV 18 ZAF 18 NZL
18 BRA 17 HRV 16 NLD 16 CUB 13 IDN 13 CHE 12 TUR
12 TKM 11 SRB 11 PAK 11 ESP 11 BDI 10 THA 10 SYR
10 KGZ 10 ASM 9 BGD 9 AUT 9 ARE 8 UKR 8 PHL
8 COL 8 CHL 8 AZE 7 AIA 6 TUN 6 SWE 6 RUS
6 MEX 6 KAZ 6 AGO 5 ITA 5 IRL 5 GRC 5 FIN
5 EST 5 ANT 5 ALA 4 PRK 4 MNG 4 MLT 4 LTU
4 HUN 4 CYP 4 ATG 4 ARG 4 AND 4 ALB 4 AFG
3 MKD 3 MAC 3 KEN 3 HTI 3 CCK 3 BGR 2 YEM
2 VGB 2 QAT 2 PRT 2 NOR 2 MCO 2 GHA 2 BWA
2 BLM 2 BEL 1 ZWE 1 VUT 1 VEN 1 URY 1 UGA
1 TTO 1 TJK 1 SWZ 1 SMR 1 SAU 1 PSE 1 NPL
1 NGA 1 NER 1 NAM 1 MNE 1 MAR 1 LUX 1 LSO
1 LAO 1 KHM 1 ISL 1 IOT 1 HMD 1 GUY 1 GUM
1 GMB 1 GAB 1 FSM 1 FJI 1 DNK 1 DJI 1 CZE
1 CRI 1 CMR 1 CIV 1 BLZ 1 BHS 1 BHR

共有 67 名白金美国大学预科参与者参加了“认证”比赛 比赛窗口。在整个比赛中，共有 38095 份分级作品，按语言细分如下：

20207 C++17
7673 C++11
5342 Python 3.6.9
4633 Java
195 C
45 Python 2.7.17

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

USACO 2023 年 12 月学术活动，白金奖

白金部门共有 673 名参与者，其中 455 名是大学预科生。最佳得分手的成绩在这里。恭喜所有顶尖选手取得优异成绩！

1 Cowntact Tracing
查看问题 | 测试数据 | 解决方案
2 A Graph Problem
查看问题 | 测试数据 | 解决方案
3 Train Scheduling
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，金奖

黄金组共有 1375 名参与者，其中 980 名是大学预科生。所有在本次比赛中得分达到或超过800分的选手将自动晋升为白金组。所有晋升者的详细结果都在这里。

1 Flight Routes
查看问题 | 测试数据 | 解决方案
2 Minimum Longest Trip
查看问题 | 测试数据 | 解决方案
3 Haybale Distribution
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，银奖

白银组共有3841名参与者，其中2967名是大学预科生。所有在本次比赛中得分达到或超过750分的参赛者将自动晋升为黄金组。

1 Bovine Acrobatics
查看问题 | 测试数据 | 解决方案
2 Cycle Correspondence
查看问题 | 测试数据 | 解决方案
3 Target Practice
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，铜奖

青铜组共有12591名参赛者，其中9707名是大学预科生。所有在本次比赛中得分达到或超过700分的选手将自动晋升为银牌组。

1 Candy Cane Feast
查看问题 | 测试数据 | 解决方案
2 Cowntact Tracing 2
查看问题 | 测试数据 | 解决方案
3 Farmer John Actually Farms
查看问题 | 测试数据 | 解决方案

结语

欢迎来到 2023-2024 USACO 赛季！我很高兴看到我们的 第一届比赛进行得很顺利，涉及的用户数量创下了历史新高。相当多的参与者得分很高并得到了晋升，尽管这是一场具有挑战性的问题阵容。看到如此强劲的表现令人鼓舞，特别是考虑到人工智能等领域的最新创新和势头可能在上升，因而对具有卓越计算机天赋的学生的要求越来越高。

对于那些尚未晋升的人， 请记住，练习越多越好 你的算法编码技能将成为 -- 拜托坚持下去！USACO竞赛旨在挑战甚至最好的学生，这可能需要大量的努力在他们身上出类拔萃。为了帮助您修复代码中的任何错误，您需要 现在可以重新提交您的解决方案并从 使用“分析模式”判断服务器。

很多人为质量做出了贡献以及USACO竞赛的成功。那些帮助过这件事的人 参赛作品包括Mihir Singhal、Agastya Goel、Chongtian 马、Suhas Nagar、Eric Hsu、Benjamin Qi、Claire Zhang、Spencer Compton、Brandon Wang、Nick Wu、Jichao Qian、Nathan Wang、Danny Mittal、Andi Quad、Ho Tin Fan、Benjamin Chen、David 胡、Richard Qi、Andrew Gu和Anand John。 谢谢 也感谢我们的翻译人员和克莱姆森CCIT提供的 我们的比赛基础设施。最后，我们心存感激 感谢USACO赞助商的慷慨支持： Citadel、Ansatz、X-Camp、TwoSigma、VPlanet 编码、EasyFunCoding、 Orijtech 和 Jump Trading。

我们期待在 2024 年 1 月的比赛中再次见到大家。

祝您编码愉快！

Farmer John is growing N (1≤N≤2⋅10⁵) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the ith plant is h_i inches, and after each day, the ith plant grows by a_i inches.

FJ likes some of his plants more than others, and he wants some specific plants to be taller than others. He gives you an array of distinct values t₁,…,t_N containing all integers from 0 to N−1 and he wants the ith plant to have exactly t_i other plants that are taller than it. Find the minimum number of days so that FJ's request is satisfied, or determine that it is impossible.

INPUT FORMAT (pipe stdin):

The first will consist of an integer T, denoting the number of independent test cases (1≤T≤10).

The first line of each test case consists of an integer N.

The second line consists of N integers hi (1≤h_i ≤109) denoting the initial height of the ith plant in inches.

The third line consists of N integers a_i (1≤a_i≤109) denoting the number of inches the ith plant grows each day.

The fourth line consists of N distinct integers t_i denoting the array that FJ gives you.

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

OUTPUT FORMAT (pipe stdout):

Output T lines, the answer to each test case on a different line. If it is not possible, 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++).

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
3
2
5
-1
-1

In the first sample input, there are 6 test cases.

In the first test case, there is only one plant, so the condition is satisfied on day 0.

In the second test case, we need the first plant to be shorter than the second plant. After day 1, the heights are 15 and 13. After day 2, the heights are both 23. After day 3, the heights are 31 and 33, and that's the first day in which the condition is satisfied.

The third and fourth test cases are similar to the second.

In the fifth test case, both plants start with an initial height of 7 and a growth rate of 8. So they will always have identical heights, and therefore the condition is never satisfied.

In the sixth test case, the condition is not satisfied initially and the growth rates are the same. So the condition can never be satisfied.

SAMPLE INPUT:

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

SAMPLE OUTPUT:

4
7
In the second sample input, there are 2 test cases.

In the first test case, the final heights after day 4 are 19, 20, 21, 18, 16.

In the second test case, the final heights after day 7 are 25, 17, 19, 35, 36.

SCORING:

Input 3: N≤2
Inputs 4-5: N≤50 and ai,hi≤103
Inputs 6-8: N≤103
Inputs 9-13: No additional constraints.
Problem credits: Chongtian Ma

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

咨询一对一备赛规划

Farmer John has N cows in a line (1≤N≤3⋅10⁵). Unfortunately, there is a sickness spreading throughout.

Initially, some cows start off infected. Every night, an infected cow spreads the sickness to the cows on their left and right (if they exist). Once a cow is infected, she stays infected.

After some amount of nights, Farmer John realizes that the issue has gotten out of control, so he tests his cows to determine who has the sickness. Find the minimum number of cows that could have started with the sickness.

INPUT FORMAT (pipe stdin):

The first line contains N, the number of cows that Farmer John has.
The next line contains an N character bitstring of only 1s and 0s where a 1 represents an infected cow and a 0 represents an uninfected cow after some number of nights.

OUTPUT FORMAT (pipe stdout):

Output a single integer: the minimum number of cows that could have started with the sickness.

SAMPLE INPUT:

5
11111

SAMPLE OUTPUT:

1
Suppose the middle cow was the only cow to start off infected. Then the cows would be infected in the following order:

After two or more nights, the final state of the cows would look like the input. There are many other initial states and number of nights that could have produced the input state, such as:

All of these initial states contain at least one infected cow.

SAMPLE INPUT:

6
011101

SAMPLE OUTPUT:

4
The only initial state and number of nights that could have led to this final state is if no nights have passed and each of the four infected cows in the input started off with the sickness.

SCORING:

Inputs 3-7: N≤1000
Inputs 8-12: No additional constraints.
Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has N total cows, each with a certain initial height and he wants to feed them M candy canes, each also of varying height (1≤N,M≤2⋅10⁵).

FJ plans to feed the candy canes one by one to the cows, in the order they are given in the input. To feed a candy cane to his cows, he will hang the candy cane so that initially the candy cane is just touching the ground. The cows will then line up one by one, in the order given by the input, and go up to the candy cane, each eating up to their height (since they cannot reach any higher). The candy cane stays suspended in place where it is initially set up and is not lowered to the ground, even after cows eat the bottom of the candy cane. It is possible a cow may eat nothing during her turn, if the base of the candy cane is already above that cow's height. After every cow has had their turn, the cows grow in height by how many units of candy cane they ate, and Farmer John hangs the next candy cane and the cows repeat the process again (with cow 1 again being the first to start eating the next candy cane).

INPUT FORMAT (pipe stdin):

The first line contains N and M.

The next line contains the initial heights of the N cows, each in the range [1,109].

The next line contains the heights of the M candy canes, each in the range [1,109].

OUTPUT FORMAT (pipe stdout):

The final heights of each of the N cows on separate lines.

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:

3 2
3 2 5
6 1

SAMPLE OUTPUT:
7
2
7

The first candy cane is 6 units tall.

The first cow eats the portion of the first candy cane up to height 3, after which the remaining portion of the first candy cane occupies heights [3,6].
The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights [5,6], is not eaten.
Next, each cow grows by the amount she ate, so the heights of the cows become [3+3,2+0,5+2]=[6,2,7].

The second candy cane is 1 unit tall, and the first cow eats all of it.

SCORING:

Inputs 2-10: N,M≤10³
Inputs 11-14: No additional constraints.
Problem credits: Agastya Goel

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

咨询一对一备赛规划

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤10⁵) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10⁵) commands, each one of L, F, or R:

L: Bessie moves one unit to the left.
R: Bessie moves one unit to the right.
F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.

If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

INPUT FORMAT (pipe stdin):

The first line contains T and C.

The next line contains the locations of the T targets, distinct integers in the range [−C,C].

The next line contains the command string of length C, containing only the characters F, L, and R.

OUTPUT FORMAT (pipe stdout):

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

SAMPLE INPUT:

3 7
0 -1 1
LFFRFRR

SAMPLE OUTPUT:

3

If you make no changes to the string, Bessie will hit two targets:

If you change the last command from R to F, Bessie will hit all three targets:

SAMPLE INPUT:

1 5
0
FFFFF

SAMPLE OUTPUT:

1

If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.

SAMPLE INPUT:

5 6
1 2 3 4 5
FFRFRF

SAMPLE OUTPUT:
3

SCORING:

Inputs 4-6: T,C≤1000
Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John has N barns (3≤N≤5⋅10⁵), of which K (3≤K≤N) distinct pairs of barns are connected.

First, Annabelle assigns each barn a distinct integer label in the range [1,N], and observes that the barns with labels a₁,…,a_K are connected in a cycle, in that order. That is, barns a_i and a_i+1 are connected for all 1≤i<K, and barns a_K and a₁ are also connected. All a_i are distinct.

Next, Bessie also assigns each barn a distinct integer label in the range [1,N] and observes that the barns with labels b₁,…,b_K are connected in a cycle, in that order. All b_i are distinct.

Some (possibly none or all) barns are assigned the same label by Annabelle and Bessie. Compute the maximum possible number of barns that are assigned the same label by Annabelle and Bessie.

INPUT FORMAT (pipe stdin):

The first line contains N and K.

The next line contains a1,…,a_K.

The next line contains b₁,…,b_K.

OUTPUT FORMAT (pipe stdout):

The maximum number of fixed points.

SAMPLE INPUT:

6 3
1 2 3
2 3 1

SAMPLE OUTPUT:

6

Annabelle and Bessie could have assigned the same label to every barn.

SAMPLE INPUT:

6 3
1 2 3
4 5 6

SAMPLE OUTPUT:

0

Annabelle and Bessie could not have assigned the same label to any barn.

SAMPLE INPUT:

6 4
1 2 3 4
4 3 2 5

SAMPLE OUTPUT:

4

Annabelle and Bessie could have assigned labels 2,3,4,6 to the same barns.

SCORING:

Inputs 4-5: N≤8
Inputs 6-8: N≤5000
Inputs 9-15: No additional constraints
Problem credits: Benjamin Qi

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

咨询一对一备赛规划

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have N (1≤N≤2⋅10⁵) distinct weights. In particular, for each i∈[1,N], a_i of his cows have a weight of w_i (1≤a_i≤10⁹,1≤w_i≤10⁹).

His most popular stunt involves the cows forming balanced towers. A tower is a sequence of cows where each cow is stacked on top of the next. A tower is balanced if every cow with a cow directly above it has weight at least K (1≤K≤10⁹) greater than the weight of the cow directly above it. Any cow can be part of at most one balanced tower.

If FJ wants to create at most M (1≤M≤10⁹) balanced towers of cows, at most how many cows can be part of some tower?

INPUT FORMAT (pipe stdin):

The first line contains three space-separated integers, N, M, and K.
The next N lines contain two space-separated integers, wi and ai. It is guaranteed that all wi are distinct.

OUTPUT FORMAT (pipe stdout):

Output the maximum number of cows in balanced towers if FJ helps the cows form towers optimally.

SAMPLE INPUT:

3 5 2
9 4
7 6
5 5

SAMPLE OUTPUT:

14
FJ can create four balanced towers with cows of weights 5, 7, and 9, and one balanced tower with cows of weights 5 and 7.

SAMPLE INPUT:

3 5 3
5 5
7 6
9 4

SAMPLE OUTPUT:
9

FJ can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow of weight 7. Alternatively, he can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow of weight 5.

SCORING:

In inputs 3-5, M≤5000 and the total number of cows does not exceed 5000.
In inputs 6-11, the total number of cows does not exceed 2⋅10⁵.
Inputs 12-17 have no additional constraints.
Problem credits: Eric Hsu

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

咨询一对一备赛规划

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10⁵) barns, located at integer points x₁,…,x_N (0≤x_i≤10⁶) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10⁶) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some a_i and b_i (1≤a_i,b_i≤106), a_i haybales are wasted per unit of distance left each shipment is transported, and b_i haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by

Given Q(1≤Q≤2⋅105) independent queries each consisting of possible values of (a_i ,b_i ), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.

INPUT FORMAT (pipe stdin):

The first line contains N.

The next line contains x1…xN.

The next line contains Q.

The next Q lines each contain two integers a_i and b_i.

OUTPUT FORMAT (pipe stdout):

Output Q lines, the i th line containing the answer for the ith query.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

11
13
18
30

For example, to answer the second query, it is optimal to select y=2
. Then the number of wasted haybales is equal to 2(2−1)+2(2−2)+1(3−2)+1(4−2)+1(10−2)=1+0+1+2+8=13.

SCORING:

Input 2: N,Q≤10
Input 3: N,Q≤500
Inputs 4-6: N,Q≤5000
Inputs 7-16: No additional constraints.
Problem credits: Benjamin Q_i

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

咨询一对一备赛规划

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10⁵) towns numbered from 1 to N and M (1≤M≤4⋅10⁵) one-way roads. The ith road runs from town a_i
to town b_i and has label li (1≤a_{i ,} b_i≤N, 1≤l_i≤109).

A trip of length k starting at town x₀ is a sequence of towns x₀,x₁,…,x_k, such that there is a road from town x_i to town x_i+1 for all 0≤i<k. It is guaranteed that there are no trips of infinite length in Cowland, and that no two roads connect the same pair of towns.

For each town, Bessie wants to know the longest possible trip starting at it. For some starting towns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.

INPUT FORMAT (pipe stdin):

The first line contains N and M.

The next M lines each contain three integers a_{i ,} b_i and l_i, denoting a road from a_i
to b_i with label l_i.

OUTPUT FORMAT (pipe stdout):

Output N lines. The ith should contain two space-separated integers, the length and sum of road labels of Bessie's preferred trip starting at town i.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 10
2 20

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 5
2 12

In the following explanation, we let represent the road from a_i to b_i with label l_i.

There are several trips starting from vertex 4, including and are the longest. These trips each have length 2, and their road label sequences are [4,5]
and [2,10], respectively. [2,10] is the lexicographically smaller sequence, and its sum is 12.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 5
2 7

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 5
1 10
2 7

SCORING:

Inputs 5-6: All labels are the same.
Inputs 7-8: All labels are distinct.
Inputs 9-10: N,M≤5000
Inputs 11-20: No additional constraints.
Problem credits: Claire Zhang and Spencer Compton

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

咨询一对一备赛规划