天天看點

思維題——方塊 I思維題——方塊 I

題目連結

思維題——方塊 I

題目描述

有 N 個方塊排成一排,每個方塊都染有顔色,第 i 個的顔色為 Ci,一共有三種顔色,分别為紅,黃,藍,現在你可以對相鄰的顔色不同的方塊進行施法,使其變成第三種顔色,比如對相鄰的紅方塊和黃方塊進行施法,就會使其合并為藍方塊。施法順序的不同,可能對最終的結果産生不同的影響,問在最優政策下,最少能剩下多少個方塊。

輸入描述

T 組資料。

每組資料一行,将方塊序列用字元串形式給出,a,b,c 表示三種不同顔色的方塊。

T <= 10

1 <= N <= 500

輸出描述

每組資料一個整數,表示答案。

示例

輸入

abc

輸出

2

分析

可以将 a,b,c 分别用 1,2,3 表示,先判斷 n 個數是否相同,若都相同,則輸出 n,不然的話,就判斷這 n 個數的異或後所得到的值是否為 0,若為 0,則輸出 2,反之,輸出 1。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	while(cin>>s){
		int ans=0;
		int sum=0;
		int n=s.length();
		for(int i=0;i<n;i++){
			ans^=(s[i]-'a'+1);
			sum+=(s[i]-'a'+1);
		}
		if(sum==(s[0]-'a'+1)*n){
			cout<<n<<endl;
		}
		else{
			if(ans==0){
				cout<<2<<endl;
			}
			else{
				cout<<1<<endl;
			}
		}
	}
	return 0;
}
           

繼續閱讀