Đề ôn tập môn Tin học THCS - Đề số 49 - Năm học 2024-2025

Nội dung tài liệu: Đề ôn tập môn Tin học THCS - Đề số 49 - Năm học 2024-2025

1. DÃY NGOẶC ĐÚNG 2 Description Một dãy ngoặc đúng được định nghĩa như sau: • Xâu rỗng là 1 dãy ngoặc đúng. • Nếu A là 1 dãy ngoặc đúng thì (A) là 1 dãy ngoặc đúng. • Nếu A và B là dãy ngoặc đúng thì AB là 1 dãy ngoặc đúng. Cho dãy ngoặc S độ dài N và Q truy vấn có 2 dạng: 1 i c: Gán S[i] = c, trong đó c = ′(′ hoặc ′)′. 2 i j: Kiểm tra dãy ngoặc con S[i..j] có là dãy ngoặc đúng hay không ? Input Dòng đầu tiên chứa 2 số nguyên dương N và Q(1≤N,Q≤105). Dòng thứ hai chứa dãy ngoặc S. Trong Q dòng tiếp theo, mỗi dòng chứa một truy vấn. Output Với mỗi truy vấn dạng 2, in trên một dòng YES nếu đúng, ngược lại in NO. Sample Input 1 7 4 ()())() 2 3 4 2 1 5 1 2 ( 2 2 7 Sample Output 1 YES NO YES
2. Dãy ngoặc đúng Description Một dãy ngoặc đúng được định nghĩa như sau: • Xâu rỗng là 1 dãy ngoặc đúng. • Nếu A là 1 dãy ngoặc đúng thì (A) là 1 dãy ngoặc đúng. • Nếu A và B là dãy ngoặc đúng thì AB là 1 dãy ngoặc đúng. Cho dãy ngoặc S độ dài N và Q truy vấn biểu diễn bởi 2 số nguyên l và r (1≤l≤r≤N): Kiểm tra dãy ngoặc con S[l..r] có là dãy ngoặc đúng hay không ? Input Dòng đầu tiên chứa 2 số nguyên dương N và Q (1≤N,Q≤105). Dòng thứ hai chứa dãy ngoặc S. Trong Q dòng tiếp theo, mỗi dòng chứa một truy vấn. Output Với mỗi truy vấn, in trên một dòng YES nếu đúng, ngược lại in NO. Sample Input 1 7 3 ((())() 3 4 1 5 2 7 Sample Output 1 YES NO YES
3. ĐỔI CHỖ Description Cho một dãy số gồm N phần tử và có Q truy vấn. Mỗi truy vấn là một trong hai yêu cầu sau: Đổi chỗ hai phần tử ở vị trí u,v trong dãy hiện tại hoặc tính tổng của một đoạn trong dãy. Bạn hãy thực hiện Q truy vấn đó. Input Dòng đầu gồm hai số nguyên dương N và Q Dòng thứ hai gồm N số nguyên là các phần tử của dãy. QQ dòng tiếp theo, mỗi dòng gồm ba số k,u,v biểu diễn một truy vấn, k=0 là đổi vị trí, k=1 là loại còn lại, u≤v Output Với mỗi truy vấn k=1 in ra câu trả lời. Sample Input 1 5 3 1 2 3 4 5 1 2 4 0 1 3 1 2 4 Sample Output 1 9 7 Hint Substask 1: 50 \%50% số điểm có 1 \le N, Q \le 10^31≤N,Q≤103 Substask 2: 50 \%50% số điểm còn lại có N, Q \le 10^5N,Q≤105
4. Các phần tử trong dãy có giá trị tuyệt đối không quá 10^7107 Đua xe Description Vùng đất CVP rộng lớn tổ chức một giải đua xe mở rộng. Có N thí sinh tham gia, các thí sinh được đánh số từ 1 đến N. Sau nhiều vòng đua gay cấn, vòng đua cuối cùng cũng tới. Nhà vô địch sẽ là người có tổng số điềm sau các vòng đua cao nhất. Cách tính điểm của mỗi vòng đua như sau: người về đầu tiên nhận được N điểm, người về nhì được N−1 điểm, , cho đến người cuối cùng nhận được 1 điểm. Như mọi tay đua khác tham gia kì thi,Trúc Xinh Gáimuốn biết xem bao nhiêu người có khả năng dành chiến thắng trong vòng đua cuối cùng. Là một lập trình viên, bạn hãy giúpTrúc Xinh Gái trả lời câu hỏi này nhé! Biết rằng sau vòng đua cuối cùng, nếu hai tay đua bằng điểm nhau thì cả hai người đều giành chức vô định và không có hai tay đua nào đến đích cùng một lúc. Input • Dòng đầu tiên chứa số nguyên dương N (1 ≤ N≤ 300000). •NNdòng tiếp theo, mỗi dòng gồm một số nguyên Pi (0≤Pi≤2000000)- là tổng điểm của tay đua i trong các vòng đua trước đó. Output Gồm một số nguyên duy nhất là số người có khả năng thắng chung cuộc. Sample Input 1 3 8 10 9 Sample Output 1 3