Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#1486 · Chuỗi lớn nhất

MÔ TẢ BÀI TOÁN

Avatar
Đề tạo bởi
GV. Bùi Phú Khuyên

Chuỗi (strings) là một phần quan trọng trong lập trình và xử lý dữ liệu áp dụng trong nhiều lĩnh vực khác nhau.

Cho một chuỗi là tập hợp mảng 1 chiều các ký tự gồm N phần tử. Mỗi ký tự có thể là a, b hoặc ?. Bạn có quyền thay thế tất cả các ký tự ? trong chuỗi ban đầu thành a hoặc b. Sau khi thay thế hết các ký tự ?, chúng ta định nghĩa giá trị của từng cặp hai ký tự liền kề như sau:

  • aa = 0
  • ab = 1
  • bb = 0
  • ba = -1

Tổng giá trị của một chuỗi, là tổng giá trị của tất cả n - 1 cặp hai ký tự liền kề.

Bài toán đặt ra cho bạn là trong tất cả các cách thay thế những ký tự ? trong chuỗi ban đầu, bạn hãy in ra tổng giá trị lớn nhất có thể.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 10^6).
  • Dòng tiếp theo chứa một chuỗi gồm N ký tự, mỗi ký tự có thể là ký tự a, b hoặc ?.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể trong tất cả các cách thay thế.

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
Nguyễn Tri Bão Thắng @25807700104
7 ms 2264 KB
1304 Bytes
23/12/2025
15:33
2
T
Nguyễn Tri Bão Thắng @2180601452
8 ms 2232 KB
1405 Bytes
19/11/2023
19:08
3
GV. Bùi Phú Khuyên @KBP0100298
9 ms 2240 KB
311 Bytes
17/11/2023
11:51
4
T
Nguyễn Tri Bão Thắng @2180601452
9 ms 2240 KB
1405 Bytes
18/11/2023
19:43
5
Lê Duy Hải @2280600799
12 ms 1184 KB
297 Bytes
30/01/2024
08:37
6
T
Nguyễn Tiến Thịnh @2380602132
14 ms 1168 KB
506 Bytes
20/11/2023
16:31
7
T
Nguyễn Thăng Tiến @2180608641
16 ms 2236 KB
776 Bytes
20/11/2023
22:58
8
T
Nguyễn Thăng Tiến @2180608641
16 ms 2248 KB
663 Bytes
20/11/2023
23:20
9
T
Bùi Thị Hoài Thương @2380602204
17 ms 1164 KB
375 Bytes
18/11/2023
21:05
10
K
Trần Liêu Huy Khánh @2180607632
17 ms 2240 KB
466 Bytes
18/11/2023
19:52
11
T
Nguyễn Tiến Thịnh @2380602132
18 ms 1172 KB
506 Bytes
20/11/2023
16:30
12
L
Phạm Khắc Duy Long @2280610603
18 ms 2232 KB
639 Bytes
18/11/2023
21:39
13
T
Nguyễn Thăng Tiến @2180608641
18 ms 2236 KB
776 Bytes
20/11/2023
23:00
14
T
Nguyễn Thăng Tiến @2180608641
18 ms 2236 KB
776 Bytes
20/11/2023
23:01
15
T
Nguyễn Tiến Thịnh @2380602132
19 ms 1164 KB
506 Bytes
20/11/2023
16:31
16
H
Nguyễn Viết Hiến @2280600923
20 ms 1276 KB
1368 Bytes
21/07/2025
09:10
17
T
Nguyễn Tiến Thịnh @2380602132
21 ms 1164 KB
572 Bytes
20/11/2023
16:28
18
K
Hồ Nguyễn Đăng Khôi @2280601558
21 ms 1172 KB
695 Bytes
18/11/2023
21:52
19
X
Lê Dương Định Xuân @2280618826
21 ms 2236 KB
3238 Bytes
19/11/2023
23:14
20
B
Nguyễn Hữu Ngự Bình @2280600266
22 ms 6152 KB
668 Bytes
28/04/2024
17:16

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

  • Ở test ví dụ 1, ta có từng cặp chuỗi liên tiếp là aa, ab, bb, bb, tổng giá trị của chuỗi là 0 + 1 + 0 + 0 = 1
  • Ở test ví dụ 2, ta có thể thay thế các kí tự ? thành chuỗi ababbb. Những cặp chuỗi liên tiếp là ab, ba, ab, bb, bb, tổng giá trị của chuỗi là 1 + (-1) + 1 + 0 + 0 = 1.
  • Ở test ví dụ 3, ta có thể thay thế thành chuỗi bbbbb, tổng giá trị của chuỗi là 0.
Viết code