SUMMAX - Tổng giá trị lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
3,00 (OI)
Giới hạn thời gian:
0.005s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Bạn được cho một xâu gồm ~N~ kí tự liền kề nhau. Mỗi kí tự có thể là kí tự a, b hoặc ?. Ta có thể thay thế những kí tự ? trong xâu ban đầu thành kí tự a hoặc kí tự b. Giả sử chúng ta đã thay thế hết các kí tự ?, thì với mỗi cặp hai kí tự liền kề trong xâu ban đầu.
Chúng ta định nghĩa giá trị của cặp đó như sau:
aa~= 0~ab~= 1~bb~= 0~ba~= -1~
Tổng giá trị của một xâu, là tổng giá trị của tất cả ~N − 1~ cặp hai kí tự liền kề.
Yêu cầu: 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 xâu ban đầu, bạn hãy in ra tổng giá trị lớn nhất có thể.
Input
- Dòng đầu tiên chứa một số nguyên ~N (1 \le N \le 10^6).~
- Dòng tiếp theo chứa một xâu gồm ~N~ kí tự, mỗi kí tự có thể là kí tự
a,bhoặc?.
Output
- Tổng giá trị lớn nhất có thể đạt được.
Sample
Input #1
5
aabbb
Output #1
1
Input #2
6
a?a?bb
Output #2
1
Hint
- Giải thích #1: ta có từng cặp xâu liên tiếp là
aa,ab,bb,bb, tổng giá trị của xâu là ~0 + 1 + 0 + 0 = 1~. - Giải thích #2: ta có thể thay thế các kí tự
?thành xâuababbb. Những cặp xâu liên tiếp làab,ba,ab,bb,bb, tổng giá trị của xâu là ~1 + (-1) + 1 + 0 + 0 = 1~.
Bình luận
chào bạn.Đây là ý tưởng : nếu s[0]=='?' thì s[0]='a' và nếu s[n-1]=='?' thì s[n-1]='b'
quả nhiên top 1 đúng là không hề tầm thường =)) tại hạ bái phục
ý gì đây
tôi rất muốn được học hỏi bạn
cx đc nhưng nói trc tui code theo cảm tính th đó.Lâu ngày chx động vào code cx quên kha khá
Ai đó có thể nêu ý tưởng đc không ạ. Bài này có thể code theo cách nào khác ngoài code trâu O(n) không ạ.
a dùng gợi ý của Đăng xong tạo xâu S là a[0] với a[n-1] xong in ra kq theo đề luôn :))
là sao vậy anh em không hiểu lắm :)