codeforces-399B Red and Blue Balls

发表于 更新于 分类于 阅读次数：

描述

原题在这: https://codeforces.com/problemset/problem/399/B
给一个用字符串表示的栈, R表示红球, B表示蓝球. 按照以下规则按顺序操作(循环), 直到不含B:

  • 如果栈顶是R,持续pop
  • 如果栈顶是B, 替换成R
  • 如果栈不满, 补上B直到栈满

思路

乍一看是一道简单的implement的题, 于是单纯的implement一下, TLE.
观察(或者手算):

  • 最终状态必然是RRRRRR这种.
  • 如果当前栈顶连续的B只有一个, like RRRRRB, 那么本轮完成后是RRRRRR. 过渡到结束点用了1步.
  • 如果当前栈顶是两个连续的B, like RRRRBB, 那么状态会是RRRRBR -> RRRRRB -> (第一种情况). 过渡到第一种情况用了2步.
  • 如果当前栈顶是三个连续的B, like RRRBBB, 状态分别是RRRBBR -> RRRBRB -> RRRBRR -> RRRRBB -> (第二种情况). 过渡到第二种情况用了4步.
  • 归纳可知对于末尾连续n个B, 会给结果带来2^n - 1的贡献.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def do():
    n = int(input())
    stack = [s for s in input()][::-1]
    b = stack.count("B")
    res = 0
    while b > 0:
        while stack and stack[-1] == "R":
            stack.pop()
        stack[-1] = "R"
        b -= 1
        if len(stack) < n:
            res += (1 << (n - len(stack))) - 1
            stack += ["R"] * (n - len(stack))
        res += 1
    return res
print(do())