USACO 2025 - US Open - Hạng Đồng

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.

Trong một ván Hoof Paper Scissors, Bessie và Elsie có thể đưa ra một trong \(N\) (\(1 \leq N \leq 3000\)) ký hiệu móng khác nhau, được đánh số từ \(1\) đến \(N\), mỗi ký hiệu tương ứng với một vật liệu khác nhau. Có một bảng phức tạp mô tả cách các vật liệu tương tác với nhau; dựa trên bảng đó, một trong hai trường hợp sau xảy ra:

• Một ký hiệu thắng và ký hiệu còn lại thua.
• Hai ký hiệu hòa nhau.

Hoof Paper Scissors Minus One cũng tương tự, ngoại trừ Bessie và Elsie mỗi cô có thể đưa ra hai ký hiệu, mỗi móng một ký hiệu. Sau khi quan sát cả bốn ký hiệu đã được đưa ra, mỗi cô chọn một trong hai ký hiệu của mình để chơi. Kết quả được quyết định theo quy tắc Hoof Paper Scissors thông thường.

Biết \(M\) (\(1 \leq M \leq 3000\)) tổ hợp ký hiệu mà Elsie dự định sử dụng trong từng ván, Bessie muốn biết có bao nhiêu tổ hợp ký hiệu khác nhau giúp cô chắc chắn thắng Elsie. Một tổ hợp ký hiệu được định nghĩa là một cặp có thứ tự \((L,R)\), trong đó \(L\) là ký hiệu con bò đưa ra bằng móng trái và \(R\) là ký hiệu con bò đưa ra bằng móng phải. Hãy tính kết quả cho từng ván.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(M\), lần lượt là số ký hiệu móng và số ván mà Bessie và Elsie chơi.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(i\) ký tự \(a_{i,1}a_{i,2}\ldots a_{i,i}\), với mỗi \(a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}\). Nếu \(a_{i,j}=\texttt D\), ký hiệu \(i\) hòa ký hiệu \(j\). Nếu \(a_{i,j}=\texttt W\), ký hiệu \(i\) thắng ký hiệu \(j\). Nếu \(a_{i,j}=\texttt L\), ký hiệu \(i\) thua ký hiệu \(j\). Đảm bảo \(a_{i,i}=\texttt D\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(s_1\) và \(s_2\), với \(1 \leq s_1,s_2 \leq N\). Đây là tổ hợp ký hiệu của Elsie trong ván tương ứng.

Dữ liệu ra

In ra \(M\) dòng, dòng thứ \(i\) chứa số tổ hợp ký hiệu đảm bảo Bessie có thể thắng Elsie trong ván thứ \(i\).

Ví dụ

3 3
D
WD
LWD
1 2
2 3
1 1

0
0
5

Phân nhóm

• Dữ liệu 2–6: \(N,M\le 100\).
• Dữ liệu 7–12: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Bronze — Hoof Paper Scissors Minus One: https://usaco.org/index.php?page=viewproblem2&cpid=1515

Hôm nay những chú bò đặc biệt nghịch ngợm! Farmer John chỉ muốn chụp một bức ảnh các chú bò đứng thành hàng, nhưng chúng cứ di chuyển ngay trước khi ông kịp bấm máy.

Cụ thể, mỗi con trong số \(N\) con bò của FJ (\(1 \le N \le 10^5\)) có chiều cao nguyên từ \(1\) đến \(N\). FJ muốn chụp các chú bò đứng thành hàng theo một thứ tự rất cụ thể. Nếu chiều cao của chúng từ trái sang phải là \(h_1, \dots, h_K\), ông muốn dãy chiều cao thỏa mãn ba tính chất sau:

• Chiều cao tăng rồi giảm. Nói chính xác, phải tồn tại một số nguyên \(i\) sao cho \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
• Không có hai con bò đứng cạnh nhau có chiều cao bằng hệt nhau. Nói chính xác, \(h_i \neq h_{i+1}\) với mọi \(1 \le i < K\).
• Bức ảnh phải đối xứng. Nói chính xác, nếu \(i+j=K+1\) thì \(h_i=h_j\).

FJ muốn bức ảnh có nhiều bò nhất có thể. Cụ thể, FJ có thể loại bỏ một số con bò và sắp xếp lại những con còn lại. Hãy tính số bò tối đa có thể xuất hiện trong ảnh mà vẫn thỏa mãn các yêu cầu của ông.

Dữ liệu vào

Bạn phải trả lời nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên \(T\) (\(1 \leq T \leq 10^5\)), là số bộ dữ liệu. Sau đó là \(T\) bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên là chiều cao của \(N\) con bò hiện có. Mỗi chiều cao nằm trong khoảng từ \(1\) đến \(N\).

Đảm bảo tổng \(N\) trên tất cả các bộ dữ liệu không vượt quá \(10^6\).

Dữ liệu ra

In ra \(T\) dòng; dòng thứ \(i\) chứa đáp án cho bộ dữ liệu thứ \(i\). Mỗi dòng là một số nguyên biểu thị số bò tối đa FJ có thể đưa vào bức ảnh.

Ví dụ

2
4
1 1 2 3
4
3 3 2 1

3
1

Phân nhóm

• Dữ liệu 2–3: \(T\le 100, N\le 7\).
• Dữ liệu 4–5: \(T\le 10^4\), mọi con bò đều có chiều cao không quá \(10\).
• Dữ liệu 6–11: Không có ràng buộc bổ sung.

Đề bài: Nick Wu.

Nguồn

USACO 2025 US Open Contest, Bronze — More Cow Photos: https://usaco.org/index.php?page=viewproblem2&cpid=1516

Elsie đang cố kể cho Bessie nghe về kỳ thi USACO yêu thích của mình, nhưng Bessie không hiểu tại sao Elsie lại thích nó đến vậy. Elsie nói: “And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO”.

Bessie vẫn không hiểu, nên cô chép lại lời kể của Elsie thành một xâu độ dài \(N\) (\(3 \leq N \leq 10^5\)) gồm các chữ cái tiếng Anh viết thường \(s_1s_2\ldots s_N\). Elsie gọi một xâu \(t\) gồm ba ký tự là một moo nếu \(t_2=t_3\) và \(t_2\neq t_1\).

Một bộ ba \((i,j,k)\) là hợp lệ nếu \(i<j<k\) và xâu \(s_i s_j s_k\) tạo thành một moo. Với bộ ba đó, FJ thực hiện như sau để tính giá trị:

• FJ bẻ xâu \(s\) một góc 90 độ tại chỉ số \(j\).
• Giá trị của bộ ba bằng hai lần diện tích tam giác \(\Delta ijk\).

Nói cách khác, giá trị của bộ ba là \((j-i)(k-j)\).

Bessie hỏi bạn \(Q\) (\(1 \leq Q \leq 3\cdot 10^4\)) truy vấn. Trong mỗi truy vấn, cô đưa ra hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1\ge 3\)) và yêu cầu giá trị lớn nhất trong các bộ ba hợp lệ \((i,j,k)\) sao cho \(l\le i\) và \(k\le r\). Nếu không tồn tại bộ ba hợp lệ, in ra \(-1\).

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Dữ liệu vào

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

Dòng tiếp theo chứa \(s_1s_2\ldots s_N\).

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\), mô tả một truy vấn.

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng riêng.

Ví dụ

12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10

28
6
1
-1
12

Phân nhóm

• Dữ liệu 2–3: \(N,Q\le 50\).
• Dữ liệu 4–6: \(Q=1\) và truy vấn duy nhất thỏa mãn \(l=1\), \(r=N\).
• Dữ liệu 7–11: Không có ràng buộc bổ sung.

Đề bài: Chongtian Ma.

Nguồn

USACO 2025 US Open Contest, Bronze — It's Mooin' Time III: https://usaco.org/index.php?page=viewproblem2&cpid=1517