#MX154. 果园争锋

果园争锋

题目描述

两名果农在一条果园带上竞争。果园带上 nn 棵果树排成一排,每棵树状态为未成熟(标记为 00)或成熟(标记为 11)。两人轮流行动,果农 11 先开始。

每回合行动规则:

  • 果农 11:必须选择两棵相邻且均未成熟的果树(0000),将其移出果园。
  • 果农 22:必须选择两棵相邻果树中至少一棵已成熟的果树(0101、1010 或 1111),将其移出果园。

若某个果农无法按规则行动(包括剩余果树少于 2 棵),则认定该果农败北。

任务:

给定果园初始状态序列 ss(例如 "01100110"),请计算所有连续果树段(子串)中,果农 11 在双方最优策略下必胜的片段数量。

输入格式

第一行输入一个整数 nn 代表果树数量。

第二行输入一个长度为 nn 的字符串 ss 代表果树是否成熟。每一个字符都是 00 或者 11。

输出格式

输出一个整数,代表能让果农 11 获得胜利的连续果树段数量。

样例 1 输入

10
0010010011

样例 1 输出

12

样例解释

在样例 11 里面,以下的果树段能让玩家 11 获胜。(s[l,r]s[l, r] 代表 slsl+1…srs_ls_{l + 1}\ldots s_r):s[1,2]s[1, 2], s[1,3]s[1, 3], s[1,7]s[1, 7], s[2,4]s[2, 4], s[2,8]s[2, 8], s[3,5]s[3, 5], s[4,5]s[4, 5], s[4,6]s[4, 6], s[5,7]s[5, 7], s[6,8]s[6, 8], s[7,8]s[7, 8], s[7,9]s[7, 9]。

数据规模与约定

  • 对于 10%10\% 的数据,n≤10n \le 10。
  • 对于 50%50\% 的数据,n≤103n \le 10^3。
  • 对于 100%100\% 的数据,n≤3×105n \le 3 \times 10^5。