【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e639
【解題想法】前綴和
- pre[i]：紀錄到第 i 個字符(含)時，累計遇到幾個 ‘1’。
- 【例】s = “000111001011”
- pre[ ] = {0, 0, 0, 1, 2, 3, 3, 3, 4, 4, 5, 6}
- (i, j) = (3, 5)：pre[3] = 1, pre[5] = 3 -> 區間內的字符均為 ‘1’
- (i, j) = (6, 7)：pre[6] = 3, pre[7] = 3 -> 區間內的字符均為 ‘0’
#include <iostream>
#include <cstring>
using namespace std;
int pre[1000005];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, i, j, Case = 1;
string s;
while ((cin >> s) && (s != "")){
memset(pre, 0, sizeof(pre));
pre[0] = (s[0] == '1');
for (i = 1; i < s.size(); i++){
pre[i] = pre[i-1] + (s[i] == '1');
}
cout << "Case " << Case++ << ":\n";
cin >> n;
while (n--){
cin >> i >> j;
if (i > j) swap(i, j);
if (pre[i] == pre[j] || pre[j] - pre[i] == j - i){
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
return 0;
}