e639 - 10324 - Zeros and Ones

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個二進位字串和多個查詢，每個查詢包含兩個索引 i 和 j。對於每個查詢，需要判斷字串中從索引 min(i, j) 到 max(i, j) (包含兩端) 的所有字元是否都相同。

解題思路

解題思路是針對每個查詢，提取字串中指定範圍內的子字串，然後檢查該子字串中的所有字元是否都相同。首先，確保 x 小於等於 y，如果不是，則交換它們。然後，獲取起始位置 x 處的字元值 ans。接著，迭代從 x 到 y 的範圍，如果遇到與 ans 不同的字元，則設置一個標誌 flag 為 1，表示範圍內存在不同的字元。最後，根據 flag 的值輸出 "Yes" 或 "No"。

複雜度分析

• 時間複雜度: O(n*m)，其中 n 是查詢的數量，m 是字串的長度。在最壞情況下，對於每個查詢，我們可能需要遍歷字串中 x 到 y 範圍內的字元。
• 空間複雜度: O(1)，因為我們只使用了幾個整數變數和一個布林變數來存儲中間結果，空間使用量不隨輸入大小變化。

程式碼

#include <iostream>
using namespace std;
int main(){
	int n,x,y,c=0;
	string a;
	while(cin >> a){
		cout << "Case " << ++c << ":\n";
		cin >> n;
		while(n--){
			cin >> x >> y;
			if(x>y){
				x^=y;
				y^=x;
				x^=y;
			}
			bool ans=a[x]-'0',flag=0;
			for(int i=x;i<=y;++i)
				if(a[i]-'0'!=ans){
					flag=1;
					break;
				}
			(flag)?cout << "No\n":cout << "Yes\n";
		}
	}
}