作者： chenchen

Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has N (1≤N≤10⁵) bottles that he is trying to fill. Each bottle initially contains some amount of milk mi (0≤m_i≤10⁹). Every day, he takes A (1≤A≤N)
bottles and fills each bottle with one unit of milk.

Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo Milk, knows about Farmer John's production processes and has a plan to curtail his business. Every day, after Farmer John fills his A bottles, Farmer Nhoj will sneakily steal one unit of milk from each of B (0≤B<A) different nonempty bottles. To remain sneaky, Farmer Nhoj chooses B so that it is strictly less than A, so that it is less likely for Farmer John to discover him.

After D(1≤D≤10⁹) days, Farmer John will sell his OohMoo Milk. If a bottle has M
units of milk, it will sell for M² moonies.

Let P be the unique profit such that FJ can guarantee that he makes at least P profit regardless of how FN behaves, and FN can guarantee that FJ makes at most P profit regardless of how FJ behaves. Output the value of P modulo 10⁹+7.

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

The first line of the input contains N and D, where N is the number of bottles and D is the number of days that take place.

The second line of the input contains A and B representing the number of units of milk that Farmer John fills and Farmer Nhoj steals respectively.

The third line of the input contains N space-separated integers m_i representing the initial amount of milk in each bottle.

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

Output the value of P modulo 10⁹+7.

SAMPLE INPUT:

5 4
4 2
4 10 8 10 10

SAMPLE OUTPUT:

546

On the first day, Farmer John could add milk to the second, third, fourth, and fifth bottles. Then, Farmer Nhoj could remove milk from the second and fourth bottles.

Thus, the new amount of milk in each bottle is

[4,10,8,10,10]→[4,11,9,11,11]→[4,10,9,10,11].

After four days, the amount of milk in each bottle could be

[4,10,8,10,10]→[4,10,9,10,11]→[4,10,10,11,11]→[4,11,11,11,11]→[4,11,11,12,12].

The total amount of moonies Farmer John would make in this situation is 4²+11²+11²+12²+12²=546. It can be shown that this is the value of P.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

777

SAMPLE INPUT:

5 1000000000
3 1
0 1 2 3 4

SAMPLE OUTPUT:

10

Make sure you output P modulo 10⁹+7.

SCORING:

Inputs 4-6: N,D≤1000.
Inputs 7-10: D≤10⁶.
Inputs 11-20: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

**Note: The time limit for this problem is 3s, 1.5x the default.**

Farmer John has N(2≤N≤2⋅10⁵) cows numbered from 1 to N. An election is being held in FJ's farm to determine the two new head cows in his farm. Initially, it is known that cow i will vote for cow a_i  (1≤a_i ≤N).

To determine the two head cows, FJ will hold his election in the following process:

Choose an arbitrary subset S of his cows that contains at least one cow but not all cows. FJ is able to choose cow x as the first head cow if its votes appear most frequently among all votes cast by cows in S.
FJ is able to choose cow y as the second head cow if its votes appear most frequently among votes cast by cows not in S.
For a fixed subset S, FJ denotes the diversity between his head cows as |x−y|. As FJ does not like having leaders with similar numbers, he wants to choose S
such that the diversity is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is 0.

However, some cows keep changing their minds, and FJ may have to rerun the election many times! Therefore, he asks you Q (1≤Q≤10⁵) queries. In each query, a cow changes their vote. After each query, he asks you for the maximum possible diversity among his new head cows.

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

The first line contains N and Q.

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

The following Q lines contain two integers i and x, representing the update a_i=x
(1≤i,x≤N).

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

Output Q lines, the i'th of which is the maximum possible diversity after the first i
queries.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
3
2

After the first query, a=[1,2,4,4,5]. At the first step of the election, FJ can make S={1,3}. Here, cow 1 receives one vote and cow 4 receives one vote. Therefore, FJ can choose either cow 1 or cow 4 as its first head cow.

For all cows not in the election, cow 2 receives one vote, cow 4 receives one vote, and cow 5 also receives one vote. Therefore, FJ can choose any one of cows 2, 4,or 5 to be its second head cow.

To obtain the maximum diversity, FJ can choose cow 1 as the first head cow and cow 5 as the second head cow. Therefore, the diversity is |1−5|=4.

After the second query, a=[2,2,4,4,5] and FJ can make S={4,5}. Then, he can choose 5 as the first head cow and cow 2 as the second head cow. The maximum possible diversity is |5−2|=3.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
4
4
7
7

SCORING:

Inputs 3-4: N,Q≤100
Inputs 5-7: N,Q≤3000
Inputs 8-15: No additional constraints.
Problem credits: Chongtian Ma and Haokai Ma

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

咨询一对一备赛规划

You have a long string S of Ms and Os and an integer K≥1. Count the number of ways of ways to decompose S into subsequences such that each subsequence is MOOOO....O with exactly K Os, modulo 10⁹+7.

Since the string is very long, you are not given it explicitly. Instead, you are given an integer L (1≤L≤10¹⁸), and a string T of length N (1≤N≤10⁶). The string S is the concatenation of L copies of the string T.

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

The first line contains K, N, and L.
The second line contains the string T of length N. Every character is either an M or an O.

It is guaranteed that the number of decompositions of S is nonzero.

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

Output the number of decompositions of string S, modulo 10⁹+7.

SAMPLE INPUT:

2 6 1
MOOMOO

SAMPLE OUTPUT:

1

The only way to decompose S into MOOs is to let the first three characters form a MOO and the last three characters form another MOO.

SAMPLE INPUT:

2 6 1
MMOOOO

SAMPLE OUTPUT:

6

There are six distinct ways to decompose the string into subsequences (uppercase letters form one MOO, lowercase letters form another):

MmOOoo
MmOoOo
MmOooO
MmoOOo
MmoOoO
MmooOO

SAMPLE INPUT:

1 4 2
MMOO

SAMPLE OUTPUT:

4

SAMPLE INPUT:

1 4 100
MMOO

SAMPLE OUTPUT:

976371285

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

SCORING:

Inputs 5-7: K=1, L=1
Inputs 8-10: K=2, N≤1000, L=1
Inputs 11-13: K=1
Inputs 14-19: L=1
Inputs 20-25: No additional constraints.

Problem credits: Dhruv Rohatgi

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

咨询一对一备赛规划

**Note: The time limit for this problem is 4s, 2x the default.**

Farmer John has distributed cows and packages in a weird pattern across the number line using the following process:

Farmer John chooses a number M (1≤M≤10¹⁸).
Farmer John chooses N (1≤N≤2⋅10⁴) intervals [ L_i,R_i] to distribute cows in (1≤L_i≤R_i≤10¹⁸). He then places cows at locations L_i,L_i+M,L_i+2M,…,R_i. It is guaranteed that R_i−L_i is a multiple of M.
Farmer John chooses P (1≤P≤2⋅10⁴) intervals [A_i,B_i] to distribute packages in (1≤A_i≤B_i≤10¹⁸). He then places packages at locations A_i ,A_i +M,A_i +2M,…,B_i
. It is guaranteed that B_i−A_i is a multiple of M.

Once the cows and packages are distributed, Farmer John wants to see how long it takes the cows to pick up the packages. Every second, Farmer John can issue a command to a single cow to move one unit left or right of their current position with his handy walkie talkie. If a cow travels to the position where a package is located, they are able to pick it up. Farmer John wants to know the minimum time in seconds that it would take the cows to pick up every package.

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

The first line contains M, N, and P.

The next N lines each contain two integers L_i and R_i.

The next P lines each contain two integers A_i and B_i.

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

Output a single integer, representing the minimum amount of time it can take the cows to pick up all the packages, given that every second, he can issue a single left/right command to a single cow.

SAMPLE INPUT:

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

SAMPLE OUTPUT:

22

In the above test case, suppose the cows and packages are numbered from left to right. Farmer John can follow this procedure to pick up the packages in 22 seconds:

Issue 3 lefts to cow 1 so that it picks up package 1
Issue 3 rights to cow 3 so that it picks up package 7
Issue 4 rights to cow 2 so that it picks up package 5
Issue 10 rights to cow 1 so that it picks up packages 2, 3, and 4
Issue 2 rights to cow 2 so that it picks up package 6

SAMPLE INPUT:

2 1 1
1 5
2 6

SAMPLE OUTPUT:

3

There are three cows and three packages. Farmer John can issue one right to each cow.

SCORING:

Input 3-4: It is guaranteed that the total number of cows and packages does not exceed 2⋅10⁵ 
Inputs 5-10: It is guaranteed that N,P≤500.
Inputs 11-13: It is guaranteed that no intervals of packages or cows intersect.
Inputs 14-20: No additional constraints.

Problem credits: Suhas Nagar and Benjamin Q_i

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

咨询一对一备赛规划

Farmer John has N cows (2≤N≤5⋅10⁶) and is attempting to get them to sort a non-negative integer array A of length N by relying on their laziness. He has a lot of heavy boxes so he lines the cows up one behind another, where cow i+1 is behind cow i, and gives a_i boxes to cow i (0≤a_i).

Cows are inherently lazy so they always look to pass their work off to someone else. From cow 1 to N−1 in order, each cow looks to the cow behind them. If cow i
has strictly more boxes than cow i+1, cow i thinks this is "unfair" and gives one of its boxes to cow i+1. This process repeats until every cow is satisfied.

Farmer John will then note the number of boxes b_i that each cow i is holding and create an array B out of these values. If B=sorted(A), then Farmer John will be happy. Unfortunately, Farmer John forgot all but Q values (2≤Q≤min(N,100)) in A. Luckily, those values include the number of boxes he was going to give to the first and last cow. Each value that FJ remembers is given in the form c_i v_i representing that a c_i=vi(1≤c_i≤N, 1≤v_i ≤10⁹). Determine the number of different ways the missing values can be filled in so that he will be happy mod 10⁹+7.

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

The first line contains two space-separated integers N and Q representing the number of cows and queries respectively.

The next Q lines contain two space separated integers c_i v_i representing that cow c_i initially holds v_i  boxes. It is guaranteed that c₁=1, c_Q=N, and c_i<c_i+1
(the order of the cows is strictly increasing).

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

Print the number of different ways modulo 10⁹+7 that values a_i can be assigned such that Farmer John will be happy after the cows perform the lazy sort. It is guaranteed that there will be at least one valid assignment.

SAMPLE INPUT:

3 2
1 3
3 2

SAMPLE OUTPUT:

2

In this example, FJ remembers the values at the ends of the array. The arrays [3,2,2] and [3,3,2] are the valid arrays that will make FJ happy at the end of the lazy sorting.

SAMPLE INPUT:

6 3
1 1
3 3
6 5

SAMPLE OUTPUT:

89

SCORING:

Inputs 3-4: N,v_i≤100
Inputs 5-6: N≤100 and v_i≤10⁶
Inputs 7-9: N≤2⋅10⁵ and v_i≤10⁶
Inputs 10-12: N≤2⋅10⁵
Inputs 13-15: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

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

在 5782 天的比赛中，共有 4 名不同的用户登录了比赛。共有 4024 名参与者提交了至少一个解决方案，来自 100+ 个不同的国家/地区。2349 名参与者来自美国，其中来自中国、加拿大、韩国、罗马尼亚、印度和新加坡的参与人数也很高。

总共有 10638 篇评分的提交，按语言细分如下：

6698 C++17

1701 Python-3.6.9

1315 Java

866 C++11

41 C

17 Python-2.7.17

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

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

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

1 Forklift Certified
查看问题 | 测试数据 | 解决方案
2 Lazy Sort
查看问题 | 测试数据 | 解决方案
3 Package Pickup
查看问题 | 测试数据 | 解决方案

USACO 2025 年美国公开赛，金牌

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

1 Moo Decomposition
查看问题 | 测试数据 | 解决方案
2 Election Queries
查看问题 | 测试数据 | 解决方案
3 OohMoo Milk
查看问题 | 测试数据 | 解决方案

USACO 2025 年美国公开赛，银牌

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

1 Sequence Construction
查看问题 | 测试数据 | 解决方案
2 Compatible Pairs
查看问题 | 测试数据 | 解决方案
3 Ski Slope
查看问题 | 测试数据 | 解决方案

USACO 2025 年美国公开赛，铜牌

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

1 Hoof Paper Scissors Minus One
查看问题 | 测试数据 | 解决方案
2 More Cow Photos
查看问题 | 测试数据 | 解决方案
3 It's Mooin' Time III
查看问题 | 测试数据 | 解决方案

结语

2024-2025 赛季现已结束。我很高兴看到，尽管问题重重，但本赛季的所有比赛都进行得很顺利，并带来了大量的晋升。祝贺所有参与其中的人，他们的编码和解决问题的能力在整个赛季都有所提高。

对于那些尚未晋升的人，请记住，你练习得越多，你的算法编码技能就会越好——请坚持下去！USACO竞赛旨在挑战最优秀的学生，要想在他们职中脱颖而出，可能需要付出大量的努力。为了帮助您修复代码中的任何错误，您现在可以使用“分析模式”重新提交解决方案并从评判服务器获得反馈。

大量的人为USACO竞赛的质量和成功做出了贡献。本次竞赛的协助人员包括Suhas Nagar, Nathan Wang, Nick Wu, William Lin, Chongtian Ma, Alex Liang, Aakash Gokhale, Weiming Zhou, Ho Tin Fan, Michelle Wei, Jichao Qian, Brandon Wang, Dhruv Rohatgi, Thomas Liu, Haokai Ma, Larry Xing, Eric Yang, Austin Geng, Andi Qu, Benjamin Chen, Anand John, and Benjamin Qi。 也感谢我们的翻译帮助我们扩大比赛的范围。最后，我们非常感谢USACO赞助商的慷慨支持：Citadel， 它已成为我们营地和IOI/EGOI团队的独家赞助商，以及Jump Trading，它帮助赞助我们的在线比赛。

祝我们在 2025 年 IOI 和 EGOI 上好运，我们期待着 在 2025-2026 赛季再次见到大家！

祝您编码愉快！

Farmer John is training to become forklift certified! As part of his training, he needs to clear N(1≤N≤10⁵) boxes, conveniently labeled 1 through N, from an old warehouse.

The boxes can be modeled as axis-aligned rectangles in a 2-dimensional plane, where the +x-direction is east and the +y-direction is north. Box i has its southwest corner at (x_i1,y_i1) and its northeast corner at (x_i2,y_i2). All coordinates are integers in the range [1,2N], and no two corners from two different rectangles share the same x or y coordinate. All boxes have a non-zero area, and no two boxes intersect.

Farmer John plans to remove the boxes one at a time out of the southwest entrance of the warehouse. However, he can only remove a box if no part of any other box lies both south and west of the box's northeast corner due to physical limitations of the forklift.

An example with N=4 is shown below. To remove box 4, there cannot be any other boxes in the shaded region. Boxes 2 and 3 prevent box 4 from being removed, but box 1 does not.

Help Farmer John decide how to remove all the boxes! Your code should operate in two separate modes, defined by an integer flag M:

Mode 1 (M=1): Generate a permutation of 1,…,N specifying a valid box removal order. If there are multiple valid orders, find any. It can be proven that such an order always exists.
Mode 2 (M=2): For each k=1,…,N, output 1 if Farmer John can remove box k if boxes 1,…,k−1 have already been removed, and 0 otherwise.

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 each input does not exceed 5⋅10⁵.

The first line of input contains T and M. (Note that M is the same for each test case.) Each test case is then formatted as follows:

The first line contains a single integer N.

Each of the next N lines contains four space-separated integers x_i1,y_i1, x_i2,y_i2 the locations of the southwest and northeast corners of box i.

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

For each test case:

If M=1, output a single line with N space-separated integers, where the j-th integer is the label of the j-th box to remove.

If M=2, output a single line with a binary string of N characters specifying the answer for each k=1,…,N.

SAMPLE INPUT:

2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

SAMPLE OUTPUT:

1 3 2 4
2 3 1

The first test case corresponds to the N=4 exammple above. Box 1 is not blocked by anything, box 3 is blocked by box 1, box 2 is blocked by box 3, and box 4 is blocked by boxes 2 and 3.

SAMPLE INPUT:

2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

SAMPLE OUTPUT:

1011
011

For the first test case, box 2 is blocked by box 3, so Farmer John cannot remove it before removing box 3.

SCORING:

Inputs 3-5: M=1, N≤1000.
Input 6: M=2, N≤1000.
Inputs 7-13: M=1, no additional constraints.
Inputs 14-16: M=2, no additional constraints.

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

咨询一对一备赛规划