【牛客网】2017年浙江工业大学大学生程序设计迎新赛热身赛 F题 方块 I
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
有 N 个方块排成一排，每个方块都染有颜色，第 i 个的颜色为 Ci，一共有三种颜色，分别为红，黄，蓝，现在你可以对相邻的颜色不同的方块进行施法，使其变成第三种颜色，比如对相邻的红方块和黄方块进行施法，就会使其合并为蓝方块。施法顺序的不同，可能对最终的结果产生不同的影响，问在最优策略下，最少能剩下多少个方块。
输入描述:
T组数据。
每组数据一行，将方块序列用字符串形式给出，a，b，c表示三种不同颜色的方块。
T <= 10
1 <= N <= 5000
输出描述:
每组数据一个整数，表示答案。
引言：这个题在群里看到有人问，就思考了一下。虽做法简单，证法却不失趣味性，索性久违的写个题解吧~
假设方块段长度
如果含多种颜色，可以通过消除一种颜色变成01字符串（ex：0000011110011000）的形式。
我们总可以令01串的的开头是0，并先假设01串段数至少为3，段数为2特殊处理。
主方法：取从左往右第一个1往左一直合并，根据0的个数会变成1或者2（被消除的第三种颜色）。接下来分两种情况：
1. 如果变成1，就相当于最开始的0段被消除，1段增加了一个，成了递归形式，把01串01翻转就可以了。
2. 如果变成2，则串形式变成”21111000……”，接下来用2向右合并，合并掉右边的1段后，01串又有两种分歧：
2.1 “2000……”，此时只要01翻转就是情况2的递归形式。
2.2 “0000……”，此时串为原始形态的递归形式。
当递归到最后除开头可能有的2以外，01串仅剩两段时（ex：00001111），需要特别处理。根据开头有无2、0个数奇偶，分四种情况。
开头无2，0个数为奇（ex：000001111）：采用主方法，用右边第一个1向左合并，串变为2111形式，再用2向右合并，最后一定剩一个，至于是0还是2，看1的个数吧。
开头无2，0个数为偶（ex：00001111）：直接合并掉最左边的所有0，会变成1111，肯定不能这么做。解决方法是先隔离最左边的0，当做情况【开头无2，0个数为奇】处理，然后再尝试用处理后结果尝试和0合并。如果1个数为奇则最后可以合并为1，否则剩两个0。
开头有2，0个数为奇（ex：20001111）：向右合并到剩一个0，变成”201111”，接下来用0向右合并，最后尝试和开头的2合并。1个数为奇则剩两个2，1个数为偶剩一个1。
开头有2，0个数为偶（ex：200001111）：不多说，2一直向右合并即可。1个数为偶剩一个2，1个数为奇剩一个0。
得证：非纯色方块段，最后必可合并成2个或者1个方块。
注意，接下来才是本题的解法！
根据上面的证明可知非纯色方块段最后一定可以剩2个或1个方块，那2个能否合并成一个？
引入一个概念：三种颜色分别用0，1，2表示。题意所示合并方式即01合并等于2，02合并等于1，12合并等于0。该合并方式可以用公式表示：
0^1^3=2
0^2^3=1
1^2^3=0
可以很容易找到规律，两颜色合并变成第三种颜色，即代表的数字
该规律有什么用？
只要出现合并就会异或上一个3，一个长度为
由于一开始我们证明了非纯色方块段必能合并成剩1或2个方块。那最后2个方块能否合并成1个方块，只要看n个数
最终解法异常简单：三种颜色分别用0，1，2表示，然后先判断
PS：如果有更加简单巧妙的证明，可以留言~
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 5005 ;
char s[MAXN] ;
void solve () {
int n = strlen ( s ) ;
char c = s[0] ;
int ans = n % 2 ? 0 : 3 , cnt = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
ans ^= s[i] - 'a' ;
if ( s[i] == c ) ++ cnt ;
}
if ( cnt == n ) printf ( "%d\n" , n ) ;
else printf ( "%d\n" , ans == 3 ? 2 : 1 ) ;
}
int main () {
while ( ~scanf ( "%s" , s ) ) solve () ;
}