Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3829 Known Notation

Chieh posted @ 2015年11月01日 18:27 in NO Answer No Speak , 367 阅读
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
char ch[maxn];
int len;
int ai[maxn];
int f;
void init()
{
    scanf("%s",ch+1);
    len=strlen(ch+1);
    f=0;
    for(int i=1; i<=len; i++)
    {
        if(ch[i]=='*')ai[i]=1;
        else ai[i]=0;
        f+=ai[i];
    }
}

void play()
{
    int f2=len-f;
    f2=f-f2;
    int ans=0;
    if(f2>=0)
    {
        ans=f2+1;
    }
    int before=ans;
    int st=len;
    for(int i=1; i<=len; i++)
    {
        if(ai[i]==1)
        {
            if(before<2)
            {
                while(ai[st]!=0)
                {
                    st--;

                }
                ai[st]=1;
                before++;
                ans++;
            }
            else
            {
                before--;
            }
        }
        else
        {
            before++;
        }
    }
    if(ai[len]!=1&&f!=0)ans++;
    printf("%d\n",ans);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter