Necklace
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1566 Accepted Submission(s): 455
Problem Description
You are given a necklace consists of N beads linked as a circle. Each bead is either crystal or jade.
Now, your task is:
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
Now, your task is:
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
Input
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.
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.
Output
For each case, print “Case x: d” on a single line in which x is the number of case counted from one and d is the number of ways.
Sample Input
2
CJCJCJ
CCJJCCJJCCJJCCJJ
Sample Output
Case 1: 6
Case 2: 8
Author
love8909
Source
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std; char a[];
bool flag[];
int s1[];
typedef struct
{
int num;
int sum;
} Queue;
Queue q[],tmp;
int tom; int main()
{
int T,t;
int i,k,n,len,tail,head;
while(scanf("%d",&T)>)
{
getchar();
for(t=; t<=T; t++)
{
scanf("%s",a+);
n=strlen(a+);
len=n+n;
for(i=n+; i<=len; i++)
a[i]=a[i-n];
for( s1[]=,i=; i<=len; i++)
{
if(a[i]=='C') s1[i]=s1[i-]+;
else s1[i]=s1[i-]-;
}
memset(flag,false, sizeof(flag));
head=;
tail=-;
for(i=; i<=len-; i++)
{
tmp.sum=s1[i];
tmp.num=i;
while( head<=tail && q[tail].sum>tmp.sum ) tail--;
q[++tail]=tmp;
if( i>=n )
{
while( head<=tail && q[head].num+n<=i ) head++;
if( q[head].sum-s1[i-n]>= )
{
flag[ i-n+ ]=true;
// printf("%d ",i-n+1);
}
}
}
// printf("\n");
s1[]=;
for(i=; i<=len; i++)
{
k=len-i+;
if(a[k]=='C') s1[i]=s1[i-]+;
else s1[i]=s1[i-]-;
}
head=;tail=-;
for(i=; i<=len; i++)
{
tmp.sum=s1[i];
tmp.num=i;
while( head<=tail && q[tail].sum>tmp.sum ) tail--;
q[++tail]=tmp;
if( i>n )
{
while( head<=tail && q[head].num+n<=i ) head++;
if( q[head].sum-s1[i-n]>= )
{
flag[ n-(i-n)+ ]=true;
// printf("%d ",n-(i-n)+1);
}
}
}
// printf("\n");
for(tom=,i=; i<=n; i++)
if(flag[i]==true) tom++;
printf("Case %d: %d\n",t,tom);
}
}
return ;
}