d336 - 一即是全、全即是一

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個由 0 和 1 組成的二進位字串，要求判斷這個字串所代表的數值是否能被 3 整除。有多組測試資料。

解題思路

題目要求判斷二進位字串轉換為十進位數後是否能被 3 整除。直接轉換成十進位數再判斷可能會導致數值過大，造成溢位或效率低下。 觀察到，一個數能被 3 整除，等價於其各位數字的和能被 3 整除。對於二進位數，可以將其視為各位權重為 2 的冪次的數字之和。 更進一步，可以利用同餘的性質，2 ≡ -1 (mod 3)，因此二進位數的值可以表示為各位數字乘以 (-1) 的冪次的和。 然而，題目提示避免使用模運算，因此可以採用貪心策略，直接計算二進位字串中 '1' 的位置所貢獻的數值。 具體來說，如果遇到一個 '1'，則將 sum 加 1；如果相鄰兩個 '1' 出現，則將 sum 加 2。 這樣，sum 的值就代表了二進位數除以 3 的餘數。

複雜度分析

• 時間複雜度: O(n)，其中 n 是二進位字串的長度。需要遍歷字串一次。
• 空間複雜度: O(1)，只需要常數級別的額外空間。

程式碼

#include<stdio.h>
#include<string.h>
int main(){
	char in[9001]={0};
	int t=0,i=0,j=0,sum=0,len;
	scanf("%d",&t);
	for(i=0;i<t;i++){
		scanf("%s",in);
		len=strlen(in);
		for(j=0;j<len;j++){
			if(in[j]=='1')
				sum++;
			j++;
			if(in[j]=='1')
				sum+=2;
		}
		puts((sum%3==0)?"Yes\n":"No\n");
		sum=0;
	}
	return 0;
}