2014
04-04

# Necklace

1.  Choose an arbitrary position to cut it into a chain.
2.  Choose either direction to collect it.
3.  Collect all the beads in the chosen direction under the constraint that the number of crystal beads in your hand is not less than the jade at any time.
Calculate the number of ways to cut meeting the constraint

In the first line there is an integer T, indicates the number of test cases. (T<=50)
Then T lines follow, each line describes a necklace. ‘C’ stands for a crystal bead and ‘J’ stands for a jade bead. The length of necklace is between 2 and 10^6.

In the first line there is an integer T, indicates the number of test cases. (T<=50)
Then T lines follow, each line describes a necklace. ‘C’ stands for a crystal bead and ‘J’ stands for a jade bead. The length of necklace is between 2 and 10^6.

2
CJCJCJ
CCJJCCJJCCJJCCJJ

Case 1: 6
Case 2: 8

 Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 4390122 2011-08-11 20:28:07 Accepted 3474 453MS 28592K 1947 B C++ xym2010

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000005;
struct queuey
{
int flag,key;
}q[maxn*2];
int r,f;
void insert(int flag,int key)
{
while(r>f&&key<q[r].key)
r--;
q[++r].flag=flag;
q[r].key=key;
}
void init()
{
r=f=0;
}
char s[2*maxn],ss[2*maxn];
bool vd[2*maxn];
int sum[2*maxn];
int main()
{
int c,len,count=0,d=0;
scanf("%d",&c);
while(c--)
{
d++;
scanf("%s",s);
len=strlen(s);
for(int i=0;i<len;i++)
ss[i]=s[i];
for(int i=0;i<len;i++)
ss[len+i]=s[i];
sum[0]=ss[0]=='C'?1:-1;
init();
for(int i=1;i<2*len;i++)
sum[i]=sum[i-1]+(ss[i]=='C'?1:-1);
count=0;
memset(vd,0,sizeof(vd));
for(int i=0;i<2*len;i++)
{
insert(i,sum[i]);
while(q[f+1].flag<=i-len&&r>f)
f++;
if(i-len>=0)
{
if(q[f+1].key>=sum[i-len])
if(vd[i]==0)
{
count++;
vd[i]=1;
}
}
}
init();
sum[2*len]=0;
sum[2*len-1]=ss[2*len-1]=='C'?1:-1;
for(int i=2*len-2;i>=0;i--)
{
sum[i]=sum[i+1]+(ss[i]=='C'?1:-1);
}
for(int i=2*len;i>0;i--)
{
insert(i,sum[i]);
while(q[f+1].flag>=i+len&&r>f)
f++;
if(i<=len)
{
if(q[f+1].key>=sum[i+len])
if(vd[i+len-1]==0)
{
count++;
vd[i+len-1]=1;
}
}
}
printf("Case %d: %d\n",d,count);
}
}