首页 > ACM题库 > HDU-杭电 > HDU 3474-Necklace-模拟-[解题报告]HOJ
2014
04-04

HDU 3474-Necklace-模拟-[解题报告]HOJ

Necklace

问题描述 :

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

输入:

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

题意:给你一条项链,让你切开,然后将上面的水晶和珍珠拿下来再连起来,但现在只问你你有多少种切割方法使得你拿下来的水晶数量一定不少于珍珠数量,只能一个一个拿。

分析:最先想到的肯定是暴力枚举每个断点然后查询len长度的C和J的个数比较一下,看一下范围项链长度2<=len<=10^6,肯定会超,因为任何时候都要满足一个条件,就是sum(C)>=sum(J)也就是sum(C)-sum(J)>=0;我们可以将sum(C)-sum(J)用sum[i]来表示,表示前i个珠子里水晶数量与珍珠的差值,显然我们可以看出sum[i]-sum[j]表示的是从j+1开始到i这个珠子的差值和,而我们要找的是len长度中的差值全部不小于0的那一段,这显然用单调队列来实现只要保证min(sum[i]~sum[i-len+1])-sum[i-len]就可以了,问题解决了,后面写的是后发现还要反过来求一次,最后将两次的位置去重就好了,这个细节卡了我一个下午,校对位置的时候错了,一直没发现,后来模拟多点数据就发现错了,就这样贡献了10+wa啊,我是从0开始的,别人好像为了去重方便就直接从1开始,我从0开始,后面回差一位,就果断在后面加个0对位,一交果断AC。

还有今天突发奇想的想用二分优化单调队列,结果写完后更慢了,坑爹啊。

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);
    }
}

参考:http://blog.csdn.net/xymscau/article/details/6679941


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks