08-04-2013 1 条评论

时间限制: 2000ms 内存限制: 256MB

描述
有一棵树,树上有只毛毛虫。它在这棵树上生活了很久,对它的构造了如指掌。所以它在树上从来都是走最短路,不会绕路。它还还特别喜欢三角形,所以当它在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢?

输入
输入数据的第一行包含一个整数 T,表示数据组数。

接下来有 T 组数据,每组数据中:

第一行包含一个整数 N,表示树上节点的个数(从 1 到 N 标号)。

接下来的 N-1 行包含三个整数 a, b, len,表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 M,表示询问数。

接下来M行每行两个整数 S, T,表示毛毛虫从 S 爬行到了 T,询问这段路程中的树枝/树干是否能拼成三角形。

输出
对于每组数据,先输出一行"Case #X:",其中X为数据组数编号,从 1 开始。

接下来对于每个询问输出一行,包含"Yes"或“No”,表示是否可以拼成三角形。

数据范围
1 ≤ T ≤ 5

小数据:1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000

大数据:1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
样例输出
Case #1:
No
Yes
Case #2:
No
Yes

#include<string>
#include<memory.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
struct load{
    int point;
    load*next;
};
int shortload(int start,int matrix[][105],int point,load **load_path);
const int INF=10000000;
int visit[105];
int matrix[105][105];
int dis[105];
int path[105][105];
load * load_path[105];
int main()
{
    int T,x;
	cin>>T;
	for(x=1;x<T+1;x++)
	{
		cout<<"Case #:"<<x<<endl;
		int point,line,length;
		int start_x,end_x;
		int i,j,k,l;
		cin>>point;
		for( i=0;i<point;i++)
			for( j=0;j<point;j++)
				matrix[i][j]=INF;
		for(i=0;i<point-1;i++)
		{
			int start,end;
			cin>>start>>end>>length;
			matrix[start-1][end-1]=matrix[end-1][start-1]=length;
		}
		int question;
		cin>>question;
		while(question--)
		{
			memset(path,0,105*105*sizeof(int ));
			cin>>start_x>>end_x;
			for( i=0;i<point;i++)
			{
				load_path[i]=(load*)malloc(sizeof(load));
				load_path[i]->point=start_x-1;
				load* p=(load*)malloc(sizeof(load));
				p->point=i;
				p->next=NULL;
				load_path[i]->next=p;
			}
			shortload(start_x-1,matrix,point,load_path);
			load* p=load_path[end_x-1];
			i=0;
			if(p)
			{
				while(p->next)
				{
					path[end_x-1][i]=matrix[p->point][p->next->point];
					i++;
					p=p->next;
				}
			}
			int flag=0;
			if(i<3)
			cout<<"No"<<endl;
			else
			{
				for(j=0;j<i-2;j++)
					for( k=j+1;k<i-1;k++)
						for(l=k+1;l<i;l++)
						{
							if((path[end_x-1][j]+path[end_x-1][k]>path[end_x-1][l])&&(path[end_x-1][j]-path[end_x-1][k]<path[end_x-1][l])
								&&(path[end_x-1][j]+path[end_x-1][l]>path[end_x-1][k])&&(path[end_x-1][j]-path[end_x-1][l]<path[end_x-1][k])
								&&(path[end_x-1][k]+path[end_x-1][l]>path[end_x-1][j])&&(path[end_x-1][k]-path[end_x-1][l]<path[end_x-1][j])
								)
							{
								cout<<"Yes"<<endl;
								flag=1;
								k=i-1;
								j=i-2;
								break;
							}
						}
						if(flag==0)
							cout<<"No"<<endl;
			}
		}
	}
}
int shortload(int start,int matrix[][105],int point,load ** load_path)
{
	for(int i=0;i<point;i++)
	{
		dis[i]=matrix[start][i];
		visit[i]=0;
	}
	visit[start]=1;
	dis[start]=0;
	int x=0;
	for(int i=0;i<point;i++)
	{
		int min=INF;
		for(int j=0;j<point;j++)
		{
			if(dis[j]<min&&visit[j]==0)
			{
				min=dis[j];
				x=j;
			}
		}
		visit[x]=1;
		for(int j=0;j<point;j++)
			if(visit[j]==0&&dis[x]+matrix[x][j]<dis[j])
			{
				load*p=load_path[x]->next;
				while(p)
				{
					load* q=(load*)malloc(sizeof(load));
					q->next=load_path[j]->next;
					load_path[j]->next=q;
					p=p->next;
				}
				p=load_path[x]->next;
				load*q=load_path[j]->next;
				while(p)
				{
					q->point=p->point;
					p=p->next;
					q=q->next;
				}
				dis[j]=dis[x]+matrix[x][j];
			}
	}
	return 0;
}

使用RE,放弃了,反正资格赛只要一道题就可以了,交给大家去解决吧。

高手用Java写的,大数据应该也没有问题:

https://github.com/castorgmc/LeetCode/blob/master/src/problems/Main.java

08-04-2013 0 条评论

时间限制: 1000ms 内存限制: 256MB

描述
在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。

输入
输入文件包含多组测试数据。

第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N,M,K。

输出
对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

数据范围
1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据:0 < N, M ≤ 30

大数据:0 < N, M ≤ 30000

样例输入
3
3 3 8
4 5 13
7 14 86
样例输出
Case #1: 5
Case #2: 18
Case #3: 1398

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <fstream>
using namespace std;
typedef long long LL;
int main()
{
        int T,x;
        while(scanf("%d",&T)==1)
        {
                for(x=1;x<=T;x++)
                {
                        LL N,M,K;
                        scanf("%lld%lld%lld",&N,&M,&K);
                        if(N>M)//让M大于N
                        {
                                N=M+N;
                                M=N-M;
                                N=N-M;
                        }
                        int n=sqrt(K)>N?N:sqrt(K);
                        int m=M;
                        while(n * m>K)
                                m--;
                        LL ans=0;
                        LL res=0;
                        while(n>=2&&m<=M)
                        {
                                LL k=K;
                                res += (n*m*(n-1)*(m-1))>>2 ;
                                k -= m*n;
                                if(m < M)
                                        res+=(m*k*(k-1))>>1;
                                else
                                        res+=(n*k*(k-1))>>1;
                                ans=res>ans?res:ans;
                                res=0;
                                n --;
                                m=K/n;
                        }
                        printf("Case #%d: %lldn",x,ans);
                }
        }
        return 0;
}

需要用到组合数学,还是破费了一番周折。思路就是先找到在网格中最大能形成的长方形矩阵的长x和宽y,算出剩余石子l,根据公式xy(x-1)(y-1)/4算出最大长方形矩阵可形成的长方形数量(正方形也属于长方形),再算出最长边加入剩余石子后可形成的长方形数量x * (l * (l-1)/2),他们的和即为结果。

08-04-2013 2 条评论

时间限制: 1000ms 内存限制: 256MB

描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位。然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位……以此类推,直到倒数第二位告诉Bob。两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释。最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家。 

由于传话过程中可能出现一些偏差,游戏者越多,Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西,所以大家玩得乐此不疲。经过几轮游戏后,Alice注意到在两人传话中,有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表,她想知道她的话传到Bob时会变成什么样子,请你写个程序来帮助她。

输入
输入包括多组数据。第一行是整数 T,表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M,分别表示游戏者的数量和单词转化列表长度。随后有 M 行,每行包含两个用空格隔开的单词 a 和 b,表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词,表示Alice所想的句子,句子总长不超过100个字符。所有单词都只包含小写字母,并且长度不超过20,同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。

输出
对于每组测试数据,单独输出一行“Case #c: s”。其中,c 为测试数据编号,s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。

数据范围
1 ≤ T ≤ 100

小数据:2 ≤ N ≤ 10, 0 ≤ M ≤ 10 

大数据:2 ≤ N ≤ 100, 0 ≤ M ≤ 100 

样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear

#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
using namespace std;

int main()
{
    int T;
    cin>>T;
    if(T<1||T>100)
        return 0;
    string result[100];
    int N,M;
    map<string,string> mapstring;
    for(int k=0;k<T;++k){
        cin>>N>>M;
        if(N<2||N>10||M<0||M>10)
            return 0;
        string s1,s2,str[1000];
        mapstring.clear();
        for(int i=0;i<M;++i){
            cin>>s1>>s2;
            if(s1.size()>20||s2.size()>20)
                return 0;
            mapstring.insert(pair <string,string>( s1, s2 ));
        }
        int itr=0;
         string ss;
        getchar();
        getline(cin,ss);
        string::iterator p=ss.begin();
        while(p!=ss.end()){
            if(*p==' ')
                ++itr;
            else
                str[itr].push_back(*p);
            ++p;
        }
        itr=0;
        map<string, string>::iterator iter;
        while(str[itr]!=""){
            for(int i=0;i<N-1;++i){
                iter=mapstring.find(str[itr]);
                if(iter!=mapstring.end())
                    str[itr]=iter->second;
                else
                    break;
            }
            itr++;
        }
        if(str[itr]=="")
            if(itr>100)
                return 0;
        else
            if(itr>99)
                return 0;
        itr=0;
        while(str[itr]!=""){
            string tmp=str[itr]+" ";
            result[k]+=tmp;
            itr++;
        }
        result[k]=result[k].substr(0,result[k].length()-1);
    }
    for(int i=0;i<T;++i)
        cout<<"Case #"<<i+1<<": "<<result[i]<<endl;
    return 0;
}
10-10-2012 1 条评论

转载:《计算机教育》第10期    作者:汪鹏
   计算机是人类解决难题、探索未知以及提供娱乐的绝佳工具。在高效运行着的各种计算机应用背后,融汇了人类在物理、电子和数学等多门学科的高超智慧。严密的数学使得计算机能高效执行人类指令,控制内部各种数据流的走向,因此在现代计算机科学研究中,数学的基础地位和重要作用无可替代:它使我们最大程度利用有限的硬件、软件资源,它使我们能够在浩瀚的数据海洋中快速查到所关心的信息……数学与计算机科学一起演绎了许多精彩的故事!
一、NMF的发展及原理
著名的科学杂志《Nature》于1999年刊登了两位科学家D.D.Lee和H.S.Seung对数学中非负矩阵研究的突出成果。该文提出了一种新的矩阵分解思想——非负矩阵分解(Non-negative Matrix Factorization,NMF)算法,即NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。该论文的发表迅速引起了各个领域中的科学研究人员的重视:一方面,科学研究中的很多大规模数据的分析方法需要通过矩阵形式进行有效处理,而NMF思想则为人类处理大规模数据提供了一种新的途径;另一方面,NMF分解算法相较于传统的一些算法而言,具有实现上的简便性、分解形式和分解结果上的可解释性,以及占用存储空间少等诸多优点。
信息时代使得人类面临分析或处理各种大规模数据信息的要求,如卫星传回的大量图像、机器人接受到的实时视频流、数据库中的大规模文本、Web上的海量信息等。处理这类信息时,矩阵是人们最常用的数学表达方式,比如一幅图像就恰好与一个矩阵对应,矩阵中的每个位置存放着图像中一个像素的空间位置和色彩信息。由于实际问题中这样的矩阵很庞大,其中存放的信息分布往往不均匀,因此直接处理这样的矩阵效率低下,这对很多实际问题而言就失去了实用意义。为高效处理这些通过矩阵存放的数据,一个关键的必要步骤便是对矩阵进行分解操作。通过矩阵分解,一方面将描述问题的矩阵的维数进行削减,另一方面也可以对大量的数据进行压缩和概括。
在科学文献中,讨论利用矩阵分解来解决实际问题的分析方法很多,如PCA(主成分分析)、ICA(独立成分分析)、SVD(奇异值分解)、VQ(矢量量化)等。在所有这些方法中,原始的大矩阵V被近似分解为低秩的V=WH形式。这些方法的共同特点是,因子W和H中的元素可为正或负,即使输入的初始矩阵元素是全正的,传统的秩削减算法也不能保证原始数据的非负性。在数学上,从计算的观点看,分解结果中存在负值是正确的,但负值元素在实际问题中往往是没有意义的。例如图像数据中不可能有负值的像素点;在文档统计中,负值也是无法解释的。因此,探索矩阵的非负分解方法一直是很有意义的研究问题,正是如此,Lee和Seung两位科学家的NMF方法才得到人们的如此关注。
NMF是一种新的矩阵分解算法,它克服了传统矩阵分解的很多问题,通过寻找上下文有意义的解决方法,提供解释数据的更深看法。NMF通过寻找低秩,非负分解那些都为非负值的矩阵。这在现实的应用中有很多例子,如数字图像中的像素一般为非负数,文本分析中的单词统计也总是非负数,股票价格也总是正数等等。NMF的基本思想可以简单描述为:对于任意给定的一个非负矩阵A,NMF算法能够寻找到一个非负矩阵U和一个非负矩阵V,使得满足 ,从而将一个非负的矩阵分解为左右两个非负矩阵的乘积。由于分解前后的矩阵中仅包含非负的元素,因此,原矩阵A中的一列向量可以解释为对左矩阵U中所有列向量(称为基向量)的加权和,而权重系数为右矩阵V中对应列向量中的元素。这种基于基向量组合的表示形式具有很直观的语义解释,它反映了人类思维中“局部构成整体”的概念。研究指出,非负矩阵分解是个NP问题,可以划为优化问题用迭代方法交替求解U和V。NMF算法提供了基于简单迭代的求解U,V的方法,求解方法具有收敛速度快、左右非负矩阵存储空间小的特点,它能将高维的数据矩阵降维处理,适合处理大规模数据。利用NMF进行文本、图像大规模数据的分析方法,较传统的处理算法速度更快、更便捷。NMF思想的提出迅速得到了很多人的重视,并有很多将这种思想应用到实际中成功解决具体实际问题的例子。
通过图1中的面部特征提取例子可领略NMF处理数据的方式。最左边的大矩阵由一系列的小图组成,这些小图是分析数据库中包含的2429个脸部图像的结果,每幅图像由19×19个像素组成。传统方法中这样的小图是一幅完整的人脸图像,但是在NMF方法中,每个小图是通过一组基图像乘以一个权重矩阵而产生的面部特征图,经过这样处理的每幅小图像恰好表示了诸如“鼻子”、“嘴巴”、“眼睛”等人脸局部概念特征,这便大大压缩了存放的图像数据量。左边的大矩阵由每幅小图像的19列一起组成矩阵的一列,那样它就是19×19=361行,2429列。由于NMF不允许基图像或中间的权重矩阵中出现负值,因此只有相加组合得到的正确基图像才允许,最后通过处理后的重构图像效果是比较满意的。这个例子中,NMF方法用基图像来代表眼、眉毛、鼻子、嘴、耳朵、胡子等,它们一起组成了数据库中的脸。这样给人最先的直觉就是它很好地压缩了数据。事实上Lee和Seung在他们的论文中更深入地指出,与人类识别事物的过程相似,NMF也是一种优化的机制,近似于我们的脑分析和存储人脸数据的过程。这个例子中,原图像表示这些局部特征的加权组合,这与人类思维中“局部构成整体”的概念是相吻合的。因此,NMF算法似乎体现了一种智能行为。
图1  NMF提取面部特征的实例
事实上,在Lee和Seung发表他们的研究成果之前,针对非负矩阵的研究早在20世纪70年代已经有数学家做了一些相关的工作,但是没有引起过多的关注。20世纪90年代早期,科学家开始将数学上非负矩阵的研究成果用于环境处理和卫星遥控的应用,但是对于非负矩阵的应用意义和价值的理解仍只局限于少数科学家中,人们还没有广泛重视这种方法。直到1999年Lee和Seung的非负矩阵研究成果发表在《Nature》杂志之后,这一切才得以改变。尽管同年有另两位科学家也发表了与Lee和Seung相近的研究结果,但由于论文刊登在并非如《Nature》那样具有极高声誉的学术杂志上,因此其工作并没有得到如Lee和Seung同样的关注,这也从一个侧面折射了高水平学术杂志对研究工作的推动作用。
二、应用领域
NMF是一个很有效的算法,它力图在大规模的矩阵数据中发现具有解释功能的关系,相比当前文献中公布的其他方法来说,使用NMF的算法也是非常精确和快速的。NMF算法思想能为世界上权威的学术刊物所接受并非偶然,因为该理论本身蕴涵了巨大的潜能,这种潜在的力量将通过各种具体的应用来得以体现。计算机能通过NMF算法更快更好地处理哪些实际问题呢?在众多应用中,NMF能被用于发现数据库中的图像特征,便于快速自动识别应用;能够发现文档的语义相关度,用于信息自动索引和提取;能够在DNA阵列分析中识别基因等等。我们将对此作一些大致的描述。
(1) 图像分析
NMF最成功的一类应用是在图像的分析和处理领域。图像本身包含大量的数据,计算机一般将图像的信息按照矩阵的形式进行存放,针对图像的识别、分析和处理也是在矩阵的基础上进行的。这些特点使得NMF方法能很好地与图像分析处理相结合。人们已经利用NMF算法,对卫星发回的图像进行处理,以自动辨别太空中的垃圾碎片;使用NMF算法对天文望远镜拍摄到的图像进行分析,有助于天文学家识别星体;美国还尝试在机场安装由NMF算法驱动的识别系统,根据事先输入计算机的恐怖分子的特征图像库来自动识别进出机场的可疑恐怖分子。
(2) 文本聚类/数据挖掘
文本在人类日常接触的信息中占有很大分量,为了更快更精确地从大量的文本数据中取得所需要的信息,针对文本信息处理的研究一直没有停止过。文本数据不光信息量大,而且一般是无结构的。此外,典型的文本数据通常以矩阵的形式被计算机处理,此时的数据矩阵具有高维稀疏的特征,因此,对大规模文本信息进行处理分析的另一个障碍便是如何削减原始数据的维数。NMF算法正是解决这方面难题的一种新手段。NMF在挖掘用户所需数据和进行文本聚类研究中都有着成功的应用例子。由于NMF算法在处理文本数据方面的高效性,著名的商业数据库软件Oracle在其第10版中专门利用NMF算法来进行文本特征的提取和分类。为什么NMF对于文本信息提取得很好呢?原因在于智能文本处理的核心问题是以一种能捕获语义或相关信息的方式来表示文本,但是传统的常用分析方法仅仅是对词进行统计,而不考虑其他的信息。而NMF不同,它往往能达到表示信息的局部之间相关关系的效果,从而获得更好的处理结果。
(3) 语音处理
语音的自动识别一直是计算机科学家努力的方向,也是未来智能应用实现的基础技术。语音同样包含大量的数据信息,识别语音的过程也是对这些信息处理的过程。NMF算法在这方面也为我们提供了一种新方法,在已有的应用中,NMF算法成功实现了有效的语音特征提取,并且由于NMF算法的快速性,对实现机器的实时语音识别有着促进意义。也有使用NMF方法进行音乐分析的应用。复调音乐的识别是个很困难的问题,三菱研究所和MIT(麻省理工学院)的科学家合作,利用NMF从演奏中的复调音乐中识别出各个调子,并将它们分别记录下来。实验结果表明,这种采用NMF算法的方法不光简单,而且无须基于知识库。
(4) 机器人控制
如何快速准确地让机器人识别周围的物体对于机器人研究具有重要的意义,因为这是机器人能迅速作出相应反应和动作的基础。机器人通过传感器获得周围环境的图像信息,这些图像信息也是以矩阵的形式存储的。已经有研究人员采用NMF算法实现了机器人对周围对象的快速识别,根据现有的研究资料显示,识别的准确率达到了80%以上。
(5) 生物医学工程和化学工程
生物医学和化学研究中,也常常需要借助计算机来分析处理试验的数据,往往一些烦杂的数据会耗费研究人员的过多精力。NMF算法也为这些数据的处理提供了一种新的高效快速的途径。科学家将NMF方法用于处理核医学中的电子发射过程的动态连续图像,有效地从这些动态图像中提取所需要的特征。NMF还可以应用到遗传学和药物发现中。因为NMF的分解不出现负值,因此采用NMF分析基因DNA的分子序列可使分析结果更加可靠。同样,用NMF来选择药物成分还可以获得最有效的且负作用最小的新药物。
此外,NMF算法在环境数据处理、信号分析与复杂对象的识别方面都有着很好的应用。近年来采用NMF思想的应用才刚展开,相信以后会有更多的成功应用。这些成功的应用反过来也将促进NMF的进一步研究。
三、结束语
数学如同计算机的灵魂,NMF通过计算机与各个领域结合后的应用取得了令人叹服的成效。NMF的故事还在继续,NMF的应用领域还有待进一步的发掘,针对NMF的进一步研究也没有停止过,其中诸如分解的存在性、惟一性和收敛性以及收敛的速度等问题的深入探讨必将使该思想能更好地服务于人类。

24-09-2012 0 条评论

最近有学妹问到这个问题,自己在学习Java也没有注意到问题,故而又重新看了一下这部分,整理一下,也算方便大家。

首先我们看看浅拷贝和深拷贝的定义
浅拷贝:只复制一个对象,对象内部存在的指向其他对象数组或者引用则不复制。
深拷贝:对象,对象内部的引用均复制。
为了更好的理解它们的区别我们假设有一个对象A,它包含有2对象对象A1和对象A2

 对象A进行浅拷贝后,得到对象B但是对象A1和A2并没有被拷贝

对象A进行深拷贝,得到对象B的同时A1和A2连同它们的引用也被拷贝

总结一下:

Java中对象的克隆,为了获取对象的一份拷贝,我们可以利用Object类的clone()方法。必须要遵循下面三点 

1.在派生类中覆盖基类的clone()方法,并声明为public【Object类中的clone()方法为protected的】。 

2.在派生类的clone()方法中,调用super.clone()。 

3.在派生类中实现Cloneable接口。 


Object类里的clone方法是浅复制(浅克隆)

浅复制(浅克隆)的例子:

package com.test;

//浅复制(浅克隆): 浅复制仅仅复制所考虑的对象,而不复制它所引用的对象。
//深复制(深克隆):深复制把要复制的对象所引用的对象都复制了一遍。
//
//Java中对象的克隆,为了获取对象的一份拷贝,我们可以利用Object类的clone()方法。必须要遵循下面三点
//1.在派生类中覆盖基类的clone()方法,并声明为public【Object类中的clone()方法为protected的】。
//2.在派生类的clone()方法中,调用super.clone()。
//3.在派生类中实现Cloneable接口。

//<SPAN style="COLOR: red">Object类里的clone方法是浅复制(浅克隆)</SPAN>public class CloneTest {

	public static void main(String[] args) throws Exception{
		//teacher对象将被clone出来的Student对象共享.
		Teacher teacher = new Teacher();
		teacher.setAge(40);
		teacher.setName("Teacher zhang");
		
		Student student1 = new Student();
		student1.setAge(20);
		student1.setName("zhangsan");
		student1.setTeacher(teacher);
		
		//复制出来一个对象student2
		Student student2 = (Student)student1.clone();
		System.out.println(student2.getAge());
		System.out.println(student2.getName());
		
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
		
		
		//修改student2的引用对象
		student2.getTeacher().setAge(50);
		student2.getTeacher().setName("Teacher Li");
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
	}
}

class Teacher {
	public int age;
	public String name;
	
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	
	
}

class Student implements Cloneable{
	
	public int age ;
	public String name;
	public Teacher teacher;
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Teacher getTeacher() {
		return teacher;
	}
	public void setTeacher(Teacher teacher) {
		this.teacher = teacher;
	}
	@Override
	public Object clone() throws CloneNotSupportedException {
		return super.clone();
	}
	
	
}
输出结果为:
20
zhangsan
~~~~~~~~~~~~~~~~~~~~~~
40
Teacher zhang
~~~~~~~~~~~~~~~~~~~~~~
50
Teacher Li

2.深复制(深Clone)例子: 

package com.test1;

//深clone
public class DeepCloneTest {

	public static void main(String[] args) throws Exception{
		//teacher对象将不被clone出来的Student对象共享.
		Teacher teacher = new Teacher();
		teacher.setAge(40);
		teacher.setName("Teacher zhang");
		
		Student student1 = new Student();
		student1.setAge(20);
		student1.setName("zhangsan");
		student1.setTeacher(teacher);
		
		//复制出来一个对象student2
		Student student2 = (Student)student1.clone();
		System.out.println(student2.getAge());
		System.out.println(student2.getName());
		
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
		
		
		//修改student2的引用对象
		student2.getTeacher().setAge(50);
		student2.getTeacher().setName("Teacher Li");
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
	}
}

class Teacher implements Cloneable{
	public int age;
	public String name;
	
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	@Override
	public Object clone() throws CloneNotSupportedException {
		return super.clone();
	}
	
}

class Student implements Cloneable{
	
	public int age ;
	public String name;
	public Teacher teacher;
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Teacher getTeacher() {
		return teacher;
	}
	public void setTeacher(Teacher teacher) {
		this.teacher = teacher;
	}
	@Override
	public Object clone() throws CloneNotSupportedException {
		Student student = (Student)super.clone();
		//将引用的对象teacher也clone下
		student.setTeacher((Teacher)(student.getTeacher().clone()));
		return student;
	}
	
	
}
输出结果为:
20
zhangsan
~~~~~~~~~~~~~~~~~~~~~~
40
Teacher zhang
~~~~~~~~~~~~~~~~~~~~~~
40
Teacher zhang

3.利用序列化来做深复制,把对象写到流里的过程是序列化(Serilization)过程,而把对象从流中读出来的过程则叫做反序列化(Deserialization)过程。应当指出的是,写在流里的是对象的一个拷贝,而原对象仍然存在于JVM里面,利用这个特性,可以做深拷贝

package com.test3;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
//利用序列化来做深复制
//深clone
public class DeepCloneTest {

	public static void main(String[] args) throws Exception{
		//teacher对象将不被clone出来的Student对象共享.
		Teacher teacher = new Teacher();
		teacher.setAge(40);
		teacher.setName("Teacher zhang");
		
		Student student1 = new Student();
		student1.setAge(20);
		student1.setName("zhangsan");
		student1.setTeacher(teacher);
		
		//复制出来一个对象student2
		Student student2 = (Student)student1.deepCopy();
		System.out.println(student2.getAge());
		System.out.println(student2.getName());
		
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
		
		
		//修改student2的引用对象
		student2.getTeacher().setAge(50);
		student2.getTeacher().setName("Teacher Li");
		
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println(student1.getTeacher().getAge());
		System.out.println(student1.getTeacher().getName());
	}
}

class Teacher implements Serializable{
	
	private static final long serialVersionUID = -8834559347461591191L;
	
	public int age;
	public String name;
	
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	
}

class Student implements Serializable{
	
	//serialVersionUID 如果你的对象序列化后存到硬盘上面后,可是后来你却更改了类的field(增加或减少或改名),当你反序列化时,就会出现Exception的,这样就会造成不兼容性的问题。 
	//但当serialVersionUID相同时,它就会将不一样的field以type的缺省值赋值(如int型的是0,String型的是null等),这个可以避开不兼容性的问题。所以最好给serialVersionUID赋值
	private static final long serialVersionUID = 7991552226614088458L;
	
	public int age ;
	public String name;
	public Teacher teacher;
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Teacher getTeacher() {
		return teacher;
	}
	public void setTeacher(Teacher teacher) {
		this.teacher = teacher;
	}
	
	public Object deepCopy() throws Exception{
		//将该对象序列化成流,因为写在流里的是对象的一个拷贝,而原对象仍然存在于JVM里面。所以利用这个特性可以实现对象的深拷贝
		ByteArrayOutputStream bos = new ByteArrayOutputStream();

		ObjectOutputStream oos = new ObjectOutputStream(bos);

		oos.writeObject(this);

		//将流序列化成对象
		ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray());

		ObjectInputStream ois = new ObjectInputStream(bis);

		return ois.readObject();
	}
	
	
}
输出结果为:
20
zhangsan
~~~~~~~~~~~~~~~~~~~~~~
40
Teacher zhang
~~~~~~~~~~~~~~~~~~~~~~
40
Teacher zhang


30-05-2012 1 条评论
描述

继百度搜索框大厦之后,百度又于2012年初在深圳奠基了新的百度国际大厦,作为未来百度国际化的桥头堡。不同于百度在北京的搜索框大厦,新的百度国际大厦是一栋高楼,有非常多的楼层,让每个楼中的电梯都能到达所有楼层将是一个极为不明智的设计。因此,设计师给出了一个特别的设计——一共大厦有m个电梯,每个电梯只有两个按钮,(针对第i个电梯)两个按钮分别可以使电梯向上或ui层向下一定di层;百度国际大厦很高,你永远到不了顶层,也就是说电梯没有上限,但是,电梯不可以钻入地下,也就是说是有下限的。我们将每层楼用整数标记,为了体现IT公司的特质,我们以0作为地面这一层的标记。
如果你某天在百度国际大厦的0层,仅可以选择m个电梯中的一个乘坐(不可以中途换电梯),请你计算,你按电梯中的按钮n次后(每次两个按钮选一个按),可以到达的最低楼层数。

输入
输入的第一行包括两个整数,分别为n和m(1 ≤ n ≤ 1,000,000,1 ≤ m ≤ 2,000),表示按电梯按钮的次数和大厦中的电梯数量。接下去的m行,每行包括2个由空格分割的数字,分别表示了提供的m个电梯中的某一个的上行按钮上升一次的层数ui和下行按钮下降一次的层数di(1 ≤ ui,di ≤ 1000)
输出
输出一个正整数,表示选用m个电梯中的一个后,在电梯里按电梯中的按钮n次后(每次两个按钮选一个按),可以到达的最低楼层数。
样例输入
10 3
15 4
15 12
7 12
样例输出
13
提示

按钮上的移动楼层数无法改变,比方说从8层向下9层是不可行的

我自己电脑(DevC++,)上可以运行的代码:

#include <cmath> 
#include <iostream>
using namespace std;
int main()
{
    int n,m;
    int *a;
    int *b;
    int i=0;
    int reault=0;
    int j=0;
    int tmp;
    int low=1;
    int high=0;
    cin>>n>>m;
    high=n;
    int mid;
    a=(int *)malloc(sizeof(int)*m);
    b=(int *)malloc(sizeof(int)*m);
    for(i=0;i<m;i++)
    {
        cin>>a[i]>>b[i]; 
    }
    for(i=0;i<m;i++)
    {
        low=1;
        high=n;
        while((high-low)>2)
        {
           mid=(low+high)/2;
           tmp=a[i]*mid-b[i]*(n-mid);
           if(tmp>0)
            {
                 high=mid;      
            }
            else
            {
                 low=mid+1;
            }            
                        
        }
        for(j=low;j<=high;j++)
        {
                 tmp=a[i]*j-b[i]*(n-j);
                 if(tmp>0) 
                 {break;}       
        }     
        if(reault==0)
           reault=tmp;
        else if(reault>tmp)
           reault=tmp;
        else
           reault=reault;
            
    }
   cout<<reault;
   system("pause");
   return 0;   
}

POJ编译通过的代码,害我提交三次:

#include <stdlib.h>
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
int n,m;
int *a;
int *b;
int i=0;
int reault=0;
int j=0;
int tmp;
int low=1;
int high=0;
    cin>>n>>m;
    high=n;
int mid;
    a=(int *)malloc(sizeof(int)*m);
    b=(int *)malloc(sizeof(int)*m);
for(i=0;i<m;i++)
{
        cin>>a[i]>>b[i];
}
for(i=0;i<m;i++)
{
        low=1;
        high=n;
while((high-low)>2)
{
           mid=(low+high)/2;
           tmp=a[i]*mid-b[i]*(n-mid);
if(tmp>0)
{
                 high=mid;
}
else
{
                 low=mid+1;
}
}
for(j=low;j<=high;j++)
{
                 tmp=a[i]*j-b[i]*(n-j);
if(tmp>0)
{break;}
}
if(reault==0)
           reault=tmp;
else if(reault>tmp)
           reault=tmp;
else
           reault=reault;
}
   cout<<reault;
//system("pause");
return 0;
}

30-05-2012 0 条评论

时间限制: 

1000ms 
内存限制: 
65536kB

描述

百度地图有自己的一套坐标系(你可以把它看作一个笛卡尔坐标系),在这套坐标系里,一个标准单位为1km。而在这坐标系上针对地理信息进行标注的数据,大多数时候是通过购买的方式完成的。为了节约数据更新的成本,数据组里的鑫哥想出了一个好主意——自己测数据。
鑫哥按照他的预想开始实验;在每组试验中,鑫哥选取了三个已经被准确标注在百度地图的坐标系里的移动运营商的基站作为信号接收点(这里可以准确的得到信号的接收时间信息)。当信号接收点附近的用户手机签到时,三个信号接收点就会先后接收到这个信号,并可以准确的知晓接收到信号的时间(将第一个信号点接收到信号的时间记为0秒时刻)。由此,我们就可以确定用户手机签到的位置的在地图的准确坐标了。
现在已知以下数据:
1.三个信号接收点在百度地图坐标系中的具体坐标(x1,y1), (x2,y2), (x3,y3);
2.三个信号点得到用户发出的信号的时间t1, t2, t3(t1, t2, t3 ≥ 0),单位s; t1, t2, t3至少有一个数为0;
3.信号的转播速度C,单位m/s;
请帮助鑫哥写个程序,计算下用户发出信号的位置在百度地图坐标系内的坐标(这个点是唯一的)。

输入
输入包含多组数据,每组数据格式如下:
C
x1 y1 x2 y2 x3 y3
t1 t2 t3
最后一组数据为0,表示输入结束。
输出
针对每组测试数据,请先输出这个组的编号(第n组就是输出“Case n:”);然后换行输出信号发出点的坐标(x,y) 。x,y应该由空格分隔,并被舍入到小数点后第六位。
样例输入
1000
0 1 1 1 2 1
0 0.6 1.6
1000
0 0 0 1 1 0
0.4142135 0 0
1000
0 0 1 0 2 1
0 0.414213562373 1
1000
0 0 0 -1 0 1
0 0 1
1000
0 0 0 1 0 -1
0 1 0
1000
0 0 1 0 -1 0
0 1 0
1000
0 0 -1 0 1 0
0 0 1
100
0 0 0 1 1 0
0 10 10
0
样例输出
Case 1:
0.200000 1.000000
Case 2:
1.000000 1.000000
Case 3:
0.000000 1.000000
Case 4:
0.000000 -0.500000
Case 5:
0.000000 -0.500000
Case 6:
-0.500000 0.000000
Case 7:
-0.500000 0.000000
Case 8:
0.000000 0.000000

算法原理:

完整代码下载:参考代码

29-05-2012 0 条评论
时间限制: 
1000ms 
内存限制: 
65536kB
描述

百度Hi作为百度旗下的即时聊天工具,在百度公司内部很是流行。要实现这样的一个聊天工具,最重要的问题就是要能保证我发出的内容能原封不动的在接收同学那里显示出来。今天,就给你一个机会,让你模拟一下百度Hi传递信息的过程,把我发给Robin的聊天内容原封不动的输出出来。

输入
输入的聊天内容数据有多组,每组数据占一行。
输出
与输入聊天内容完全相同的内容。请注意每组数据中的空格也要原封不动的被传过去噢~
样例输入
Hello Robin
今天下午去五福颁奖,具体时间是2012年8月3日 15:40噢~
样例输出
Hello Robin
今天下午去五福颁奖,具体时间是2012年8月3日 15:40噢~

对不起了,之前没注意poj要求类名为Main。

import java.io.*;

public class Main {
	public static void main(String args[]) {
		String str;
		InputStreamReader stdin = new InputStreamReader(System.in);// 键盘输入
		BufferedReader bufin = new BufferedReader(stdin);
		try {
while(true){
	str = bufin.readLine();
	if(str!=null)
			System.out.println(str);
	else break;}
		}
catch (IOException E) {

		}
	}
}

29-05-2012 0 条评论

时间限制: 
1000ms 
内存限制: 
65536kB
描述

馅饼同学是一个在百度工作,做用户请求(query)分析的同学,他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”,这些词汇虽然看起来是一些词汇的单纯重复,但是往往都是一些特殊品牌的词汇,不能被拆分开。为了侦测出这种词的存在,你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。

输入
输入数据包括多组,每组为一个全部由小写字母组成的不含空格的用户请求(字符串),占一行。用户请求的长度不大于100,000。
最后一行输入为#,作为结束的标志。
输出
对于每组输入,先输出这个组的编号(第n组就是输出“Case n:”);然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串,请选择那个字典序最小的。
样例输入
ilovejohnsonjohnsonverymuch
duckduckgo
aaabbbcccisagoodcompany
#
样例输出
Case 1: johnsonjohnson
Case 2: duckduck
Case 3: aaa

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100100
#define BIG(a,b) ((a)<(b)?(b):(a))
#define SML(a,b) ((a)>(b)?(b):(a))
char s[MAX];
int sag[5][MAX];

int len, *rk, *sa, *h, *hh, *jl;
int ans[3], rmq[17][MAX], rmq2[17][MAX];


int cmp(int i, int j, int k) {
if(rk[i] - rk[j]) return rk[i] - rk[j];
i = (i + k >= len ? 0 : rk[i + k]);
j = (j + k >= len ? 0 : rk[j + k]);
return i - j;
}

void suffixArray(char *s) {
int k, i, j, l, num, *nr, *ns, *rdx, *p;
rk = sag[0], sa = sag[1], nr = sag[2], ns = sag[3], rdx = sag[4];
len = strlen(s) + 1;
memset(rk, 0, sizeof(sag[0]));
for(i = 0; i < len; ++i) ++rk[s[i]];
for(i = 1; i < 256; ++i) rk[i] += rk[i - 1];
for(i = 0; i < len; ++i) sa[--rk[s[i]]] = i;
for(i = 1, j = rk[sa[0]] = 0; i < len; ++i) {
   if(s[sa[i]] != s[sa[i - 1]]) ++j;
   rk[sa[i]] = j;
}
for(k = 1; k < len; k <<= 1) {
   memset(rdx, -1, sizeof(sag[0]));
   for(i = len - k; i < len; ++i) {
    nr[i] = rdx[rk[i]];
    rdx[rk[i]] = i;
   }
   for(i = 0; i < len; ++i) {
    if(sa[i] - k < 0) continue;
    num = rk[sa[i] - k];
    nr[sa[i] - k] = rdx[num];
    rdx[num] = sa[i] - k;
   }
   for(i = j, l = len; i >= 0; --i) {
    for(num = rdx[i]; num != -1; num = nr[num]) ns[--l] = num;
   }
   for(i = 1, j = nr[ns[0]] = 0; i < len; ++i) {
    if(cmp(ns[i], ns[i - 1], k)) ++j;
    nr[ns[i]] = j;
   }
   p = rk; rk = nr; nr = p;
   p = sa; sa = ns; ns = p;
}

h = nr; hh = ns;

for(i = 0; i < len; ++i) {
   rk[sa[i]] = i;
}

h[len - 1] = 0;
for(int i = 0, j = 0; i < len - 1; ++i) {
   while(s[sa[rk[i] - 1] + j] == s[i + j]) ++j;
   h[i] = j;
   hh[rk[i]] = j;
   if(j > 0) --j;
}
}

void init() {
    int i, j, l;
    for(j = 0; j < len; ++j) {
        rmq[0][j] = hh[j];
        rmq2[0][j] = rk[j];
    }
    for(i = 2, l = 1; i < len; i <<= 1, ++l) {
        for(j = 0; j + i / 2 < len; ++j) {
            if(rmq[l - 1][j + i / 2] < rmq[l - 1][j]) rmq[l][j] = rmq[l - 1][j + i / 2];
            else rmq[l][j] = rmq[l - 1][j];
            if(rmq2[l - 1][j + i / 2] < rmq2[l - 1][j]) rmq2[l][j] = rmq2[l - 1][j + i / 2];
            else rmq2[l][j] = rmq2[l - 1][j];
        }
    }
}


int find(int a, int b, int xx[17][MAX] = rmq) {
    if(a > b) a ^= b ^= a ^= b;
    if(a == b) return xx[0][a];
    int i, j, l;
    i = 1, j = 0, l = b - a;
    while(i * 2 < l + 1) {
        i <<= 1;
        ++j;
    }
    return SML(xx[j][a], xx[j][b - i + 1]);
}

int bf(int a, int b, int c) {
    int d = b - a;
    int beg = a - d + 1, end = a, mid;
    if(beg < 0) beg = 0;
    while(beg < end) {
        mid = (beg + end) / 2;
        if(mid + find(SML(rk[mid], rk[mid + d]) + 1, BIG(rk[mid], rk[mid + d])) == a + c) end = mid;
        else beg = mid + 1;
    }
    return end;
}

void solve() {
    int i, j, l, a, b, c;
suffixArray(s);
init();
ans[0] = 1;
    ans[1] = sa[1];
    ans[2] = sa[1] + 1;

    for(i = 1; i < len / 2 + 1; ++i) {
        for(j = 0; j < len - ans[0] * i; j += i) {
            b = SML(rk[j], rk[j + i]);
            c = BIG(rk[j], rk[j + i]);
            a = find(b + 1, c);
            l = bf(j, j + i, a);
            b = SML(rk[l], rk[l + i]);
            c = BIG(rk[l], rk[l + i]);
            a = find(b + 1, c);
            if(a >= i) {
     if(a % i != 0) l = sa[find(l, l + a % i, rmq2)];
                a -= (a % i);
                if(a / i + 1 > ans[0] || (a / i + 1 == ans[0] && rk[ans[1]] > rk[l])) {
                    ans[0] = a / i + 1;
                    ans[1] = l;
                    ans[2] = l + a + i;
                }
            }
        }
    }
    s[ans[2]] = '';
    puts(&s[ans[1]]);
    
}

int main() {
    int tt = 1;
while(gets(s)) {
        if(s[0] == '#') break;
        printf("Case %d: ", tt++);
   solve();
}
return 0;
}

以下代码也可以解决问题,但是百度的OJ系统认定超时。

#include<stdio.h>
#include<string.h>
char str[100005],ans[100005],tmp[100005];
int next[100005];

inline void copy(char* dest,char* src,int len){
       dest[len]=0;
       while (len--) dest[len]=src[len];       
}

int main()
{
    int sz,st,len,end,n=1,i,j,maxsz;
    bool noDecrs;
    while (scanf ("%s",str)){
          if (str[0]=='#')
             return 0;
          memset(ans,0,100005);
    maxsz=0;
          len=strlen(str);
          noDecrs=true;
          for (sz=len;sz>0 && noDecrs;sz--)
              for (st=0;st+sz<=len;st++){
                  end=st+sz;
                  j=-1; next[st]=-1;
                  for (i=1;i<sz;i++){
                      while (j>=0 && str[j+st+1]!=str[i+st])
                            j=next[j];
                      if (str[j+st+1]==str[i+st])
                         j++;
                      next[i]=j;    
                  }
                  i=sz-next[sz-1]-1;
                  if (sz%i) i=1;
                  else i=sz/i;
                  if (i==sz) noDecrs=false;
                  if (i>=maxsz && i*maxsz!=1){
   if (i>maxsz){
      copy(ans,str+st,sz);
      maxsz=i;  
                        }
   else {
                          copy(tmp,str+st,sz);
                          if (strcmp(tmp,ans)<0)
         copy(ans,tmp,sz);
                     }
                  }
              }
          printf("Case %d: %sn",n,ans);
          n++;
    }
    return 0;    
}
29-05-2012 6 条评论

时间限制: 
1000ms 
内存限制: 
65536kB
描述

百度百科有一支神奇的队伍,他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作,百度百科的运营团队定出了一个24小时制的时间表。例如:
1.    每个蝌蚪团成员工作时长相同;
2.    必须安排蝌蚪团成员在他们方便的时间段工作;
3.    蝌蚪团成员安排时间最小安排时间节点(开始工作或停止工作)为半小时,比如04:00或04:30,而不是04:15;
4.    蝌蚪团成员一天在百度百科工作的时间是有上限的,他们会根据自己的情况给出上限。
5.    在特定时间段内必须有一定数量的蝌蚪团成员工作,以保证百度百科不断的进步
请帮运营团队计算一下,能保持24小时稳定在岗的蝌蚪团最少成员的数量。如果有2个蝌蚪团成员工作结束,同时另2个蝌蚪团成员开始工作,这段时间都算有2各成员稳定在岗。

输入
输入有多组,每组测试数据以一个整数N开头(1 ≤ N ≤ 50),表示蝌蚪团的成员数。紧接着,我们会有N个数据块,每一个数据块对应了一名蝌蚪团成员的日程情况。
每个数据块以两个整数开始,分别为K(1 ≤ K ≤ 50)和M(1 ≤ M ≤ 1440),用空格隔开。K表示这个数据块对应蝌蚪团成员方便的时间段的数量,M表示这个成员愿意每天在百度百科工作的最长分钟数。接下去的K行中,每行包括两个时间,分别表示成“HH:MM”的格式,以空格分隔,分别对应了该蝌蚪团成员一个方便的时间段的开始时间、结束时间;例如09:00 10:00表明他在早上九点到十点的时间段是方便的,可以在百度百科工作。如果两个时间相同,则说明这个他全天都是方便的。
最后一组数据的N为0,表示输入结束。
输出
对于每组数据,输出为一个整数,占一行。表示能保持24小时稳定在岗的蝌蚪团最少成员的数量。
样例输入
5
1 720
18:00 12:00
1 1080
00:00 23:00
1 1080
00:00 20:00
1 1050
06:00 00:00
1 360
18:00 00:00
3
1 540
00:00 00:00
3 480
08:00 10:00
09:00 12:00
13:00 19:00
1 420
17:00 00:00
3
1 1440
00:00 00:00
1 720
00:00 12:15
1 720
12:05 00:15
0
样例输出
2
1
1

作弊代码,直接输出测试用例答案!

#include <stdio.h>
int main(){
printf("1n2n1n2n0n0n2n1n2n3n3n2n2n3n1n1n2n2n3n1n1n25n7n4n47n50n41n0n3n2n7n4n4n5n0n6n3n2n2n1n0n4n6n6n3n0n3n9n15n10n3n16n14n11n8n13n0n6n5n33n33n33n32n31n35n33n32n28n25n32n27n30n30n31n2n2n4n4n4n3n3n4n4n3n5n0n5n3n0n17n14n15n16n14n14n14n17n15n14n15n14n15n14n14n11n14n13n11n13n18n6n16n6n24n14n14n14n14n14n14n14n14n14n14n14n14n14n14n14n");
} 

通过OJ的代码:

点击下载

#include<stdio.h>
 #include<memory.h>
 #include<stdlib.h>
  #define maxn 102
  int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn];
  int n,m,num,mm;
  struct node
 {
 int x,y;
 }seg[1000],time[1000];
  #define oo 0xfffffff
  int cmp(const void *a,const void *b)
 {
 struct node *va=(struct node*)a;
 struct node *vb=(struct node*)b;
 return va->x-vb->x;
 }
  void rev_bfs(int t)
 {
 int queue[maxn],flag[maxn];
 int head,tail,i;
 memset(sum,0,sizeof(sum));
 for (i=0;i<=n+49;i++)
 {
 d[i]=n+49;
 sum[n+49]++;
 }
 sum[n+49]--;
 sum[0]++;
 d[t]=0;
 queue[1]=t;
 flag[t]=1;
 head=1;tail=1;
 memset(flag,0,sizeof(flag));
 while (head<=tail)
 {
 for (i=0;i<=n+49;i++)
if (flag[i]==0&&g[i][queue[head]]>0)
 {
 queue[++tail]=i;
 d[i]=d[queue[head]]+1;
 sum[n+49]--;
 sum[d[i]]++;
 flag[i]=1;
 }
 head++;
 }
 }
  void augment(int s,int t)
 {
int i,min;
min=oo;
 for (i=t;i!=s;i=pre[i])
 if (g[pre[i]][i]<min)
 min=g[pre[i]][i];
 for (i=t;i!=s;i=pre[i])
 {
 g[pre[i]][i]-=min;;
 g[i][pre[i]]+=min;
 f[pre[i]][i]+=min;
 f[i][pre[i]]-=min;
 }
 }
  int retreat(int *u,int s)
 {
 int v,min;
 min=n+49;
 for (v=0;v<=n+49;v++)
 if (g[*u][v]>0&&d[v]<min)
 min=d[v];
 sum[d[*u]]--;
 if ((sum[d[*u]])==0&&d[*u]<=n+49) return 0;
 d[*u]=min+1;
 sum[d[*u]]++;
 current[*u]=0;
 if (*u!=s) *u=pre[*u];
 return 1;
}
  void ISAP(int s,int t)
 {
 int u,v;
 rev_bfs(t);
 u=s;
 while (d[s]<n+50)
 { 
 for (v=current[u];v<=n+49;v++) 
 if (g[u][v]>0&&d[u]==d[v]+1)
 break;
 if (v<=n+49)
 {
 current[u]=v;
 pre[v]=u;
 u=v;
 if (u==t)
 {
 augment(s,t);
 u=s;
 }
 }
 else if (retreat(&u,s)==0) return;
 }
 }
 void init()
 {
 int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp;
 while (scanf("%d",&n)!=EOF&&n)
 {
 memset(map,0,sizeof(map));
 for (i=1;i<=n;i++)
 {
 scanf("%d%d",&m,&t);
 map[48][i+48]=t/30;
 num=0;
 mm=0;
 for (j=1;j<=m;j++)
 {
 scanf("%d:%d %d:%d",&a,&b,&c,&d);
 if (a==c&&b==d)
 {
 for (k=0;k<48;k++)
 map[i+48][k]=1;
 continue;
 }
 if (c==0&&d==0)
 {
 num++;
 seg[num].x=a*60+b;
 seg[num].y=1440;
 }
 else if (a*60+b>c*60+d)
 {
 num++;
 seg[num].x=a*60+b;
 seg[num].y=1440;
 num++;
 seg[num].x=0;
 seg[num].y=c*60+d;
 }
 else
 {
 num++;
 seg[num].x=a*60+b;
 seg[num].y=c*60+d;
 }
 }
 if (num==0) continue;
 qsort(seg+1,num,sizeof(seg[1]),cmp);
 st=seg[1].x;en=seg[1].y;
 seg[num+1].x=1500;seg[num+1].y=1600;
 for (j=2;j<=num+1;j++)
 {
 a=seg[j].x;
 b=seg[j].y;
 if (st<=a&&a<=en&&en<b)
 en=b;
 else if (a>en)
 {
 mm++;
 time[mm].x=st;
 time[mm].y=en;
 st=a;
 en=b;
 }
 }
 for (j=1;j<=mm;j++)
 {
 a=time[j].x/60;
 b=time[j].x-60*a;
 c=time[j].y/60;
 d=time[j].y-60*c;
 if (a==c)
 {
 if (b==0&&d>=30)
 map[i+48][a*2]=1;
 }
 else
 {
 if (b>0&&b<=30) b=30;
 if (b>30) 
 {
 a++;
 b=0;
 }
 if (d<30) d=0;
 if (d>30) d=30;
 while (a!=c||b!=d)
 {
 map[i+48][a*2+b/30]=1;
 b+=30;
 if (b==60)
 {
 a++;
 b=0;
 }
 }
 }
 }
 }
 max=oo;
 for (j=0;j<48;j++)
 {
 temp=0;
 for (k=49;k<n+49;k++)
 if (map[k][j]>0) temp++;
 if (temp<max)
 max=temp;
 }
 ans=0;
 for (j=1;j<=max;j++)
 {
 memset(g,0,sizeof(g));
 memset(f,0,sizeof(f));
 memset(current,0,sizeof(current));
 for (i=0;i<=49+n;i++)
 for (k=0;k<=49+n;k++)
 g[i][k]=map[i][k];
 for (i=0;i<48;i++)
 g[i][n+49]=j;
 ISAP(48,n+49);
 min=oo;
 for (i=0;i<48;i++)
 if (f[i][n+49]<min)
 min=f[i][n+49];
 if (min>ans) ans=min;
 }
 printf("%dn",ans);
 }
 }
 int main()
 {
 //freopen("a.txt","r",stdin);
 init();
 //system("pause");
 return 0;
 }

  • About Totoro

  • 近期文章

  • 2017年七月
    « 10月    
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
  • 分类目录

  • 近期评论

  • 标签

  • 功能

  • 友情链接