「ditoly 暑假模拟赛」玩球 - 数学

发表于 | 更新于 | 分类于 | 评论数：

小 D 有一个栈，栈里一开始有 nn 个球，每个球是蓝色或红色。

小 D 打算用一种操作来玩这些球，每次操作他先从栈顶开始取球，如果取出的球是红色他就继续取，直到取到一个蓝球。接下来，他用神秘力量把取出的球红蓝颜色互换，再按原来的顺序塞回栈里。我们用 R 代表红色，B 代表蓝色，那么栈中从顶到底的颜色序列为 RRBB 时，进行一次操作，会变成 BBRB。

当栈中的球均为红色时，小 D 就玩不了了，小 D 想知道自己最多能进行多少次操作，如果能操作的次数超过 101810^{18}，小 D 也懒得玩了，你只要输出 −1-1 就好了。

链接

FZOJ #10001

题解

用 00 代表 R，11 代表 B，把状态表示成一个二进制数。因为栈是后进先出的，所以需要将这个二进制数反转。这样每一次操作可以看作将这个二进制数减 11，将这个二进制数转换成十进制数就是答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <string>
#include <algorithm>

char fafachar() {
    char c;
    while (!isgraph(c = getchar()));2

    return c;
}

int main() {
    int n;
    scanf("%d", &n);

    std::string s;
    for (int i = 1; i <= n; ++i) {
        s += "01"[fafachar() == 'B'];
    }

    std::reverse(s.begin(), s.end());

    printf("%llu\n", std::stoull(s, 0, 2));
}