USACO 2025 - US Open - Hạng Vàng

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2025 - Moo Decomposition 100 (p) 4.0s 512M
2 USACO 2025 - Election Queries 100 (p) 4.0s 512M
3 USACO 2025 - OohMoo Milk 100 (p) 4.0s 512M

1. USACO 2025 - Moo Decomposition

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn có một xâu dài \(S\) gồm các ký tự M và O, cùng một số nguyên \(K\geq 1\). Hãy đếm số cách phân tách \(S\) thành các dãy con sao cho mỗi dãy con có dạng MOOOO....O với đúng \(K\) ký tự O, lấy modulo \(10^9+7\).

Vì xâu rất dài nên bạn không được cung cấp nó một cách tường minh. Thay vào đó, bạn được cho một số nguyên \(L\) (\(1\leq L\leq 10^{18}\)) và một xâu \(T\) độ dài \(N\) (\(1\leq N\leq 10^6\)). Xâu \(S\) là phép nối của \(L\) bản sao của xâu \(T\).

Dữ liệu vào

Dòng đầu tiên chứa \(K\), \(N\) và \(L\).

Dòng thứ hai chứa xâu \(T\) độ dài \(N\). Mỗi ký tự là M hoặc O.

Đảm bảo số cách phân tách \(S\) khác không.

Dữ liệu ra

In ra số cách phân tách xâu \(S\), lấy modulo \(10^9+7\).

Ví dụ

Ví dụ 1

Input 
2 6 1
MOOMOO
Output 
1
Giải thích

Cách duy nhất để phân tách \(S\) thành các MOO là cho ba ký tự đầu tiên tạo thành một MOO và ba ký tự cuối cùng tạo thành một MOO khác.

Ví dụ 2

Input 
2 6 1
MMOOOO
Output 
6
Giải thích

Có sáu cách khác nhau để phân tách xâu thành các dãy con (chữ hoa tạo thành một MOO, chữ thường tạo thành MOO còn lại):

  • MmOOoo
  • MmOoOo
  • MmOooO
  • MmoOOo
  • MmoOoO
  • MmooOO

Ví dụ 3

Input 
1 4 2
MMOO
Output 
4

Ví dụ 4

Input 
1 4 100
MMOO
Output 
976371285
Giải thích

Hãy nhớ lấy đáp án modulo \(10^9+7\).

Phân nhóm

  • Dữ liệu 5–7: \(K=1\), \(L=1\).
  • Dữ liệu 8–10: \(K=2\), \(N\leq 1000\), \(L=1\).
  • Dữ liệu 11–13: \(K=1\).
  • Dữ liệu 14–19: \(L=1\).
  • Dữ liệu 20–25: Không có ràng buộc bổ sung.

Đề bài: Dhruv Rohatgi.

Nguồn

USACO 2025 US Open Contest, Gold — Moo Decomposition: https://usaco.org/index.php?page=viewproblem2&cpid=1521

2. USACO 2025 - Election Queries

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần giới hạn mặc định.

Farmer John có \(N\) (\(2\leq N\leq 2\cdot 10^5\)) con bò được đánh số từ \(1\) đến \(N\). Một cuộc bầu cử đang được tổ chức tại trang trại của FJ để chọn ra hai bò lãnh đạo mới. Ban đầu, biết rằng bò \(i\) sẽ bỏ phiếu cho bò \(a_i\) (\(1\leq a_i\leq N\)).

Để chọn ra hai bò lãnh đạo, FJ tiến hành cuộc bầu cử theo quy trình sau:

  • Chọn một tập con tùy ý \(S\) gồm ít nhất một con bò nhưng không gồm tất cả các con bò. FJ có thể chọn bò \(x\) làm bò lãnh đạo thứ nhất nếu số phiếu dành cho nó xuất hiện nhiều nhất trong tất cả các phiếu của những con bò thuộc \(S\).
  • FJ có thể chọn bò \(y\) làm bò lãnh đạo thứ hai nếu số phiếu dành cho nó xuất hiện nhiều nhất trong tất cả các phiếu của những con bò không thuộc \(S\).
  • Với một tập con \(S\) cố định, FJ định nghĩa độ đa dạng giữa hai bò lãnh đạo là \(|x-y|\). Vì FJ không thích các lãnh đạo có số hiệu gần nhau, ông muốn chọn \(S\) sao cho độ đa dạng lớn nhất. Lưu ý rằng nếu FJ không thể chọn hai bò lãnh đạo khác nhau thì độ đa dạng bằng \(0\).

Tuy nhiên, một số con bò liên tục thay đổi ý định, và FJ có thể phải tổ chức lại cuộc bầu cử nhiều lần! Vì vậy, ông hỏi bạn \(Q\) (\(1\leq Q\leq 10^5\)) truy vấn. Trong mỗi truy vấn, một con bò thay đổi lá phiếu của mình. Sau mỗi truy vấn, ông hỏi độ đa dạng lớn nhất có thể có giữa hai bò lãnh đạo mới.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa \(a_1,a_2,\ldots,a_N\).

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(x\), biểu thị cập nhật \(a_i=x\) (\(1\leq i,x\leq N\)).

Dữ liệu ra

In ra \(Q\) dòng; dòng thứ \(i\) là độ đa dạng lớn nhất có thể sau \(i\) truy vấn đầu tiên.

Ví dụ

Ví dụ 1

Input 
5 3
1 2 3 4 5
3 4
1 2
5 2
Output 
4
3
2
Giải thích

Sau truy vấn đầu tiên, \(a=[1,2,4,4,5]\). Ở bước đầu tiên của cuộc bầu cử, FJ có thể chọn \(S=\{1,3\}\). Khi đó, bò \(1\) nhận một phiếu và bò \(4\) nhận một phiếu. Vì vậy, FJ có thể chọn bò \(1\) hoặc bò \(4\) làm bò lãnh đạo thứ nhất.

Trong số tất cả những con bò không thuộc \(S\), bò \(2\) nhận một phiếu, bò \(4\) nhận một phiếu và bò \(5\) cũng nhận một phiếu. Vì vậy, FJ có thể chọn bất kỳ con nào trong các bò \(2\), \(4\), \(5\) làm bò lãnh đạo thứ hai.

Để đạt độ đa dạng lớn nhất, FJ có thể chọn bò \(1\) làm bò lãnh đạo thứ nhất và bò \(5\) làm bò lãnh đạo thứ hai. Do đó, độ đa dạng là \(|1-5|=4\).

Sau truy vấn thứ hai, \(a=[2,2,4,4,5]\) và FJ có thể chọn \(S=\{4,5\}\). Khi đó, ông có thể chọn \(5\) làm bò lãnh đạo thứ nhất và bò \(2\) làm bò lãnh đạo thứ hai. Độ đa dạng lớn nhất có thể là \(|5-2|=3\).

Ví dụ 2

Input 
8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 4
Output 
4
4
4
7
7

Phân nhóm

  • Dữ liệu 3–4: \(N,Q\leq 100\).
  • Dữ liệu 5–7: \(N,Q\leq 3000\).
  • Dữ liệu 8–15: Không có ràng buộc bổ sung.

Đề bài: Chongtian Ma và Haokai Ma.

Nguồn

USACO 2025 US Open Contest, Gold — Election Queries: https://usaco.org/index.php?page=viewproblem2&cpid=1522

3. USACO 2025 - OohMoo Milk

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Farmer John đang cố sản xuất loại sữa OohMoo Milk nổi tiếng thế giới của mình để bán kiếm lời. Ông có \(N\) (\(1\leq N\leq 10^5\)) chai cần đổ đầy. Ban đầu, mỗi chai chứa một lượng sữa \(m_i\) (\(0\leq m_i\leq 10^9\)). Mỗi ngày, ông chọn \(A\) (\(1\le A\le N\)) chai và đổ thêm một đơn vị sữa vào mỗi chai.

Không may, Farmer Nhoj, đối thủ của Farmer John trong ngành kinh doanh OohMoo Milk, biết quy trình sản xuất của Farmer John và có kế hoạch kìm hãm việc kinh doanh của ông. Mỗi ngày, sau khi Farmer John đổ sữa vào \(A\) chai, Farmer Nhoj sẽ lén lấy đi một đơn vị sữa từ mỗi chai trong số \(B\) (\(0\le B<A\)) chai khác nhau đang không rỗng. Để tránh bị phát hiện, Farmer Nhoj chọn \(B\) nhỏ hơn hẳn \(A\), khiến Farmer John ít có khả năng phát hiện ra hắn hơn.

Sau \(D\) (\(1\leq D\leq 10^9\)) ngày, Farmer John sẽ bán OohMoo Milk. Nếu một chai có \(M\) đơn vị sữa, nó sẽ được bán với giá \(M^2\) moonie.

Gọi \(P\) là lợi nhuận duy nhất sao cho FJ có thể đảm bảo kiếm được ít nhất \(P\) bất kể FN hành động thế nào, và FN có thể đảm bảo FJ kiếm được nhiều nhất \(P\) bất kể FJ hành động thế nào. Hãy in \(P\) modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(D\), trong đó \(N\) là số chai và \(D\) là số ngày.

Dòng thứ hai chứa \(A\) và \(B\), lần lượt là số đơn vị sữa Farmer John thêm vào và Farmer Nhoj lấy đi.

Dòng thứ ba chứa \(N\) số nguyên \(m_i\) cách nhau bởi dấu cách, biểu thị lượng sữa ban đầu trong mỗi chai.

Dữ liệu ra

In ra giá trị \(P\) modulo \(10^9+7\).

Ví dụ

Ví dụ 1

Input 
5 4
4 2
4 10 8 10 10
Output 
546
Giải thích

Trong ngày đầu tiên, Farmer John có thể thêm sữa vào chai thứ hai, thứ ba, thứ tư và thứ năm. Sau đó, Farmer Nhoj có thể lấy sữa khỏi chai thứ hai và thứ tư.

Vì vậy, lượng sữa mới trong mỗi chai là

\[ [4,10,8,10,10]\to[4,11,9,11,11]\to[4,10,9,10,11]. \]

Sau bốn ngày, lượng sữa trong mỗi chai có thể là

\[ [4,10,8,10,10]\to[4,10,9,10,11]\to[4,10,10,11,11]\to[4,11,11,11,11]\to[4,11,11,12,12]. \]

Tổng số moonie Farmer John kiếm được trong trường hợp này là \(4^2+11^2+11^2+12^2+12^2=546\). Có thể chứng minh đây là giá trị của \(P\).

Ví dụ 2

Input 
10 5
5 1
1 2 3 4 5 6 7 8 9 10
Output 
777

Ví dụ 3

Input 
5 1000000000
3 1
0 1 2 3 4
Output 
10
Giải thích

Hãy nhớ in \(P\) modulo \(10^9+7\).

Phân nhóm

  • Dữ liệu 4–6: \(N,D\le 1000\).
  • Dữ liệu 7–10: \(D\le 10^6\).
  • Dữ liệu 11–20: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Gold — OohMoo Milk: https://usaco.org/index.php?page=viewproblem2&cpid=1523