作者： chenchen

2024 年美国公开赛的比赛以算法编程问题为特色，涵盖了广泛的技术和难度级别。

共有4280名参与者提交了至少一个解决方案。其中2270人来自美国，中国、加拿大、韩国、巴基斯坦、印度、新加坡、台湾、英国、罗马尼亚、香港、德国、埃及和越南的代表性也很高。

总共有 8416 份评分提交，按语言细分如下：

5065 C++17
1247 Python-3.6.9
1114 Java
949 C++11
33 C
8 Python-2.7.17

以下是每场白金、黄金、白银和铜牌比赛的详细结果。 您还可以找到每个问题的解决方案和测试数据，然后单击任何 问题 您可以在“分析模式”下练习重新提交解决方案。

USACO 2024 年 美国公开赛，白金奖

白金组共有461名参与者，其中339名是大学预科生。得分最高的成员的结果在这里。恭喜所有优秀参赛者取得优异成绩！

1 Identity Theft
查看问题 | 测试数据 | 解决方案
2 Splitting Haybales
查看问题 | 测试数据 | 解决方案
3 Activating Robots
查看问题 | 测试数据 | 解决方案

USACO 2024 年美国公开赛，金牌

黄金组共有668名参赛者，其中453名是大学预科生。所有在本次比赛中获得 700 分或以上的参赛者将自动晋升为白金组。所有晋升者的详细结果都在这里。

1 Cowreography
查看问题 | 测试数据 | 解决方案
2 Grass Segments
查看问题 | 测试数据 | 解决方案
3 Smaller Averages
查看问题 | 测试数据 | 解决方案

USACO 2024 年美国公开赛，银牌

银牌组共有2661名参赛者，其中2081名是大学预科生。所有在本次比赛中得分为650分或以上的参赛者将自动晋升为黄金组。

1 Bessie's Interview
查看问题 | 测试数据 | 解决方案
2 Painting Fence Posts
查看问题 | 测试数据 | 解决方案
3 The 'Winning' Gene
查看问题 | 测试数据 | 解决方案

USACO 2024 年美国公开赛，铜牌

铜牌组共有3025名参赛者，其中2360名是大学预科生。所有在本次比赛中获得 650 分或以上的参赛者将自动晋升为银牌组。

1 Logical Moos
查看问题 | 测试数据 | 解决方案
2 Walking Along a Fence
查看问题 | 测试数据 | 解决方案
3 Farmer John's Favorite Permutation
查看问题 | 测试数据 | 解决方案

结语

2023-24赛季常规赛赛季已经结束！——感谢所有参赛者，尤其是本赛季每一场比赛的参赛者。

从技术角度来看，美国公开赛进行得相当顺利。比赛中的问题确实相当具有挑战性，导致了相当大的晋升缺口。我们意识到，近年来，我们的比赛难度有所上升；这将是我们在即将到来的训练营中与教练讨论的一个话题，以确保我们的低级别比赛对新手学生来说仍然平易近人。对于那些尚未晋升的人，请记住，你练习得越多，你的算法编码技能就会变得越好——请坚持下去！USACO竞赛旨在挑战即使是最优秀的学生，也需要付出大量的努力才能脱颖而出。为了帮助您修复代码中的任何错误，您现在可以重新提交解决方案，并使用“分析模式”从判断服务器获得反馈。

在整个赛季中，我们在解决问题和编码方面看到了惊人的结果，但我并不高兴看到的事情也出现了惊人的增长：（通常是明目张胆的）学术不诚实案件、对我们基础设施的攻击，以及骚扰竞争对手和USACO员工的事件。USACO工作人员的大量时间都被这些问题所消耗——我更希望这些时间用于我们的学术倡议。我恳请我们社区的每一个人共同努力，在这方面促进更高标准的适当行为。随着我们白金“认证”比赛的趋势，我们可能会在未来几季采取进一步的、可能更具戏剧性的措施来重组我们的比赛，以确保比赛的完整性。接下来还有更多的事情要做。

大量的人为USACO比赛的质量和成功做出了贡献。参与本次比赛的有马崇天、齐、齐、维贾拉姆、苏哈斯·纳加尔、屈、丹尼·米塔尔、梁、阿南德·约翰、斯潘塞·康普顿、顾、张、王、王、钱纪超和陈明辉。也感谢我们的翻译在整个赛季的帮助，帮助扩大我们比赛的范围。最后，我们非常感谢USACO赞助商的慷慨支持：Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech和Jump Trading。

我们期待着在2024年美国公开赛上再次见到大家，这是我们本赛季的最后一场比赛。

编码快乐！

-Brian Dean(bcdean@clemson.edu)
克莱姆森大学计算机学院教授兼院长
计算机学院教授兼主任 USACO 主任

Farmer John has a permutation p of length N (2≤N≤10⁵), containing each positive integer from 1 to N exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled p. To not be too cruel, FN has written some hints that will help FJ reconstruct p. While there is more than one element remaining in p
, FN does the following:

Let the remaining elements of p be p′₁,p′₂,…,p′_n,

If p′₁>p′_n , he writes down p′₂ and removes p′₁ from the permutation.
Otherwise, he writes down p′_n−1 and removes p′_n from the permutation.

At the end, Farmer Nhoj will have written down N−1 integers h₁,h₂,…,h_N−1, in that order. Given h, Farmer John wants to enlist your help to reconstruct the lexicographically minimum p consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations p and p′, p is lexicographically smaller than p′ if p_i<p′_i at the first position i where the two differ.

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

Each input consists of T independent test cases (1≤T≤10). Each test case is described as follows:

The first line contains N.

The second line contains N−1 integers h₁,h₂,…,h_N−1 (1≤h_i≤N).

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

Output T lines, one for each test case.

If there is a permutation p of 1…N consistent with h, output the lexicographically smallest such p. If no such p exists, output −1.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

For the fourth test case, if p=[3,1,2,4] then FN will have written down h=[2,1,1].

p' = [3,1,2,4]
p_1' < p_n' -> h_1 = 2
p' = [3,1,2]
p_1' > p_n' -> h_2 = 1
p' = [1,2]
p_1' < p_n' -> h_3 = 1
p' = [1]

Note that the permutation p=[4,2,1,3] would also produce the same h, but [3,1,2,4] is lexiocgraphically smaller.

For the second test case, there is no p consistent with h; both p=[1,2] and p=[2,1] would produce h=[1], not h=[2].

SCORING:

Input 2: N≤8
Inputs 3-6: N≤100
Inputs 7-11: No additional constraints.

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

Farmer John's N cows (1≤N≤10⁵) each like to take a daily walk around the fence enclosing his pasture.

The fence consists of P posts (4≤P≤2⋅10⁵, P even), the location of each being a different 2D point (x,y) on a map of FJ's farm (0≤x,y≤1000). Each post is connected to the two adjacent posts by fences that are either vertical or horizontal line segments, so the entire fence can be considered a polygon whose sides are parallel to the x or y axes (the last post connects back to the first post, ensuring the fence forms a closed loop that encloses the pasture). The fence polygon is "well-behaved" in that fence segments only potentially overlap at their endpoints, each post aligns with exactly two fence segment endpoints, and every two fence segments that meet at an endpoint are perpendicular.

Each cow has a preferred starting and ending position for her daily walk, each being points somewhere along the fence (possibly at posts, possibly not). Each cow walks along the fence for her daily walks, starting from her starting position and ending at her ending position. There are two routes that the cow could take, given that the fence forms a closed loop. Since cows are somewhat lazy creatures, each cow will walk in the direction around the fence that is shorter (if there is a tie, the cow may choose either direction).

Determine the distance that each cow walks.

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

The first line of input contains N and P. Each of the next P lines contains two integers representing the positions of the fence posts in clockwise or counterclockwise order. Each of the next N lines contains four integers  x₁y₁x₂y₂ representing the starting position (x₁,y₁) and ending position (x₂,y₂) of a cow.

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

Write N integers as output, giving the distance that each cow walks.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

2
3
3
4
4

The first cow can walk directly from (0,0) to (0,2).

The second cow can walk from (0,2) to (0,0) and then to (1,0).

The fourth cow has two possible routes with equal lengths: (1,0)→(0,0)→(0,2)→(1,2) and (1,0)→(2,0)→(2,2)→(1,2).

SCORING:

Inputs 2-6: 0≤x,y≤100 and N≤100
Inputs 7-11: No additional constraints.

Problem credits: Brian Dean

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

咨询一对一备赛规划

Farmer John has a boolean statement that is N keywords long (1≤N<2⋅10⁵, N odd). Only true or false appear in odd positions, while only and and or appear in even positions.

A phrase of the form x OPERATOR y, where x and y are either true or false, and OPERATOR is and or or, evaluates as follows:

x and y: This evaluates to true if both x and y are true, and false otherwise.
x or y: This evaluates to true if either x or y is true, and false otherwise.

When evaluating the statement, FJ has to take the order of precedence in Moo Language into account. Similar to C++, and takes priority over or. More specifically, to evaluate the statement, repeat the following step until the statement consists of only one keyword.

1.If the statement contains an and, choose any of them and replace the phrase surrounding it with its evaluation.
2.Otherwise, the statement contains an or. Choose any of them and replace the phrase surrounding it with its evaluation.

It may be proven that if multiple phrases can be evaluated during a given step, it does not matter which one is chosen; the statement will always evaluate to the same value.

FJ has Q (1≤Q≤2⋅10⁵ ) queries. In each query, he gives you two integers l and r (1≤l≤r≤N, l and r are both odd), and deletes the segment from keyword l to keyword r inclusive. In turn, he wishes to replace the segment he just deleted with just one simple true or false so that the whole statement evaluates to a certain boolean value. Help FJ determine if it's possible!

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

The first line contains N and Q.

The next line contains N strings, a valid boolean statement.

The following Q lines contain two integers l and r, and a string true or false, denoting whether he wants the whole statement to evaluate to true or false.

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

Output a string of length Q, where the i'th character is Y if the i'th query is possible, otherwise N.

SAMPLE INPUT:

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

SAMPLE OUTPUT:

NYYYNYY

Let's analyze the first query:

If we were to replace delete the segment [1,1] and replace it with true, then the whole statement becomes:

true and true or true

We evaluate the and keyword from at position 2 and obtain

true or true

Since we have no and keywords left, we have to evaluate the or keyword. After evaluation, all that is left is

true

It can be shown that if we were to replace the segment with false, the statement will still evaluate to true, so we output N since the statement cannot possibly evaluate to false.

For the second query, we can replace the segment [1,3] with true and the whole statement will evaluate to true, so we output Y.

For the third query, since [1,5] is the whole statement, we can replace it with anything, so we output Y.

SAMPLE INPUT:

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

SAMPLE OUTPUT:

YNYY

SCORING:

Inputs 3-5: N,Q≤10²
Inputs 6-8: N,Q≤10³
Inputs 9-26: No additional constraints.

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

After years of hosting games and watching Bessie get first place over and over, Farmer John has realized that this can't be accidental. Instead, he concludes that Bessie must have winning coded into her DNA so he sets out to find this "winning" gene.

He devises a process to identify possible candidates for this "winning" gene. He takes Bessie's genome, which is a string S of length N where 1≤N≤3000. He picks some pair (K,L) where 1≤L≤K≤N representing that the "winning" gene candidates will have length L and will be found within a larger K length substring. To identify the gene, he takes all K length substrings from S
which we will call a k-mer. For a given k-mer, he takes all length L substrings, identifies the lexicographically minimal substring as a winning gene candidate (choosing the leftmost such substring if there is a tie), and then writes down the 0 -indexed position p_i where that substring starts in S to a set P.

Since he hasn't picked K and L yet, he wants to know how many candidates there will be for every pair of (K,L).

For each v in 1…N, help him determine the number of (K,L) pairs with |P|=v.

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

N representing the length of the string. S representing the given string. All characters are guaranteed to be uppercase characters where si∈A−Z since bovine genetics are far more advanced than ours.

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

For each v in 1…N, output the number of (K,L) pairs with |P|=v, with each number on a separate line.

SAMPLE INPUT:

8
AGTCAACG

SAMPLE OUTPUT:

11
10
5
4
2
2
1
1

In this test case, the third line of the output is 5 because we see that there are exactly 5 pairs of K and L that allow for three "winning" gene candidates. These candidates are (where p_i is 0-indexed):

(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]

To see how (4,2) leads to these results, we take all 4-mers

AGTC
GTCA
TCAA
CAAC
AACG

For each 4-mer, we identify the lexicographically minimal length 2 substring

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

We take the positions of all these substrings in the original string and add them to a set P to get P=[0,3,4].

On the other hand, if we focus on the pair (4,1), we see that this only leads to 2 total "winning" gene candidates. If we take all 4-mers and identify the lexicographically minimum length 1 substring (using A and A' and A* to distinguish the different As), we get

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

While both A' and A* are lexicographically minimal in the last 3 cases, the leftmost substring takes precedence so A' is counted as the only candidate in all of these cases. This means that P=[0,4].

SCORING:

Inputs 2-4: N≤100
Inputs 5-7: N≤500
Inputs 8-16: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

**Note: The time limit and memory limit for this problem are 3s and 512MB, which are 1.5x and 2x the normal amount, respectively.**

Farmer John's N cows (1≤N≤10⁵) each like to take a daily walk around the fence enclosing his pasture. Unfortunately, whenever a cow walks past a fence post, she brushes up against it, requiring Farmer John to need to repaint the fence posts regularly.

The fence consists of P posts (4≤P≤2⋅10⁵, P even), the location of each being a different 2D point (x,y) on a map of FJ's farm (0≤x,y≤10⁹). Each post is connected to the two adjacent posts by fences that are either vertical or horizontal line segments, so the entire fence can be considered a polygon whose sides are parallel to the x or y axes (the last post connects back to the first post, ensuring the fence forms a closed loop that encloses the pasture). The fence polygon is "well-behaved" in that fence segments only potentially overlap at their endpoints, each post aligns with exactly two fence segment endpoints, and every two fence segments that meet at an endpoint are perpendicular.

Each cow has a preferred starting and ending position for her daily walk, each being points somewhere along the fence (possibly at posts, possibly not). Each cow walks along the fence for her daily walks, starting from her starting position and ending at her ending position. There are two routes that the cow could take, given that the fence forms a closed loop. Since cows are somewhat lazy creatures, each cow will walk in the direction around the fence that is shorter. Remarkably, this choice is always clear -- there are no ties!

A cow touches a fence post if she walks past it, or if the fence post is the starting or ending point of her walk. Please help FJ calculate the number of daily touches experienced by each fence post, so he knows which post to repaint next.

It can be shown that there is exactly one possibility for the fences given the locations of all of the posts.

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

The first line of input contains N and P. Each of the next P lines contains two integers representing the positions of the fence posts in no particular order. Each of the next N lines contains four integers x₁ y₁ x₂ y₂ representing the starting position (x₁,y₁) and ending position (x₂,y₂)of a cow.

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

Write P integers as output, giving the number of touches experienced by each fence post.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
2
2
1

The following posts are connected by fence segments:

(3,1)↔(3,5)↔(1,5)↔(1,1)↔(3,1)

The posts touched by each cow are as follows:

1.Posts 2 and 4.
2.Posts 2 and 3.
3.Posts 1 and 3.
4.No posts.
5.No posts.

SAMPLE INPUT:

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

SAMPLE OUTPUT:

1
0
0
0
1
1
1
2

SAMPLE INPUT:

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

SAMPLE OUTPUT:

1
1
1
1
1
0
0
0
0
0
0
0

SCORING:

Inputs 4-6: N,P≤1000
Inputs 7-9: All locations satisfy 0≤x,y≤1000.
Inputs 10-15: No additional constraints.
Problem credits: Brian Dean

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

咨询一对一备赛规划

Bessie is looking for a new job! Fortunately, K farmers are currently hiring and conducting interviews. Since jobs are highly competitive, the farmers have decided to number and interview cows in the order they applied. There are N cows that applied before Bessie, so her number is N+1(1≤K≤N≤3⋅10⁵).

The interview process will go as follows. At time 0, farmer i will start interviewing cow i for each 1≤i≤K. Once a farmer finishes an interview, he will immediately begin interviewing the next cow in line. If multiple farmers finish at the same time, the next cow may choose to be interviewed by any of the available farmers, according to her preference.

For each 1≤i≤N, Bessie already knows that cow i's interview will take exactly t_i minutes (1≤t_i ≤10⁹). However, she doesn't know each cow's preference of farmers.

Since this job is very important to Bessie, she wants to carefully prepare for her interview. To do this, she needs to know when she will be interviewed and which farmers could potentially interview her. Help her find this information!

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

The first line of the input will contain two integers N and K.

The second line will contain Nintegers t₁…t_N.

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

On the first line, print the time Bessie's interview will begin.

On the second line, a bit string of length K, where the i-th bit is 1if farmer i could interview Bessie and 0 otherwise.

SAMPLE INPUT:

6 3
3 1 4159 2 6 5

SAMPLE OUTPUT:

8
110

There are 6 cows aside from Bessie and 3 farmers, and the interview process will go as follows:

1.At time t=0, farmer 1 interviews cow 1, farmer 2 interviews cow 2, and farmer 3 interviews cow 3.
2.At time t=1, farmer 2 finishes his interview with cow 2 and starts interviewing cow 4.
3.At time t=3, both farmer 1 and farmer 2 finish their interviews, and there are two possibilities:
Farmer 1 interviews cow 5 and farmer 2 interviews cow 6. In this case, farmer      2 would finish his interview at time t=8 and start interviewing Bessie.
Farmer 1 interviews cow 6 and farmer 2 interviews cow 5. In this case, farmer      1 would finish his interview at time t=8 and start interviewing Bessie.

Thus, Bessie's interview will begin at time t=8, and she could be interviewed by either farmer 1 or farmer 2.

SCORING:

Inputs 2-3: No two farmers finish at the same time.
Inputs 4-9: N≤3⋅10³ 
Inputs 10-21: No additional constraints.

Problem credits: Avnith Vijayram

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

咨询一对一备赛规划

Bessie has two arrays of length N(1≤N≤500). The i-th element of the first array is a_i (1≤a_i≤10⁶) and the i-th element of the second array is b_i (1≤b_i≤10⁶).

Bessie wants to split both arrays into non-empty subarrays such that the following is true.

1.Every element belongs in exactly 1 subarray.
2.Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be k (i.e. the first array is split into exactly k subarrays and the second array is split into exactly k subarrays).
3.For all 1≤i≤k, the average of the i-th subarray on the left of the first array is less than or equal to the average of the i-th subarray on the left of the second array.

Count how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo 109+7. Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.

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

The first line contains N.

The next line contains a_l,a₂,...,a_N.

The next line contains b₁,b₂,...,b_N.

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

Output the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo 10⁹+7.

SAMPLE INPUT:

2
1 2
2 2

SAMPLE OUTPUT:

2

The two valid ways are:

1.Split the first array into [1],[2] and the second array into [2],[2].
2.Split the first array into [1,2] and the second array into [2,2].

SAMPLE INPUT:

3
1 3 2
2 2 2

SAMPLE OUTPUT:

3

The three valid ways are:

1.Split the first array into [1,3],[2] and the second array into [2,2],[2].
2.Split the first array into [1,3],[2] and the second array into [2],[2,2].
3.Split the first array into [1,3,2] and the second array into [2,2,2].

SAMPLE INPUT:

5
2 5 1 3 2
2 1 5 2 2

SAMPLE OUTPUT:

1

The only valid way is to split the first array into [2],[5,1,3],[2] and the second array into [2],[1,5],[2,2].

SAMPLE INPUT:

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

SAMPLE OUTPUT:

140

SCORING:

Inputs 5-6: N≤10
Inputs 7-9: N≤80
Inputs 10-17: N≤300
Inputs 18-20: N≤500

Problem credits: Alex Liang

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

咨询一对一备赛规划