Nội dung Bài tập
- Mã:
- BRACKET
- Tên:
- Dãy ngoặc kì diệu
- Dạng thi:
- oi
- Thang điểm:
- 7 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- VNOI Online 2018
- Được tạo bởi:
- phuc
Xâu ký tự X gồm các kí tự " ( " và " ) " được coi là một dãy ngoặc đúng, khi và chỉ khi thỏa mãn một
trong ba điều kiện sau:
● X là dãy rỗng;● X = ( A ) , với A là dãy ngoặc đúng;● X = AB, với A và B là hai dãy ngoặc đúng.
Xét dãy ngoặc đúng X , kí tự đóng ngoặc ở vị trí j được gọi là tương ứng với kí tự mở ngoặc ở vị trí i,
khi và chỉ khi cả ba điều kiện sau được thỏa mãn:
● i < j ;● X [ i .. j ] là dãy ngoặc đúng;● i + 1 > j - 1 hoặc X [ i + 1 .. j - 1] là dãy ngoặc đúng.
Ở đây, kí hiệu X [ i .. j ] là xâu con bắt đầu ở vị trí i và kết thúc tại vị trí j của xâu X .
Có thể chứng minh rằng, trong dãy ngoặc đúng, mỗi mở ngoặc có một và chỉ một đóng ngoặc
tương ứng.
Xét dãy ngoặc ((()))() , ta dễ dàng nhận thấy điều sau:
Vị trí mở ngoặc Vị trí đóng ngoặc
Đếm số dãy ngoặc đúng độ dài n , thoả mãn m điều kiện. Điều kiện thứ i được cho bởi cặp số (xi, yi) với ý nghĩa là:
● Vị trí thứ xi của dãy ngoặc phải là mở ngoặc;● Vị trí thứ yi của dãy ngoặc phải là đóng ngoặc tương ứng của mở ngoặc ở vị trí xi
Dữ liệu:
- Dòng đầu tiên gồm hai số nguyên dương n và m (1 ≤ n, m ≤ 106 );
- m dòng sau, mỗi dòng gồm hai số nguyên dương x i và y i (1 ≤ x i ≤ y i ≤ n ).
Kết quả
● In ra phần dư khi chia số lượng dãy ngoặc thỏa mãn cho 109 +7.
Ví dụ 1:
BRACKET.INP BRACKET.OUT
Giải thích: Hai dãy ngoặc thỏa mãn đề bài là ()()(), ()(()) . Dãy ngoặc ((())) cũng là một dãy ngoặc đúng độ dài 6, nhưng không thỏa mãn đề bài vì đóng ngoặc tương ứng của mở ngoặc ở vị trí 1 nằm ở vị trí thứ 6.
Ví dụ 2:
BRACKET.INP BRACKET.OUT
Giải thích:Rõ ràng không có dãy ngoặc đúng nào độ dài lẻ.
Ví dụ 3:
BRACKET.INP BRACKET.OUT
Giải thích: Bốn dãy ngoặc thỏa mãn đề bài là (()())(()()) , (()())((())) , ((()))(()()) , ((()))((())) .
Chấm điểm
● Subtask 1 (20% số điểm): 1 ≤ n ≤ 20;● Subtask 2 (30% số điểm): 1 ≤ n ≤ 200;● Subtask 3 (30% số điểm): 1 ≤ n ≤ 5000;● Subtask 4 (20% số điểm): không có ràng buộc gì thêm.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...