首页 > ACM题库 > HDU-杭电 > hdu 2668 Daydream[解题报告]C++
2014
02-12

hdu 2668 Daydream[解题报告]C++

Daydream

问题描述 :

Welcome to 2009 HDU Girl’s Cup, bless you will happy in it.
Every girl are beautiful if you use you heart to feel. Every corner in the world will colourful and energetic by several girls standing. If you boy, a normal bay, I believe that you will try to watch when a beautiful girl passing you and you will nervous if a girl watching you just when you are watching her.

Now give you a surprise that may be never happy in the real time. Millions of PLMM stand in a line and facing you(^_^). They are dress colourful clothings. You should to find out a maximal subline PLMM that their clothing color are all different.

输入:

The input contains multiple test cases.
Each case first give a integer n expressing many many girls stand in line.(n<=10000000)
Next line a string including n character, each character standing one girls’s clothing color.

输出:

The input contains multiple test cases.
Each case first give a integer n expressing many many girls stand in line.(n<=10000000)
Next line a string including n character, each character standing one girls’s clothing color.

样例输入:

3
abc
5
aaaba
8
hdugirls

样例输出:

3 0 2
2 2 3
8 0 7

每次记录一个区间长度,当新加入的字符与它相等的最近字符的位置小于区间起点时,区间长度加1。

则更新区间,遍历一遍找到最大区间





#include<stdio.h>
#include<string.h>
int n,mark[150];
char str[10000010];
int main()
{
	int i,x,len,ss,llen;
	while(scanf("%d",&n)!=-1)
	{
		memset(mark,-1,sizeof(mark));//记录字符出现的位置
		scanf("%s",str);
		len=llen=0;x=ss=0;
		for(i=0;i<n;i++)
		{
			if(mark[str[i]]<ss)//如果字符上次出现的位置在区间外,区间+1
				llen++;
			else
			{				
				if(llen>len)//更新最大区间
				{	
					len=llen;
					x=ss;
				}
				ss=mark[str[i]]+1;//新起点
				llen=i-ss+1;//新区间长度
				
			}
			mark[str[i]]=i;
		}
		if(llen>len)
		{	
			len=llen;
			x=ss;
		}
		printf("%d %d %d\n",len,x,x+len-1);
	}
}

解题转自:http://blog.csdn.net/aixiaoling1314/article/details/9288059


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。