| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Cave Paintings | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Non-Decreasing Subsequences | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - Falling Portals | 100 (p) | 4.0s | 512M |
Bessie đã trở thành một họa sĩ và đang sáng tác những bức tranh về hang động! Tác phẩm hiện tại của cô là một lưới cao \(N\) hàng, mỗi hàng có đúng \(M\) ô vuông (\(1\le N,M\le 1000\)). Mỗi ô vuông ở một trong ba trạng thái: trống, chứa đá hoặc chứa nước. Bessie đã tô những ô chứa đá, bao gồm toàn bộ đường biên của bức tranh. Giờ đây, cô muốn tô một số ô trống bằng nước sao cho nếu bức tranh là thật thì nước không có chuyển động ròng. Định nghĩa độ cao của một ô ở hàng thứ \(i\) tính từ trên xuống là \(N+1-i\). Bessie muốn bức tranh của mình thỏa mãn điều kiện sau:
Giả sử ô \(a\) chứa nước. Nếu tồn tại một đường đi từ \(a\) đến ô \(b\) chỉ qua các ô trống hoặc ô chứa nước có độ cao không lớn hơn ô \(a\), sao cho mỗi hai ô liên tiếp trên đường đi có chung một cạnh, thì ô \(b\) cũng phải chứa nước.
Hãy tìm số bức tranh khác nhau Bessie có thể tạo ra, lấy modulo \(10^9+7\). Bessie có thể tô bằng nước một số lượng ô trống bất kỳ, kể cả không tô ô nào hoặc tô tất cả các ô.
Dữ liệu vào được đọc từ tệp cave.in.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự. Mỗi ký tự là . hoặc #, lần lượt biểu thị một ô trống và một ô chứa đá. Hàng đầu tiên, hàng cuối cùng, cột đầu tiên và cột cuối cùng chỉ chứa ký tự #.
Ghi ra tệp cave.out một số nguyên: số bức tranh thỏa mãn điều kiện, lấy modulo \(10^9+7\).
Ví dụ 1
4 9
#########
#...#...#
#.#...#.#
#########9Nếu một ô ở hàng thứ hai được tô bằng nước thì tất cả các ô trống đều phải được tô bằng nước. Nếu không, giả sử không có ô nào như vậy được tô bằng nước. Khi đó, Bessie có thể chọn tô bằng nước một tập con bất kỳ trong ba vùng ô trống liên thông theo chiều ngang ở hàng thứ ba. Vì vậy, số bức tranh bằng \(1+2^3=9\).
Gần đây Bessie tham gia một kỳ thi USACO và gặp bài toán sau. Tất nhiên, Bessie biết cách giải nó. Còn bạn thì sao?
Xét một dãy \(A_1,A_2,\ldots,A_N\) có độ dài \(N\) (\(1\le N\le 5\cdot 10^4\)), chỉ gồm các số nguyên trong khoảng \(1\ldots K\) (\(1\le K\le 20\)). Bạn được cho \(Q\) truy vấn (\(1\le Q\le 2\cdot 10^5\)) có dạng \([L_i,R_i]\) (\(1\le L_i\le R_i\le N\)). Với mỗi truy vấn, hãy tính số dãy con không giảm của \(A_{L_i},A_{L_i+1},\ldots,A_{R_i}\) theo modulo \(10^9+7\).
Một dãy con không giảm của \(A_L,\ldots,A_R\) là một tập hợp chỉ số \((j_1,j_2,\ldots,j_x)\) sao cho \(L\le j_1<j_2<\cdots<j_x\le R\) và \(A_{j_1}\le A_{j_2}\le\cdots\le A_{j_x}\). Hãy nhớ tính cả dãy con rỗng!
Dữ liệu vào được đọc từ tệp nondec.in.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\), cách nhau bởi dấu cách.
Dòng thứ ba chứa một số nguyên \(Q\).
Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(L_i\) và \(R_i\), cách nhau bởi dấu cách.
Với mỗi truy vấn \([L_i,R_i]\), ghi ra tệp nondec.out trên một dòng mới số dãy con không giảm của \(A_{L_i},A_{L_i+1},\ldots,A_{R_i}\) theo modulo \(10^9+7\).
Ví dụ 1
5 2
1 2 1 1 2
3
2 3
4 5
1 53
4
20Với truy vấn đầu tiên, các dãy con không giảm là \(()\), \((2)\) và \((3)\). \((2,3)\) không phải một dãy con không giảm vì \(A_2\not\le A_3\).
Với truy vấn thứ hai, các dãy con không giảm là \(()\), \((4)\), \((5)\) và \((4,5)\).
Có \(N\) thế giới (\(2\le N\le 2\cdot 10^5\)), mỗi thế giới có một cổng dịch chuyển. Ban đầu, thế giới \(i\) (với \(1\le i\le N\)) có tọa độ \(x\) bằng \(i\) và tọa độ \(y\) bằng \(A_i\) (\(1\le A_i\le 10^9\)). Trên mỗi thế giới còn có một con bò. Tại thời điểm \(0\), tất cả các tọa độ \(y\) đều phân biệt và các thế giới bắt đầu rơi: thế giới \(i\) chuyển động liên tục theo chiều âm của trục \(y\) với vận tốc \(i\) đơn vị mỗi giây.
Tại bất kỳ thời điểm nào khi hai thế giới có cùng tọa độ \(y\) (thời điểm này có thể là một số không nguyên), các cổng dịch chuyển sẽ "thẳng hàng", nghĩa là một con bò trên một trong hai thế giới có thể chọn dịch chuyển tức thời sang thế giới còn lại.
Với mỗi \(i\), con bò trên thế giới \(i\) muốn đi đến thế giới \(Q_i\) (\(Q_i\neq i\)). Hãy giúp mỗi con bò xác định hành trình của mình sẽ mất bao lâu nếu nó di chuyển một cách tối ưu.
Mỗi đáp án truy vấn phải là một phân số \(a/b\), trong đó \(a\) và \(b\) là các số nguyên dương nguyên tố cùng nhau, hoặc là \(-1\) nếu hành trình không thể thực hiện được.
Dữ liệu vào được đọc từ tệp falling.in.
Dòng đầu tiên chứa một số nguyên \(N\).
Dòng tiếp theo chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\), cách nhau bởi dấu cách.
Dòng tiếp theo chứa \(N\) số nguyên \(Q_1,Q_2,\ldots,Q_N\), cách nhau bởi dấu cách.
Ghi ra tệp falling.out gồm \(N\) dòng; dòng thứ \(i\) chứa thời gian hành trình của con bò \(i\).
Ví dụ 1
4
3 5 10 2
3 3 2 17/2
7/2
5/1
-1Xét đáp án của con bò ban đầu ở thế giới \(2\). Tại thời điểm \(2\), thế giới \(1\) và thế giới \(2\) thẳng hàng, vì vậy con bò có thể dịch chuyển sang thế giới \(1\). Tại thời điểm \(\frac{7}{2}\), thế giới \(1\) và thế giới \(3\) thẳng hàng, vì vậy con bò có thể dịch chuyển sang thế giới \(3\).