Cho xâu ký tự S chỉ bao gồm các ký tự ‘0’ và ‘1’. Nhiệm vụ của bạn là loại bỏ các xâu con “100” trong S và đưa ra độ dài lớn nhất xâu con bị loại bỏ. Ví dụ S =” 1011110000” ta nhận được kết quả là 6 vì ta cần loại bỏ xâu “110000” có độ dài 6.
Input:
- Dòng đầu tiên đưa vào số lượng bộ test T.
- Những dòng kế tiếp đưa vào T bộ test. Mỗi bộ test là một xâu ký tự nhị phân S được viết trên một dòng.
- T, S thỏa mãn ràng buộc: 1≤ T ≤100; 1≤ Length(S)≤10^5.
bài này em tham khảo, và dùng vector để đẩy cặp <ký tự, index> trong chuỗi ban đầu,
gặp 100 thì pop, rồi cập nhật MAX bằng khoảng cách giữa index
với đề này 2 code trình bày khác nhau nhưng sao em nộp trên web trường 1 bài chấp nhận 1 bài báo sai output , anh chị giúp em với
#include <bits/stdc++.h>
using namespace std;
int t;
void process(){
string str;
cin>>str;
vector<pair<char, int>>a;
a.push_back({'2',-1});
int m=0;
for(int u=0; u < str.size(); ++u){
a.push_back({str[u],u});
while(a.size()>=3 && a[a.size()-3].first=='1' && a[a.size()-2].first=='0' && a[a.size()-1].first=='0'){
for(int i=0; i<3; ++i) a.pop_back();
}
m=max(m,u-a.back().second);
}
cout<<m<<endl;
}
int main(){
cin>>t;
while(t--){
process();
}
}
với code khác nhưng cùng hướng giải.
#include <bits/stdc++.h>
using namespace std;
int longest(string str)
{
vector<pair<char,int> > arr;
arr.push_back({'@', -1});
int maxlen = 0;
for (int i = 0; i < str.length(); ++i)
{
arr.push_back({str[i], i});
while (arr.size()>=3 &&
arr[arr.size()-3].first=='1' &&
arr[arr.size()-2].first=='0' &&
arr[arr.size()-1].first=='0')
{
arr.pop_back();
arr.pop_back();
arr.pop_back();
}
int tmp = arr.back().second;
maxlen = max(maxlen, i - tmp);
}
return maxlen;
}
int main() {
int test;
cin>>test;
while(test--) {
string s;
cin>>s;
cout<<longest(s)<<"\n";
}
return 0;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?