USACO 2021 - US Open - Hạng Bạch Kim

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 2021 - United Cows of Farmer John 100 (p) 4.0s 512M
2 USACO 2021 - Routing Schemes 100 (p) 4.0s 512M
3 USACO 2021 - Balanced Subsets 100 (p) 4.0s 512M

1. USACO 2021 - United Cows of Farmer John

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

Liên hiệp Bò của Farmer John (UCFJ) đang cử một đoàn đại biểu tham dự Olympic Tin học Bò Quốc tế (IOI).

Có \(N\) con bò tham gia quá trình tuyển chọn (\(1\le N\le2\cdot10^5\)). Chúng đang đứng thành một hàng, và con bò thứ \(i\) thuộc giống \(b_i\).

Đoàn đại biểu sẽ là một đoạn liên tiếp gồm ít nhất ba con bò, tức các con bò \(l\ldots r\) với hai số nguyên \(l\) và \(r\) thỏa mãn \(1\le l<r\le N\) và \(r-l\ge2\). Ba con bò trong đoạn được chọn làm trưởng đoàn. Vì lý do pháp lý, hai con bò ở hai đầu đoạn bắt buộc phải là trưởng đoàn. Ngoài ra, để tránh xung đột trong cùng giống, mỗi trưởng đoàn phải thuộc một giống khác với tất cả thành viên còn lại của đoàn, bất kể thành viên đó có phải trưởng đoàn hay không.

Hãy giúp UCFJ xác định, vì lý do thuế, số cách chọn đoàn đại biểu tham dự IOI. Hai đoàn được coi là khác nhau nếu chúng có thành viên khác nhau hoặc có các trưởng đoàn khác nhau.

Dữ liệu vào

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

Dòng thứ hai chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\), mỗi số thuộc đoạn \([1,N]\).

Dữ liệu ra

In số đoàn đại biểu có thể chọn trên một dòng.

Lưu ý rằng do các số nguyên trong bài có thể rất lớn, bạn có thể cần dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++.

Phân nhóm

  • Các test 1-2 thỏa mãn \(N\le50\).
  • Các test 3-4 thỏa mãn \(N\le500\).
  • Các test 5-8 thỏa mãn \(N\le5000\).
  • Các test 9-20 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
7
1 2 3 4 3 2 5
Output 
9

Mỗi đoàn đại biểu tương ứng với một trong các bộ ba trưởng đoàn sau:

\[ (1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7). \]

Nguồn

USACO 2021 US Open, Platinum - United Cows of Farmer John: https://usaco.org/index.php?page=viewproblem2&cpid=1140

Tác giả: Benjamin Qi.

2. USACO 2021 - Routing Schemes

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

Xét một mạng gồm \(N\) nút (\(2\le N\le100\)) được đánh số \(1\ldots N\). Mỗi nút được chỉ định là nút gửi, nút nhận hoặc không thuộc loại nào. Số nút gửi là \(S\), bằng số nút nhận, và \(S\ge1\).

Các liên kết giữa những nút trong mạng được mô tả bằng một danh sách cạnh có hướng, mỗi cạnh có dạng \(i\to j\), nghĩa là nút \(i\) có thể định tuyến đến nút \(j\). Tất cả các cạnh này đều thỏa mãn \(i<j\), ngoại trừ \(K\) cạnh thỏa mãn \(i>j\) (\(0\le K\le2\)). Không có khuyên, tức cạnh dạng \(i\to i\).

Một “phương án định tuyến” là một tập gồm \(S\) đường đi có hướng từ các nút gửi đến các nút nhận sao cho không có hai đường đi nào chung đầu mút. Nói cách khác, các đường đi nối các nút gửi phân biệt tới các nút nhận phân biệt. Một đường đi từ nút gửi \(s\) đến nút nhận \(r\) có thể được mô tả bằng dãy nút

\[ s=v_0\to v_1\to v_2\to\cdots\to v_e=r \]

sao cho cạnh có hướng \(v_i\to v_{i+1}\) tồn tại với mọi \(0\le i<e\). Một nút có thể xuất hiện nhiều lần trong cùng một đường đi.

Hãy đếm số phương án định tuyến phân biệt sao cho mỗi cạnh có hướng được đi qua đúng một lần. Vì kết quả có thể rất lớn, hãy in phần dư theo \(10^9+7\). Dữ liệu bảo đảm có ít nhất một phương án thỏa mãn các điều kiện này.

Mỗi dữ liệu vào chứa \(T\) bộ test (\(1\le T\le20\)) cần được giải độc lập. Tổng \(N^2\) trên mọi bộ test không vượt quá \(2\cdot10^4\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(K\). Lưu ý rằng \(S\) không được cho trực tiếp trong dữ liệu vào.

Dòng thứ hai của mỗi bộ test chứa một xâu độ dài \(N\). Ký tự thứ \(i\) của xâu là S nếu nút thứ \(i\) là nút gửi, R nếu nút thứ \(i\) là nút nhận, và . nếu nút thứ \(i\) không thuộc loại nào. Số ký tự R bằng số ký tự S, và có ít nhất một ký tự S.

\(N\) dòng tiếp theo của mỗi bộ test, mỗi dòng chứa một xâu bit gồm \(N\) chữ số 0 và 1. Bit thứ \(j\) của dòng thứ \(i\) bằng \(1\) nếu có cạnh có hướng từ nút \(i\) đến nút \(j\), và bằng \(0\) nếu không có. Do không có khuyên, đường chéo chính của ma trận chỉ gồm các chữ số 0. Ngoài ra, có đúng \(K\) chữ số 1 nằm dưới đường chéo chính.

Các bộ test liên tiếp được ngăn cách bằng dòng trống cho dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in số phương án định tuyến sao cho mỗi cạnh được đi qua đúng một lần, lấy phần dư theo \(10^9+7\). Dữ liệu bảo đảm mỗi bộ test có ít nhất một phương án hợp lệ.

Phân nhóm

  • Các test 4-5 thỏa mãn \(N\le6\).
  • Các test 6-7 thỏa mãn \(K=0\).
  • Các test 8-12 thỏa mãn \(K=1\).
  • Các test 13-24 thỏa mãn \(K=2\).

Ví dụ

Ví dụ 1

Input 
2

8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000

13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000
Output 
4
12

Ví dụ 2

Input 
2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000
Output 
3
1

Ví dụ 3

Input 
5

3 2
RS.
010
101
100

4 2
.R.S
0100
0010
1000
0100

4 2
.SR.
0000
0011
0100
0010

5 2
.SSRR
01000
10101
01010
00000
00000

6 2
SS..RR
001010
000010
000010
000010
100101
000000
Output 
2
1
2
6
24

Giải thích ví dụ 1. Trong bộ test đầu tiên, các cạnh là \(1\to3\), \(2\to3\), \(3\to4\), \(3\to5\), \(4\to6\), \(5\to6\), \(6\to7\), \(6\to8\). Có bốn phương án định tuyến:

  • \(1\to3\to4\to6\to7, 2\to3\to5\to6\to8\)
  • \(1\to3\to5\to6\to7, 2\to3\to4\to6\to8\)
  • \(1\to3\to4\to6\to8, 2\to3\to5\to6\to7\)
  • \(1\to3\to5\to6\to8, 2\to3\to4\to6\to7\)

Trong bộ test thứ hai, các cạnh là \(1\to4\), \(2\to4\), \(3\to4\), \(4\to5\), \(4\to6\), \(4\to7\), \(8\to10\), \(9\to10\), \(10\to11\), \(10\to12\). Một phương án có thể có các đường đi:

  • \(1\to4\to5\)
  • \(2\to4\to7\)
  • \(3\to4\to6\)
  • \(8\to10\to12\)
  • \(9\to10\to11\)

Nói chung, các nút gửi \(\{1,2,3\}\) có thể định tuyến tới một hoán vị bất kỳ của các nút nhận \(\{5,6,7\}\), và các nút gửi \(\{8,9\}\) có thể định tuyến tới một hoán vị bất kỳ của các nút nhận \(\{11,12\}\), cho kết quả \(6\cdot2=12\).

Giải thích ví dụ 2. Trong bộ test đầu tiên, các cạnh là \(1\to3\), \(1\to5\), \(2\to3\), \(3\to1\), \(3\to4\). Có ba phương án định tuyến:

  • \(1\to3\to1\to5\), \(2\to3\to4\)
  • \(1\to3\to4\), \(2\to3\to1\to5\)
  • \(1\to5\), \(2\to3\to1\to3\to4\)

Trong bộ test thứ hai, các cạnh là \(1\to3\), \(2\to4\), \(3\to2\), \(3\to6\), \(4\to5\), \(5\to3\). Chỉ có một phương án định tuyến:

\(1\to3\to2\to4\to5\to3\to6\).

Giải thích ví dụ 3. Đây là một số bộ test nhỏ bổ sung.

Nguồn

USACO 2021 US Open, Platinum - Routing Schemes: https://usaco.org/index.php?page=viewproblem2&cpid=1141

Tác giả: Benjamin Qi.

3. USACO 2021 - Balanced Subsets

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

Có thể coi đồng cỏ của Farmer John là một lưới hai chiều rộng gồm các ô vuông, giống như một bàn cờ khổng lồ. Các ô được gán nhãn bằng cặp có thứ tự \((i,j)\) với mọi \(1\le i\le N\), \(1\le j\le N\) (\(1\le N\le150\)). Một số ô có cỏ.

Một tập con không rỗng của các ô lưới được gọi là “cân bằng” nếu thỏa mãn các điều kiện sau:

  1. Mọi ô trong tập con đều có cỏ.
  2. Tập con liên thông bốn hướng. Nói cách khác, giữa hai ô bất kỳ trong tập con luôn tồn tại một đường đi sao cho hai ô liên tiếp trên đường đi kề nhau theo chiều ngang hoặc dọc.
  3. Nếu các ô \((x_1,y)\) và \((x_2,y)\), với \(x_1\le x_2\), thuộc tập con, thì mọi ô \((x,y)\) với \(x_1\le x\le x_2\) cũng thuộc tập con.
  4. Nếu các ô \((x,y_1)\) và \((x,y_2)\), với \(y_1\le y_2\), thuộc tập con, thì mọi ô \((x,y)\) với \(y_1\le y\le y_2\) cũng thuộc tập con.

Hãy đếm số tập con cân bằng, lấy phần dư theo \(10^9+7\).

Dữ liệu vào

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

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(N\) ký tự. Ký tự thứ \(j\) của dòng thứ \(i\) tính từ trên xuống là G nếu ô \((i,j)\) có cỏ, và là . nếu không có cỏ.

Dữ liệu ra

In số tập con cân bằng lấy phần dư theo \(10^9+7\).

Phân nhóm

  • Các test 1-4 thỏa mãn \(N\le4\).
  • Các test 5-10 thỏa mãn \(N\le20\).
  • Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
2
GG
GG
Output 
13

Ví dụ 2

Input 
4
GGGG
GGGG
GG.G
GGGG
Output 
642

Giải thích ví dụ 1. Trong bộ test này, mọi tập con liên thông bốn hướng đều cân bằng:

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

Giải thích ví dụ 2. Dưới đây là một tập con thỏa mãn điều kiện thứ hai, tức liên thông bốn hướng, nhưng không thỏa mãn điều kiện thứ ba:

GG..
.G..
GG..
....

Nguồn

USACO 2021 US Open, Platinum - Balanced Subsets: https://usaco.org/index.php?page=viewproblem2&cpid=1142

Tác giả: Benjamin Qi.