首页 > 代码库 > From:hzwer.com(2014-5-17)

From:hzwer.com(2014-5-17)

2024-11-16 12:40:39   203人阅读

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

【题目描述】

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

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

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

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

以上3步骤为一次操作

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

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

【输入格式】

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

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

【输出格式】

一个整数表示操作数

【样例输入】

样例1：

3

RBR

样例2：

4

RBBR

【样例输出】

样例1：2

样例2：6

【数据范围】

50%的数据，1<=n<=20

100%的数据，1<=n<=50

 伪题解：

利用dp，找规律就可以水过了（博主用cena出错，就只用了样例与第十组数据比较，应该没问题，如果有，希望读者直接联系我）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 long long n,dp[50],sum=0;
 8 char a;
 9 int main()
10 {
11     dp[0]=1;
12     for(int i=1;i<50;i++)
13         dp[i]=2*dp[i-1]+1;
14     scanf("%lld",&n);
15     cin>>a;
16     if(a==‘B‘)
17         sum++;
18     for(int i=1;i<n;i++)
19     {
20         cin>>a;
21         if(a==‘B‘)
22         {
23             sum+=dp[i-1];
24             sum++;
25         }
26     }
27     cout<<sum;
28     return 0;
29 }

真题解（from:hzwer）

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

原来是找规律啊。。

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

模拟

 
 
 
 
 
 
C++
 
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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
int n,st[51],top;char a[51];
bool work()
{
     while(st[top]==1&&top>0)top--;
     if(top==0)return 0;
     if(st[top]==2)st[top]=1;
     for(int i=top+1;i<=n;i++)st[i]=2;
     return 1;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",a);
    for(int i=1;i<=n;i++)
       if(a[i-1]==‘R‘)st[n-i+1]=1;
       else st[n-i+1]=2;  
    for(int i=1;;i++)
        {top=n;if(!work()){printf("%d",i-1);break;}}
    return 0;
}

正解

 
 
 
 
 
 
C++
 
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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
int n,st[51];char a[51];
long long ans;
long long pow(int x)
{
     long long s=1;
     for(int i=1;i<x;i++)
         s*=2;
     return s;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",a);
    for(int i=1;i<=n;i++)
       if(a[i-1]==‘R‘)st[i]=1;
       else st[i]=2;  
    for(int i=1;i<=n;i++)if(st[i]==2)ans+=pow(i);
    printf("%lld",ans);
    return 0;
}

From:hzwer.com(2014-5-17)


联系
我们