Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/17
20:02
杂题

[bzoj 4893] 项链分赃

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有一串长度为n的项链,上面有红绿蓝三种颜色的珠子,每种颜色的珠子数目都是偶数,现在要你把它切几刀分成若干段,把其中一些段分给海盗1,剩余的段分给海盗2,要求两个海盗分得的每种颜色的珠子数量都相同,请输出最少需要切多少刀。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个整数n,表示项链的长度。
第二行n个0~2的整数,分别表示红绿蓝三种颜色。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一行一个整数,为最少切多少刀。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6
0 2 2 1 0 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2
样例解释:切两刀,分成{0,2},{2,1,0},{1}三份,第二份给海盗1,剩下给海盗2即可。

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

n<=100000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

有一个非常妙的结论是切割的刀数不会超过颜色数

证明:http://www.cnblogs.com/juruolty/p/6806029.html

于是判掉1和2的情况,不行就输出3

 

[bzoj 4893] 项链分赃