双色球 (ball. cpp/c/pas)

题目描述

机房来了新一届的学弟学妹, 邪恶的 chenzeyu97 发现一位学弟与他同名, 于是他当起了善良 的学长 233

来来来, 学弟, 我考你道水题检验一下你的水平……

一个栈内初始有 n 个红色和蓝色的小球, 请你按照以下规则进行操作

  1. 只要栈顶的小球是红色的, 将其取出, 直到栈顶的球是蓝色
  2. 然后将栈顶的蓝球变成红色
  3. 最后放入若干个蓝球直到栈中的球数为 n

以上 3 步骤为一次操作

如栈中都是红色球, 则操作停止, 请问几次操作后停止

chenzeyu97 出完题发现他自己不能 AC 所以想请你帮忙

输入格式

第一行为一个整数 n, 表示栈的容量为 n

第二行为一个字符串, 第 i 个字符表示自顶向下的第 i 个球的颜色, R 代表红色, B 代表蓝色

输出格式

一个整数表示操作数

样例输入

4
RBBR

样例输出

6

样例解释

数据范围

50% 的数据,\(1 \leq n \leq 20\)

100% 的数据,\(1 \leq n \leq 50\)

Explanation

简单看一下就发现其实把蓝球当成 0, 红球当成 1, 然后当成二进制加法就可以了.

时间复杂度是一个玄学 \(O(1)\) (为什么题解里不是这样的呢?)

所以我还是放一个官方题解比较靠谱一点~

看完就开始打模拟, 数据范围这么小是吧...... 然后果断 T 了

原来是找规律啊......

把第 n 个蓝球变成红球要 2^n 次操作...... 然后累加起来, 开个 longlong

模拟

再看一遍官方题解以后才发现其实两个说的是一件事~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

char str[64];
int n;
lli res = 0;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        char c = getchar();
        while (c != 'R' && c != 'B')
            c = getchar();
        str[i] = c;
    }
    for (int i = 1; i <= n; i++)
        if (str[i] == 'B')
            res += 1ll << lli(i - 1);
    printf("%lld\n", res);
    return 0;
}