模拟(手玩)一下

题目要求在一组中只能出现一个G或者是一个H,我们这边以出现一个H为例，(G同理)

• 首先第一步记录所有H的下标，为了满足题目条件所选区间中一定不会包含两个及以上H,所以每次可选的最大区间可以确定

接着计算当前位置左边最多能选多少个，以及右边能选多少个，分别用 l和r表示，对于当前H可选的方案可以分为三种

1. 只在H的左半边

   • 当$l < 2$时方案为零
   • 当$l >= 2$时方案为 $l - 1$

2. 只在H的右半边

   • 当$ r < 2$时方案为零
   • 当$ r >= 2$时方案为 $r - 1$

3. 在H两边

   • 左边选一个对应右边有r种选法，左边选两个对应右边也有r种选法.....

   故左右两边都有G的方案数为: $l * r$

TIPS: 为了方便处理左右边界 我们初始化左边界为 -1 右边界为字符串长度 n 这样在计算左右两边时候就不用特殊判断了

python3 代码

n = int(input())
s = input()
g, h = [-1], [-1] # 初始化左端点为-1
for i, val in enumerate(s):
    if val == 'G':
        g.append(i)
    else:
        h.append(i)
g.append(n) # 右端点为n 
h.append(n)
# 初始化完左右端点这样可以不用考虑边界情况了
res = 0
gn, hn = len(g), len(h)
for i in range(1, gn - 1): # 枚举时左右边界不需要枚举
    l, r = g[i] - g[i - 1] - 1, g[i + 1] - g[i] - 1
    if l >= 2:
        res += l - 1
    if r >= 2:
        res += r - 1 
    res += l * r
for i in range(1, hn - 1):
    l, r = h[i] - h[i - 1] - 1, h[i + 1] - h[i] - 1
    if l >= 2:
        res += l - 1
    if r >= 2:
        res += r - 1 
    res += l * r
print(res)