正文
Necklace
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1553 Accepted Submission(s): 453
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
CJCJCJ
CCJJCCJJCCJJCCJJ
Sample Output
Case 1: 6
Case 2: 8
Case 2: 8
Author
love8909
Source
2010 ACM-ICPC Multi-University Training Contest(4)——Host by UESTC
Recommend
zhengfeng | We have carefully selected several similar problems for you: 3473 3470 3471 3472 3475
解题分析:
这个题为是快用了单调队列,把C当作1,J当作-1放到arr【】数组里,其中arr【n】=arr【n-m】,这里n>m,再维护一个sum【】数组,其中sum【i】表示arr【0】到arr【i】的和,然后构造单调队列,找出连续m个元素中的最小值,然后减去该连续m个元素的第1个元素的前面的一个元素的值,然后判断这个值的大小,如果小于0则不能在此处剪,否则能在此处剪。然后注意不同的方向用不同的sum数组。最后要注意不同方向比较时要在同一剪切点进行比较。为了节省空间arr【】数组开成m大小的。然后当数组过大时就把它构造成全局变量,这样就不是堆溢出了。最后,一定要细心,粗心大意害死人呐。。。他娘的。。
#include<iostream>
#define N 2000010
using namespace std;
int arr[1000010];
int sum[N];
int que[N];
int ok1[N],ok2[N];
#define N 2000010
using namespace std;
int arr[1000010];
int sum[N];
int que[N];
int ok1[N],ok2[N];
void main()
{
int n,c=0;
cin>>n;
getchar();
while(n--)
{
c++;
int all=0;
char temp;
int m=0;
while(temp=getchar())
{
if(temp=='C')
arr[m]=1;
else if(temp=='J')
arr[m]=-1;
else break;
m++;
}
sum[0]=0;
for(int i=1;i<=m;i++)
sum[i]=sum[i-1]+arr[i-1];
for(i=m+1;i<=2*m;i++)
sum[i]=sum[m]+sum[i-m];
int start=0 , tail=0;
for(i=m*2;i>0;i--)
{
while(start<tail && sum[que[tail-1]]>sum[i]) tail--;
que[tail++]=i;
while(start<tail && que[start]-i>m-1) start++;
ok1[i]=sum[que[start]]-sum[i-1];
}
sum[2*m]=0;
for(i=2*m;i>m;i--)
sum[i-1]=sum[i]+arr[i-m-1];
for(i=m-1;i>=0;i--)
sum[i]=sum[m]+sum[m+i];
start=tail=0;
for(i=0;i<m*2;i++)
{
while(start<tail && sum[que[tail-1]]>sum[i]) tail--;
que[tail++]=i;
while(start<tail && i-que[start]>m-1) start++;
ok2[i]=sum[que[start]]-sum[i+1];
}
for(i=m;i<m*2-1;i++)
if(ok2[i]>=0 || ok1[i-(m-2)]>=0) all++;
if(ok1[1]>=0 || ok2[2*m-1]>=0) all++;
cout<<"Case "<<c<<": "<<all<<endl;
}
}