| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2022 - Lonely Photo | 100 (p) | 4.0s | 512M |
| 2 | USACO 2022 - Air Cownditioning | 100 (p) | 4.0s | 512M |
| 3 | USACO 2022 - Walking Home | 100 (p) | 4.0s | 512M |
Farmer John vừa mua thêm \(N\) con bò mới (\(3 \le N \le 5 \times 10^5\)), mỗi con thuộc giống Guernsey hoặc Holstein.
Các con bò hiện đang đứng thành một hàng, và Farmer John muốn chụp ảnh mọi dãy gồm ít nhất ba con bò liên tiếp. Tuy nhiên, ông không muốn chụp một bức ảnh có đúng một con bò giống Guernsey hoặc đúng một con bò giống Holstein — ông cho rằng con bò đơn độc ấy sẽ cảm thấy bị cô lập và ngượng ngùng. Sau khi chụp ảnh mọi dãy gồm ít nhất ba con bò, ông loại bỏ tất cả những bức ảnh được gọi là "cô đơn" này, tức các ảnh có đúng một con Guernsey hoặc đúng một con Holstein.
Cho biết thứ tự các con bò trong hàng, hãy giúp Farmer John xác định số bức ảnh cô đơn mà ông sẽ loại bỏ. Hai bức ảnh được coi là khác nhau nếu chúng bắt đầu hoặc kết thúc tại những con bò khác nhau trong hàng.
Dòng đầu tiên chứa \(N\).
Dòng thứ hai chứa một xâu gồm \(N\) ký tự. Ký tự thứ \(i\) là G nếu con bò thứ \(i\) trong hàng là Guernsey. Nếu không, ký tự đó là H và con bò thứ \(i\) là Holstein.
In ra số bức ảnh Farmer John sẽ loại bỏ vì chúng cô đơn.
long long int 64 bit trong C++).Ví dụ 1
5
GHGHG3Mọi xâu con có độ dài \(3\) trong ví dụ này đều chứa đúng một con bò giống Guernsey hoặc đúng một con bò giống Holstein, nên các xâu con này biểu diễn những bức ảnh cô đơn và sẽ bị Farmer John loại bỏ. Tất cả các xâu con dài hơn (GHGH, HGHG và GHGHG) đều được ông chấp nhận.
USACO 2021 December Contest, Bronze — Lonely Photo. Tác giả: Nick Wu.
\(N\) con bò của Farmer John rất khắt khe về nhiệt độ trong chuồng. Một số con thích nhiệt độ mát hơn, trong khi những con khác thích ấm hơn.
Chuồng của Farmer John có một dãy \(N\) ô chuồng, được đánh số \(1 \ldots N\), mỗi ô chứa đúng một con bò. Con bò thứ \(i\) muốn nhiệt độ ô của mình là \(p_i\), còn nhiệt độ hiện tại trong ô là \(t_i\). Để đảm bảo mọi con bò đều thoải mái, Farmer John lắp đặt một hệ thống điều hòa mới được điều khiển theo cách khá thú vị. Ông có thể gửi lệnh cho hệ thống để tăng hoặc giảm nhiệt độ của một dãy ô chuồng liên tiếp đúng \(1\) đơn vị — ví dụ: "tăng nhiệt độ trong các ô \(5 \ldots 8\) thêm 1 đơn vị". Dãy ô chuồng có thể chỉ gồm một ô.
Hãy giúp Farmer John xác định số lệnh ít nhất cần gửi cho hệ thống điều hòa mới để nhiệt độ trong mỗi ô chuồng đạt mức lý tưởng của con bò sống tại đó.
Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên không âm \(p_1 \ldots p_N\), cách nhau bởi dấu cách. Dòng cuối cùng chứa \(N\) số nguyên không âm \(t_1 \ldots t_N\).
In ra một số nguyên duy nhất là số lệnh ít nhất Farmer John cần sử dụng.
Ví dụ 1
5
1 5 3 3 4
1 2 2 2 15Một tập lệnh tối ưu mà Farmer John có thể sử dụng là:
Nhiệt độ ban đầu: 1 2 2 2 1
Tăng các ô 2..5: 1 3 3 3 2
Tăng các ô 2..5: 1 4 4 4 3
Tăng các ô 2..5: 1 5 5 5 4
Giảm các ô 3..4: 1 5 4 4 4
Giảm các ô 3..4: 1 5 3 3 4
USACO 2021 December Contest, Bronze — Air Cownditioning. Tác giả: Brian Dean.
Bessie đang cố đi bộ từ đồng cỏ yêu thích của mình về chuồng.
Đồng cỏ và trang trại nằm trên một lưới \(N \times N\) (\(2 \leq N \leq 50\)), với đồng cỏ của Bessie ở góc trên bên trái và chuồng ở góc dưới bên phải. Bessie muốn về nhà càng sớm càng tốt nên cô chỉ đi xuống dưới và sang phải. Ở một số vị trí có các kiện cỏ khô mà Bessie không thể đi xuyên qua; cô phải đi vòng qua chúng.
Hôm nay Bessie hơi mệt nên cô muốn đổi hướng đi không quá \(K\) lần (\(1 \leq K \leq 3\)).
Bessie có thể đi từ đồng cỏ yêu thích về chuồng theo bao nhiêu đường đi phân biệt? Hai đường đi được coi là phân biệt nếu có một ô vuông mà Bessie đi qua trong đường này nhưng không đi qua trong đường kia.
Mỗi dữ liệu vào chứa \(T\) bộ dữ liệu con, mỗi bộ mô tả một trang trại khác nhau và tất cả đều phải được trả lời đúng để vượt qua toàn bộ dữ liệu. Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 50\)). Sau đó là \(T\) bộ dữ liệu con.
Mỗi bộ dữ liệu con bắt đầu bằng một dòng chứa \(N\) và \(K\).
\(N\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(N\) ký tự. Mỗi ký tự là . nếu ô đó trống hoặc H nếu ô đó có một kiện cỏ khô. Đảm bảo rằng góc trên bên trái và góc dưới bên phải của trang trại không chứa kiện cỏ khô.
In ra \(T\) dòng, dòng thứ \(i\) chứa số đường đi phân biệt Bessie có thể chọn trong bộ dữ liệu con thứ \(i\).
Ví dụ 1
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...2
4
6
2
0
0
6Ta biểu diễn các đường đi khả dĩ của Bessie bằng các xâu gồm D và R, lần lượt chỉ việc Bessie đi xuống dưới hoặc sang phải.
Trong bộ dữ liệu con thứ nhất, hai đường đi khả dĩ của Bessie là DDRR và RRDD.
Trong bộ dữ liệu con thứ hai, bốn đường đi khả dĩ của Bessie là DDRR, DRRD, RDDR và RRDD.
Trong bộ dữ liệu con thứ ba, sáu đường đi khả dĩ của Bessie là DDRR, DRDR, DRRD, RDDR, RDRD và RRDD.
Trong bộ dữ liệu con thứ tư, hai đường đi khả dĩ của Bessie là DDRR và RRDD.
Trong bộ dữ liệu con thứ năm và thứ sáu, Bessie không thể đi bộ về chuồng.
Trong bộ dữ liệu con thứ bảy, sáu đường đi khả dĩ của Bessie là DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD và RRDRDD.
USACO 2021 December Contest, Bronze — Walking Home. Tác giả: Nick Wu.