作者： chenchen

USACO 2026赛季的第一场比赛涵盖了涵盖多种技术和难度的算法编程问题。

在为期4天的比赛期间，共有14273名不同用户登录了该比赛。共有11896名参与者提交了至少一个解决方案，来自100+个不同国家。5147名参与者来自美国，中国、加拿大、韩国、印度、马来西亚和新加坡的参与度较高。

总共有34135份评分提交，按语言分类如下：

21839 C++17
5485 Python-3.6.9
3375 C++11
3163 Java
201 C
72 Python-2.7.17

顺便说一句，我们正在努力增加对PyPy的支持，以帮助Python选手在计算要求更高的问题上获得更高分数。

以下是白金、金、银和铜三项比赛的详细成绩。 你还可以找到每个问题的解决方案和测试数据。

USACO 2026 年 首场比赛，白金认证

白金组共有191名参赛者，其中143名为大学预科生。本次白金竞赛颇具特殊性，由于大部分选手从黄金组起步，仅有少数选手以白金组身份参赛（本次竞赛中仅2025年国际信息学奥林匹克竞赛（IOI）决赛选手及在2025赛季表现相近的往届决赛选手具备此资格）。因此，自下一轮竞赛起将发布白金组排行榜，届时我们将拥有更多认证成绩可供对比。本次竞赛的题目难度显然较高，仅有2项认证成绩与15项非认证成绩超过500分！

1 Hoof, Paper, Scissors Triples
查看问题 | 测试数据 | 解决方案
2 Lineup Counting Queries
查看问题 | 测试数据 | 解决方案
3 Pluses and Minuses
查看问题 | 测试数据 | 解决方案

USACO 2026 年 首场比赛，金牌

金组共有1917名参与者，其中1242人为预科生。所有在本比赛中获得800分或以上认证分数的选手将自动晋级白金组。晋升者的详细信息将在我们完成学术诚信检查后公布。相当多的选手在这场比赛后晋升至白金组，这也不奇怪，因为许多选手曾是白金级别的选手。

1 COW Traversals
查看问题 | 测试数据 | 解决方案
2 Milk Buckets
查看问题 | 测试数据 | 解决方案
3 Supervision
查看问题 | 测试数据 | 解决方案

USACO 2026 年 首场比赛，银牌

银组共有3876名参与者，其中2802人为大学预科生。所有在本比赛中得分达到700分或以上的选手将自动晋级金组。

1 Lineup Queries
查看问题 | 测试数据 | 解决方案
2 Mooclear Reactor
查看问题 | 测试数据 | 解决方案
3 Sliding Window Summation
查看问题 | 测试数据 | 解决方案

USACO 2026 年 首场比赛，铜牌

铜组共有10377名参赛者，其中7770人为预科生。所有在本比赛中得分达到或超过700分的选手将自动晋级银组。

1 Chip Exchange
查看问题 | 测试数据 | 解决方案
2 COW Splits
查看问题 | 测试数据 | 解决方案
3 Photoshoot
查看问题 | 测试数据 | 解决方案

2026赛季正式开启，令人兴奋！正如我们官网公告所示，本季赛事结构将做出若干调整——特别是首次推出三场线上赛，后续还将举办由专业监考人员执裁的全国邀请赛，角逐美国顶尖学生的桂冠。另一项变革是几乎所有顶尖选手将从金牌组开始参赛，而非铂金组。这一调整（以及赛季首赛的常规特征）带来了可观的晋升人数。鉴于我们题目难度多年来从未降低，本次赛事亦不例外，这一成绩相当亮眼。

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

Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows.

The field can be seen as a N×N grid (1≤N≤500), with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any K×K square that is part of the field (1≤K≤min(N,25)).

At all times, each cow has a beauty value between 0 and 10⁶ . The attractiveness index of a picture is the sum of the beauty values of the cows contained in the picture.

The beauty value for every cow starts out as 0, so the attractiveness index of any picture in the beginning is 0.

At Q times (1≤Q≤3⋅10⁴), the beauty of a single cow will increase by a positive integer due to eating the magical grass that is planted on Farmer John's field.

Farmer John wants to know the maximum attractiveness index of a picture he can take after each of the Q updates.

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

The first line contains integers N and K.

The following line contains an integer Q.

Each of the following Q lines contains three integers: r, c, and v, which are the row, column, and new beauty value, respectively (1≤r,c≤N,1≤v≤10⁶). It is guaranteed that the new beauty value is greater than the beauty value at that location before.

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

Output Q lines, corresponding to the maximum attractiveness index of a picture after each update.

SAMPLE INPUT:

4 2
3
2 2 11
3 4 3
3 1 100

SAMPLE OUTPUT:

11
11
111

After the first update, a picture with the maximum attractiveness index is the picture with upper left corner (2,2) and lower right corner (3,3), which has an attractiveness index of 11+0+0+0=11.

The second update does not affect the maximum attractiveness index.

After the third update, the picture with the maximum attractiveness index changes to the picture with upper left corner (2,1) and lower right corner (3,2), which has an attractiveness index of 0+11+100+0=111.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3
5
7

There is only one cow with a positive beauty value, so the maximum attractiveness index will always include that cow.

SCORING:

Inputs 3-6: N≤50,Q≤100
Inputs 7-10: N≤50
Inputs 11-18: No additional constraints.

Problem credits: Brian Law and Cici Liu

Bessie is given a positive integer N and a string S of length 3N which is generated by concatenating N strings of length 3, each of which is a cyclic shift of "COW". In other words, each string will be "COW", "OWC", or "WCO".

String X is a square string if and only if there exists a string Y such that X=Y+Y where +represents string concatenation. For example, "COWCOW" and "CC" are examples of square strings but "COWO" and "OC" are not.

In a single operation, Bessie can remove any subsequence T from S where T is a square string. A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string.

Your job is to help Bessie determine whether it is possible to transform S into an empty string. Additionally, if it is possible, then you must provide a way to do so.

Bessie is also given a parameter k which is either 0 or 1. Let M be the number of operations in your construction.

If k=0, then M must equal the minimum possible number of operations.
If k=1, then M can be up to one plus the minimum possible number of operations

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

The first line contains T, the number of independent test cases (1≤T≤10⁴) and k (0≤k≤1).

The first line of each test case has N(1≤N≤10⁵ ).

The second line of each test case has S.

The sum of N across all test cases will not exceed 10⁵.

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

For each test case, output either one or two lines using the following procedure.

If it is impossible to transform S into an empty string, print −1 on a single line.

Otherwise, on the first line print M -- the number of operations in your construction. On the second line, print 3N space-separated integers. The ith integer x indicates that the ith letter of S was deleted as part of the xth subsequence (1≤x≤M).

SAMPLE INPUT:

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

SAMPLE OUTPUT:

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

For the last test, the optimal number of operations is two, so any valid construction with either M=2 or M=3 would be accepted.

For M=3, here is a possible construction:

1.In the first operation, remove the last twelve characters. Now we're left with COWCOW.
2.In the second operation, remove the subsequence WW. Now we're left with COCO.
3.In the last operation, remove all remaining characters.

SAMPLE INPUT:

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

SAMPLE OUTPUT:

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2

SCORING:

Inputs 3-4: T≤10,N≤6,k=0
Inputs 5-6: k=1
Inputs 7-14: k=0

Problem credits: Aakash Gokhale

Bessie the cow has in her possession A chips of type A and B chips of type B (0≤A,B≤10⁹). She can perform the following operation as many times as she likes:

If you have at least c_B chips of type B, exchange c_B chips of type B for c_A chips of type A (1≤c_A ,c_B≤10⁹).

Determine the minimum non-negative integer x such that the following holds: after receiving x additional random chips, it is guaranteed that Bessie can end up with at least f_A chips of type A (0≤f_A≤10⁹).

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

The first line contains T, the number of independent test cases (1≤T≤10⁴).

Then follow T tests, each consisting of five integers A,B,c_A,c_B,f_A.

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

Output the answer for each test on a separate line.

Note: 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:

2
2 3 1 1 6
2 3 1 1 4

SAMPLE OUTPUT:

1
0

SAMPLE INPUT:

5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000

SAMPLE OUTPUT:

9
8
7
0
1000000000000000000

For the first test, Bessie initially starts with no chips. If she receives any 9 additional chips, she can perform the operation to end up with at least 5 chips of type A. For example, if she receives 2 chips of type A and 7 chips of type B, she can perform the operation twice to end up with 6≥5 chips of type A. However, if she only receive 8 chips of type B, she can only end up with 4<5 chips of type A.

For the fourth test, she already has enough chips of type A from the start.

SCORING:

Input 3: c_A=c_B=1
Inputs 4-5: x ≤10 for all cases
Inputs 6-7: c_A=2, c_B=3
Inputs 8-12: No additional constraints.

Problem credits: Benjamin Qi

Bessie has a hidden binary string b₁b₂…b_N(1≤N≤2⋅10⁵). The only information about b you are given is a binary string r₁r₂…r_N−K+1 (1≤K≤N), where r_i is the remainder when the number of ones in the length-K window of b with leftmost index i is divided by two.

Output the minimum and maximum possible numbers of ones in Bessie's hidden binary string.

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

There are T (1≤T≤10³) independent test cases to be solved. Each test is specified by the following:

The first line contains N and K.

The second line contains the binary string r₁…r_N−K+1, where (mod2).

It is guaranteed that the sum of N over all tests does not exceed 10⁶.

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

For each test case, output the minimum and maximum possible numbers of ones in Bessie's hidden binary string, separated by a single space.

SAMPLE INPUT:

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000

SAMPLE OUTPUT:

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

For the first test case, K=1 means that r=b, and the number of ones in r is 3.

For the second test case, there are two possibilities for b: 10001 and 01110, having 2 and 3 ones, respectively.

SCORING:

Input 2: N≤8
Inputs 3-4: K≤8 and the sum of N over all tests does not exceed 10⁴.
Inputs 5-11: No additional constraints.

Problem credits: Benjamin Qi

Bessie is designing a nuclear reactor to power Farmer John's lucrative new AI data center business, CowWeave!

The reactor core consists of N (1≤N≤2⋅10⁵ ) fuel rods, numbered 1 through N. The i-th rod has a "stable operating range" [l_i,r_i] (−10⁹≤l_i≤r_i≤10⁹), meaning it can only generate power if its energy a_i (chosen by Bessie) satisfies l_i≤a_i≤r_i; otherwise, it sits idle and does not generate power. Moreover, a_i must always be  an integer. Note that aican be any integer, not limited to [−10⁹,10⁹].

However, quantum interactions between the rods mean that there are M constraints of the form (x,y,z) where Bessie must satisfy a_x+a_y=z (1≤x,y≤N and −10⁹≤z≤10⁹) to prevent the reactor from melting down.

Help Bessie find the maximum number of power-generating rods she can achieve in her design without it melting down!

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

The first line contains T(1≤T≤10), the number of independent tests. Each test is specified in the following format:

The first line contains the two integers N and M.
The second line contains the N integers l₁,…,l_N.
The third line contains the N integers  r₁,…,r_N.
The next M lines each contain three integers x, y, and z, each representing a constraint.

It is guaranteed that neither the sum of N nor the sum of M over all tests exceeds 4⋅ 10⁵ .

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

If no choice of rod energies exists that satisfies all constraints, output −1. Otherwise, output the maximum number of power-generating rods Bessie can achieve.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

-1
2

In the second test, the constraints require that:

1.a₁+a₁=2
2.a₂+a₂=10

Choosing energies a=[1,5,3] results in 2 power-generating rods because:

l₁=1≤a₁≤1=r₁
l₃=3≤a₃≤3=r₃

and a satisfies all required constraints.

SAMPLE INPUT:

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0

SAMPLE OUTPUT:

3

Choosing rod energies a=[10,−10,10] results in 3 power-generating rods.

SAMPLE INPUT:

5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 2

SAMPLE OUTPUT:

2
-1
1
-1
1

SCORING:

Input 4: x=y for all constraints.
Inputs 5-7: |x−y|=1 for all constraints.
Inputs 8-10: |x−y|≤1 for all constraints.
Inputs 11-13: No additional conditions.

Problem credits: Akshaj Arora

There is a line of cows, initially (i.e. at time t=0) containing only cow 0 at position 0 (here, a cow is at position k if there are k cows in front of it). At time t for t=1,2,3,…, the cow at position 0 moves to position ⌊t/2⌋, every cow in positions 1…⌊t/2⌋ moves forward one position, and cow t joins the line at the end of the line (position t).

Answer Q (1≤Q≤ 10⁵ ) independent queries, each of one of the following types:

1.At what position is cow c immediately after time t (0≤c≤t≤10¹⁸)?
2.Which cow is at position x immediately after time t (0≤x≤t≤10¹⁸)?

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

The first line contains Q, the number of queries.

The next Q lines each contain three integers specifying a query either of the form "1 c t" or "2 x t."

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

Output the answer to each query on a separate line.

SAMPLE INPUT:

2
1 4 9
2 2 9

SAMPLE OUTPUT:

2
4

Lineups immediately after various times:

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

Immediately after t=9, the location of cow 4 is 2, and the cow located at position 2 is 4.

SAMPLE INPUT:

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000

SAMPLE OUTPUT:

1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

SCORING:

Input 3: Q≤1000,t≤100
Input 4: t≤5000
Inputs 5-8: All queries are of type 1.
Inputs 9-12: All queries are of type 2.

Problem credits: Agastya Goel

There are N(1≤N≤10⁶) cows in cow camp, labeled 1…N. Each cow is either a camper or a coach.

A nonempty subset of the cows will be selected to attend a field trip. If the ith cow is selected, the cow will move to position pi (0≤p_i≤10⁹) on a number line, where the array p is strictly increasing.

A nonempty subset of the cows is called "good" if for every selected camper, there is a selected coach within D units to the left, inclusive (0≤D≤10⁹). How many good subsets are there, modulo 10⁹+7?

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

The first line contains two integers N and D.

The next N lines each contain two integers pi and o_i. p_i denotes the position the ith cow will move to. o_i=1 means the ith cow is a coach, whereas o_i=0 means the ith cow is a camper.

It is guaranteed that the p_i are given in strictly increasing order.

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

Output the number of good subsets modulo 10⁹ +7.

SAMPLE INPUT:

6 1
3 1
4 0
6 1
7 1
9 0
10 0

SAMPLE OUTPUT:

11

The last two campers can never be selected. All other nonempty subsets work as long as if cow 2 is selected, then cow 1 is also selected.

SAMPLE INPUT:

20 24
3 0
14 0
17 1
20 0
21 0
22 1
28 0
30 0
32 0
33 1
38 0
40 0
52 0
58 0
73 0
75 0
77 1
81 1
84 1
97 0

SAMPLE OUTPUT:

13094

SCORING:

Input 3: N=20
Input 4: D=0
Inputs 5-8: N≤5000
Inputs 9-16: No additional constraints.

Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi

Bessie has challenged Farmer John to a game involving milk buckets! There are N
(2≤N≤2⋅10⁵ ) milk buckets lined up in a row. The i-th bucket from the left initially contains ai (0≤a_i≤10⁹) gallons of milk.

The game consists of two phases:

Phase 1: Farmer John may swap any two adjacent buckets. He may perform as many swaps as he likes, but each swap costs 1 coin.

Phase 2: After swapping, Farmer John performs the following operation until only one bucket is left: Choose two adjacent buckets with milk amounts a_i
and a_i+1, and replace both buckets with one bucket containing gallons of milk in their place.

Your goal is to determine the minimum number of coins Farmer John must spend in the swapping phase to maximize the amount of milk in the final bucket after all merges are complete.

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

The first line contains one integer T (1≤T≤100): the number of independent test cases.

Then, for each test case, the first line contains an integer N: the number of milk buckets. The second line contains N integers a₁,a₂,…,a_N, separated by spaces: the number of gallons of milk in each bucket.

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

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

For each test case, output the minimum number of coins Farmer John must spend to maximize the amount of milk in the final bucket.

SAMPLE INPUT:

2
3
0 0 1
3
0 1 0

SAMPLE OUTPUT:

0
1

For the first test, we do not need to swap any milk buckets in the first phase. In the second phase, Farmer John can merge the first two buckets and then merge the only two buckets left to achieve a final amount of 0.5. It can be shown that this final amount is maximal.

For the second test, we must perform a singular swap of the first two milk buckets in the first stage to achieve a final amount of 0.5 in the second stage. It can be shown that we cannot achieve a final amount of 0.5 without swaps in the first stage.

SAMPLE INPUT:

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

SAMPLE OUTPUT:

1
2
0
3

For the first test, Farmer John can swap the second and the third buckets in the first phase. Then, in the second phase, Farmer John can perform the following:

[9,9,4,2]-> merge the third and fourth buckets ->
[9,9,3]-> merge the second and third buckets ->
[9,6]-> merge the first and second buckets ->
[7.5]

The final amount of milk is 7.5, which is the maximum possible. It can be shown that even with additional swaps, the final amount cannot exceed 7.5, and that with fewer swaps, the final amount cannot reach 7.5.

SCORING:

Inputs 3-4: a_i ≤1 and N≤2000 (sum of N≤5000)
Inputs 5-6: a_i ≤1
Inputs 7-9: N≤2000 (sum of N≤5000)
Inputs 10-14: No additional constraints.

Problem credits: Charlie Yang