B. Red and Blue Balls
这道题是Codeforces Round #233 (Div. 2)的B题,觉得在思维方面的考察挺不错的。
初看我以为是考栈,结果刚跟小伙伴学长一讲,他就说不行,用栈绝对过不了= =
但是最近正好在看栈 ,所以很想拿这道题来练练用栈的能力。后面在龙酱和小伙伴的帮助下,总算写了粗来,不过只能过掉样例,但是对我来说也挺有意义的~
用栈的方法如下:
#include <iostream> //龙酱友情提供
#include <stack>
using namespace std;
int n;
char a[10005];
int main()
{
//freopen("b.txt", "r", stdin);
while (cin >> n)
{
long long ope = 0;
stack<char> ball;
int i;
char btmp;
while(!ball.empty()) //清空栈
ball.pop();
for (i = 1; i <= n; i++) //接收字符串
cin >> a[i];
for(int i = n; i >= 1; i --)
ball.push(a[i]);
while (1)
{
while (!ball.empty()) //弹出红球直到遇到蓝球
{
if( ball.top() == 'B' )
break;
ball.pop();
}
if (ball.empty()) //栈空说明无蓝球,操作完成
break;
ball.pop();
ball.push('R'); //将蓝球涂成红色,注意,这一步既是步骤一的一部分,也是步骤二;
while (ball.size() < n)
ball.push('B'); //装满蓝球直至栈满
ope += 1;
}
cout << ope << endl;
}
return 0;
}
但是用 栈 做是会超时的。
我是这样理解的,把一个蓝球变为红球及其所有过程为一个步骤。
可以自己模拟一下:
input:
3
BBB
那么则是:
BBB
1 BBR
BB
2 BR
BRB
3 BRR
B
4 R
RBB
5 RBR
RB
6 RR
RRB
7 RRR
把第i个蓝球变成红色(从左往右数),需要2^(i-1)次步骤。
这就不难理解为何会超时了(必有样例,n是会接近50的!!)。
龙酱在群里说,用二进制。但是当时自己没模拟,根本不理解跟二进制有毛关系啊!
后面模拟了一遍就知道这个题应该用二进制。
但是改用二进制来做后又想的简单了,long long类型的数据我直接用了 << 1 来代替乘 2,没想到长整形的数据不能这样做,会溢出,果然在样例10就wa了。
下面是ac代码:
#include <stdio.h>
int n;
int main()
{
//freopen("b.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
{
int i, j;
char ball[54];
long long unsigned ope = 0;
long long unsigned tmp;
scanf("%s", ball);
for (i = 0; i < n; i++)
{
tmp = 1;
if ('B' == ball[i])
{
for (j = 0; j < i; j++)
tmp *= 2;
ope += tmp;
}
}
printf("%I64u\n", ope);
}
return 0;
}