题目链接

思维题——方块 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; }