題目連結
思維題——方塊 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;
}