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;
}
02-06-2012 0 条评论

Java路径

Java中使用的路径,分为两种:绝对路径和相对路径。具体而言,又分为四种:

一、URI形式的绝对资源路径

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/aaa.b

URL是URI的特例。URL的前缀/协议,必须是Java认识的。URL可以打开资源,而URI则不行。

URL和URI对象可以互相转换,使用各自的toURI(),toURL()方法即可!

二、本地系统的绝对路径

D:/java/eclipse32/workspace/jbpmtest3/bin/aaa.b

Java.io包中的类,需要使用这种形式的参数。

但是,它们一般也提供了URI类型的参数,而URI类型的参数,接受的是URI样式的String。因此,通过URI转换,还是可以把URI样式的绝对路径用在java.io包中的类中。

三、相对于classpath的相对路径

如:相对于

file:/D:/java/eclipse32/workspace/jbpmtest3/bin/这个路径的相对路径。其中,bin是本项目的classpath。所有的Java源文件编译后的.class文件复制到这个目录中。

四、相对于当前用户目录的相对路径

就是相对于System.getProperty("user.dir")返回的路径。

对于一般项目,这是项目的根路径。对于JavaEE服务器,这可能是服务器的某个路径。这个并没有统一的规范!

所以,绝对不要使用“相对于当前用户目录的相对路径”。然而:

默认情况下,java.io 包中的类总是根据当前用户目录来分析相对路径名。此目录由系统属性 user.dir 指定,通常是 Java 虚拟机的调用目录。

这就是说,在使用java.io包中的类时,最好不要使用相对路径。否则,虽然在J2SE应用程序中可能还算正常,但是到了J2EE程序中,一定会出问题!而且这个路径,在不同的服务器中都是不同的!

相对路径最佳实践

推荐使用相对于当前classpath的相对路径

因此,我们在使用相对路径时,应当使用相对于当前classpath的相对路径。

ClassLoader类的getResource(String name),getResourceAsStream(String name)等方法,使用相对于当前项目的classpath的相对路径来查找资源。

读取属性文件常用到的ResourceBundle类的getBundle(String path)也是如此。

通过查看ClassLoader类及其相关类的源代码,我发现,它实际上还是使用了URI形式的绝对路径。通过得到当前classpath的URI形式的绝对路径,构建了相对路径的URI形式的绝对路径。(这个实际上是猜想,因为JDK内部调用了SUN的源代码,而这些代码不属于JDK,不是开源的。)

相对路径本质上还是绝对路径

因此,归根结底,Java本质上只能使用绝对路径来寻找资源。所有的相对路径寻找资源的方法,都不过是一些便利方法。不过是API在底层帮助我们构建了绝对路径,从而找到资源的!

得到classpath和当前类的绝对路径的一些方法

下面是一些得到classpath和当前类的绝对路径的一些方法。你可能需要使用其中的一些方法来得到你需要的资源的绝对路径。

1,FileTest.class.getResource("")

得到的是当前类FileTest.class文件的URI目录。不包括自己!

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/com/test/

2,FileTest.class.getResource("/")

得到的是当前的classpath的绝对URI路径。

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/

3,Thread.currentThread().getContextClassLoader().getResource("")

得到的也是当前ClassPath的绝对URI路径。

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/

4,FileTest.class.getClassLoader().getResource("")

得到的也是当前ClassPath的绝对URI路径。

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/

5,ClassLoader.getSystemResource("")

得到的也是当前ClassPath的绝对URI路径。

如:file:/D:/java/eclipse32/workspace/jbpmtest3/bin/

推荐使用Thread.currentThread().getContextClassLoader().getResource("")来得到当前的classpath的绝对路径的URI表示法。

Web应用程序中资源的寻址

上文中说过,当前用户目录,即相对于System.getProperty("user.dir")返回的路径。

对于JavaEE服务器,这可能是服务器的某个路径,这个并没有统一的规范!

而不是我们发布的Web应用程序的根目录!

这样,在Web应用程序中,我们绝对不能使用相对于当前用户目录的相对路径。

在Web应用程序中,我们一般通过ServletContext.getRealPath("/")方法得到Web应用程序的根目录的绝对路径。

这样,我们只需要提供相对于Web应用程序根目录的路径,就可以构建出定位资源的绝对路径。

这是我们开发Web应用程序时一般所采取的策略。

通用的相对路径解决办法

Java中各种相对路径非常多,不容易使用,非常容易出错。因此,我编写了一个便利方法,帮助更容易的解决相对路径问题。

Web应用程序中使用JavaSE运行的资源寻址问题

在JavaSE程序中,我们一般使用classpath来作为存放资源的目的地。但是,在Web应用程序中,我们一般使用classpath外面的WEB-INF及其子目录作为资源文件的存放地。

在Web应用程序中,我们一般通过ServletContext.getRealPath("/")方法得到Web应用程序的根目录的绝对路径。这样,我们只需要提供相对于Web应用程序根目录的路径,就可以构建出定位资源的绝对路径。

Web应用程序,可以作为Web应用程序进行发布和运行。但是,我们也常常会以JavaSE的方式来运行Web应用程序的某个类的main方法。或者,使用JUnit测试。这都需要使用JavaSE的方式来运行。

这样,我们就无法使用ServletContext.getRealPath("/")方法得到Web应用程序的根目录的绝对路径。

而JDK提供的ClassLoader类,

它的getResource(String name),getResourceAsStream(String name)等方法,使用相对于当前项目的classpath的相对路径来查找资源。

读取属性文件常用到的ResourceBundle类的getBundle(String path)也是如此。

它们都只能使用相对路径来读取classpath下的资源,无法定位到classpath外面的资源。

Classpath外配置文件读取问题

如,我们使用测试驱动开发的方法,开发Spring、Hibernate、iBatis等使用配置文件的Web应用程序,就会遇到问题。

尽管Spring自己提供了FileSystem(也就是相对于user,dir目录)来读取Web配置文件的方法,但是终究不是很方便。而且与Web程序中的代码使用方式不一致!

至于Hibernate,iBatis就更麻烦了!只有把配置文件移到classpath下,否则根本不可能使用测试驱动开发!

怎么办?

通用的相对路径解决办法

面对这个问题,我决定编写一个助手类ClassLoaderUtil,提供一个便利方法[public static URL getExtendResource(String relativePath)]。在Web应用程序等一切Java程序中,需要定位classpath外的资源时,都使用这个助手类的便利方法,而不使用Web应用程序特有的ServletContext.getRealPath("/")方法来定位资源。

利用classpath的绝对路径,定位所有资源

这个便利方法的实现原理,就是“利用classpath的绝对路径,定位所有资源”。

ClassLoader类的getResource("")方法能够得到当前classpath的绝对路径,这是所有Java程序都拥有的能力,具有最大的适应性!

而目前的JDK提供的ClassLoader类的getResource(String 相对路径)方法,只能接受一般的相对路径。这样,使用ClassLoader类的getResource(String 相对路径)方法就只能定位到classpath下的资源。

如果,它能够接受“../”这样的参数,允许我们用相对路径来定位classpath外面的资源,那么我们就可以定位位置的资源!

当然,我无法修改ClassLoader类的这个方法,于是,我编写了一个助手类ClassLoaderUtil类,提供了[public static URL getExtendResource(String relativePath)]这个方法。它能够接受带有“../”符号的相对路径,实现了自由寻找资源的功能。

通过相对classpath路径实现自由寻找资源的助手类的源代码:

import java.io.IOException;
                        import java.io.InputStream;
                        import java.net.MalformedURLException;
                        import java.net.URL;
                        import java.util.Properties;
                        import org.apache.commons.logging.Log;
                        import org.apache.commons.logging.LogFactory;
                        /**
                        *@author沈东良shendl_s@hotmail.com
                        *Nov29,2006 10:34:34AM
                        *用来加载类,classpath下的资源文件,属性文件等。
                        *getExtendResource(StringrelativePath)方法,
                        *可以使用../符号来加载classpath外部的资源。
                        */
                        publicclass ClassLoaderUtil {
                        privatestatic Log log=LogFactory.getLog(ClassLoaderUtil.class);
                        /**
                        *Thread.currentThread().getContextClassLoader().getResource("")
                        */
                        /**
                        *加载Java类。 使用全限定类名
                        *@paramclassName
                        *@return
                        */
                        publicstatic Class loadClass(String className) {
                        try {
                        return getClassLoader().loadClass(className);
                        } catch (ClassNotFoundException e) {
                        thrownew RuntimeException("class not found '"+className+"'", e);
                        }
                        }
                        /**
                        *得到类加载器
                        *@return
                        */
                        publicstatic ClassLoader getClassLoader() {
                        return ClassLoaderUtil.class.getClassLoader();
                        }
                        /**
                        *提供相对于classpath的资源路径,返回文件的输入流
                        *@paramrelativePath必须传递资源的相对路径。
                        *@是相对于classpath的路径。
                        *@如果需要查找classpath外部的资源,需要使用../来查找
                        *@return 文件输入流
                        *@throwsIOException
                        *@throwsMalformedURLException
                        */
                        publicstatic InputStream getStream(String relativePath)
                        throws MalformedURLException, IOException {
                        if(!relativePath.contains("../")){
                        return getClassLoader().getResourceAsStream(relativePath);
                        }else{
                        return ClassLoaderUtil.getStreamByExtendResource(relativePath);
                        }
                        }
                        /**
                        *
                        *@paramurl
                        *@return
                        *@throwsIOException
                        */
                        publicstatic InputStream getStream(URL url) throws IOException{
                        if(url!=null){
                        return url.openStream();
                        }else{
                        returnnull;
                        }
                        }
                        /**
                        *
                        *@paramrelativePath必须传递资源的相对路径。是相对于classpath的路径。
                        *@如果需要查找classpath外部的资源,需要使用../来查找
                        *@return
                        *@throwsMalformedURLException
                        *@throwsIOException
                        */
                        publicstatic InputStream getStreamByExtendResource(String relativePath)
                        throws MalformedURLException, IOException{
                        return ClassLoaderUtil.getStream(
                        ClassLoaderUtil.getExtendResource(relativePath));
                        }
                        /**
                        *提供相对于classpath的资源路径,返回属性对象,它是一个散列表
                        *@paramresource
                        *@return
                        */
                        publicstatic Properties getProperties(String resource) {
                        Properties properties = new Properties();
                        try {
                        properties.load(getStream(resource));
                        } catch (IOException e) {
                        thrownew RuntimeException("couldn't load properties file'"+resource+"'",e);
                        }
                        return properties;
                        }
                        /**
                        *得到本Class所在的ClassLoader的Classpat的绝对路径。
                        *URL形式的
                        *@return
                        */
                        publicstatic String getAbsolutePathOfClassLoaderClassPath(){
                        ClassLoaderUtil.log.info(
                        ClassLoaderUtil.getClassLoader().getResource("").toString());
                        return ClassLoaderUtil.getClassLoader().getResource("").toString();
                        }
                        /**
                        *
                        *@paramrelativePath 必须传递资源的相对路径。是相对于classpath的路径。
                        *@如果需要查找classpath外部的资源,需要使用../来查找
                        *@return资源的绝对URL
                        *@throwsMalformedURLException
                        */
                        publicstatic URL getExtendResource(String relativePath)
                        throws MalformedURLException{
                        ClassLoaderUtil.log.info("传入的相对路径:"+relativePath) ;
                        //ClassLoaderUtil.log.info(Integer.valueOf(relativePath.indexOf("../"))) ;
                        if(!relativePath.contains("../")){
                        return ClassLoaderUtil.getResource(relativePath);
                        }
                        String classPathAbsolutePath=ClassLoaderUtil.getAbsolutePathOfClassLoaderClassPath();
                        if(relativePath.substring(0, 1).equals("/")){
                        relativePath=relativePath.substring(1);
                        }
                        ClassLoaderUtil.log.info(Integer.valueOf(relativePath.lastIndexOf("../"))) ;
                        String wildcardString=relativePath.substring(
                        0,relativePath.lastIndexOf("../")+3);
                        relativePath=relativePath.substring(relativePath.lastIndexOf("../")+3);
                        int containSum=ClassLoaderUtil.containSum(wildcardString, "../");
                        classPathAbsolutePath= ClassLoaderUtil.cutLastString(
                        classPathAbsolutePath, "/", containSum);
                        String resourceAbsolutePath=classPathAbsolutePath+relativePath;
                        ClassLoaderUtil.log.info("绝对路径:"+resourceAbsolutePath) ;
                        URL resourceAbsoluteURL=new URL(resourceAbsolutePath);
                        return resourceAbsoluteURL;
                        }
                        /**
                        *
                        *@paramsource
                        *@paramdest
                        *@return
                        */
                        privatestaticint containSum(String source,String dest){
                        int containSum=0;
                        int destLength=dest.length();
                        while(source.contains(dest)){
                        containSum=containSum+1;
                        source=source.substring(destLength);
                        }
                        return containSum;
                        }
                        /**
                        *
                        *@paramsource
                        *@paramdest
                        *@paramnum
                        *@return
                        */
                        privatestatic String cutLastString(String source,String dest,int num){
                        // String cutSource=null;
                        for(int i=0;i<num;i++){
                        source=source.substring(0, source.lastIndexOf(dest, source.length()-2)+1);
                        }
                        return source;
                        }
                        /**
                        *
                        *@paramresource
                        *@return
                        */
                        publicstatic URL getResource(String resource){
                        ClassLoaderUtil.log.info("传入的相对于classpath的路径:"+resource) ;
                        return ClassLoaderUtil.getClassLoader().getResource(resource);
                        }
                        /**
                        *@paramargs
                        *@throwsMalformedURLException
                        */
                        publicstaticvoid main(String[] args)
                        throws MalformedURLException {
                        //ClassLoaderUtil.getExtendResource("../spring/dao.xml");
                        //ClassLoaderUtil.getExtendResource("../../../src/log4j.properties");
                        ClassLoaderUtil.getExtendResource("log4j.properties");
                        System.out.println(
                        ClassLoaderUtil.getClassLoader().getResource("log4j.properties").toString());
                        }
                        }

后记

ClassLoaderUtil类的public static URL getExtendResource(String relativePath),虽然很简单,但是确实可以解决大问题。

不过这个方法还是比较简陋的。我还想在未来有空时,进一步增强它的能力。比如,增加Ant风格的匹配符。用**代表多个目录,*代表多个字符,?代表一个字符。达到Spring那样的能力,一次返回多个资源的URL,进一步方便大家开发。

总结:

1.尽量不要使用相对于System.getProperty("user.dir")当前用户目录的相对路径。这是一颗定时炸弹,随时可能要你的命。

2.尽量使用URI形式的绝对路径资源。它可以很容易的转变为URI,URL,File对象。

3.尽量使用相对classpath的相对路径。不要使用绝对路径。使用上面ClassLoaderUtil类的public static URL getExtendResource(String relativePath)方法已经能够使用相对于classpath的相对路径定位所有位置的资源。

4.绝对不要使用硬编码的绝对路径。因为,我们完全可以使用ClassLoader类的getResource("")方法得到当前classpath的绝对路径。

使用硬编码的绝对路径是完全没有必要的!它一定会让你死的很难看!程序将无法移植!

如果你一定要指定一个绝对路径,那么使用配置文件,也比硬编码要好得多!

当然,我还是推荐你使用程序得到classpath的绝对路径来拼资源的绝对路径!

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

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

在百度之星的贴吧里面,Java的爱好者和C++的爱好者总是能为这两种语言哪个更好争论上几个小时。Java的爱好者会说他们的程序更加整洁且不易出错。C++的爱好者则会嘲笑Java程序很慢而且代码很长。
另一个Java和C++爱好者不能达成一致的争论点就是命名问题。在Java中一个多个单词构成的变量名应该按照如下格式命名:第一个单词的开头用小写字母,其余单词都以大写字母开头,单词与单词之间不加分隔符,除单词的首字母之外的字母一律使用小写。例如:javaIdentifier, longAndMnemonicIdentifier, name, bAIDU.
与Java不同C++的命名全都使用小写字母,在单词和单词之间使用“_”来作为分隔符。例如:c_identifier, long_and_mnemonic_identifier, name (当名字中只有一个单词的时候,Java与C++的命名是相同的), b_a_i_d_u.
你的任务就是写一个程序能让C++和Java程序相互转化。当然转换完成的程序中的变量名也要符合其语言的命名规则,否则的话是不会有人喜欢你的转换器的。
首先你要做的就是写一个变量名转换器。给出一个变量名,你要先检测是Java的还是C++的,然后把它转化为另一种命名格式。如果两种都不是,那么你的程序就要报错。转换过程必须保持原有的单词顺序,只能改变字母的大小写和增加或删除下划线。

输入
输入有且仅有一行,是一个变量名,其中包含字母和下划线,长度不超过100。
输出
如果输入的是Java变量名那么输出它对应的C++形式。如果是C++的则输出对应的Java的形式。如果两种都不是就输出“Error!”。
样例输入
输入样例1:
long_and_mnemonic_identifier
输入样例2:
anotherExample
输入样例3:
i
输入样例4:
bad_Style
样例输出
输出样例1:
longAndMnemonicIdentifier
输出样例2:
another_example
输出样例3:
i
输出样例4:
Error!

需要注意的:

1)黑体字不是输入输出;

2)必须小写字母开头

3)不能有连续_

4)字符串最后不能是_

#include <iostream>
using namespace std;
int main(){
char name[200];
int flagJ=0;
int flagC=0;
int i,j;
char temp1,temp2;
cin>>name;
if(!(name[0]>='a'&&name[0]<='z')){
 flagC=1;
 flagJ=1;
for(i=0;name[i]!='';i++){
if(name[i]=='_'){
for(j=i;name[j+1]!='';j++){
name[j]=name[j+1];
}
name[j]='';
if((name[i]>='A'&&name[i]<='Z')||name[i]==''||name[i]=='_')
flagJ++;
name[i]=name[i]-'a'+'A';
flagC++;
continue;
if(name[i]>='A'&&name[i]<='Z')
{
  temp2=name[i];                 
for(j=i;name[j]!='';j++){
temp1=name[j+1];
name[j+1]=temp2;
temp2=temp1;
}
name[i]='_';
name[i+1]=name[i+1]-'A'+'a';
flagJ++;
i++;
continue;
}
}
if((flagJ>0&&flagC==0)||(flagJ==0&&flagC>0)||(flagJ==0&&flagC==0))
for(i=0;name[i]!='';i++)
cout<<name[i];
else cout<<"Error!";
return 0;

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		while(cin.hasNext())
		{
			String str = cin.nextLine();
	
			int type = checkType(str);
			if(type == -1)
				System.out.println("Error!");
			else if(type == 1)
			{
				StringBuffer sb = new StringBuffer();
				while(str.indexOf("_") != -1)
				{
					int index = str.indexOf("_");
					sb.append(str.substring(0, index));
					if(index != 0)
					{
						String tmp = str.substring(index+1);
						str = FUpper(tmp);
					}else
						str = str.substring(index+1);
					
				}
				sb.append(str);
				System.out.println(sb.toString());
			}
			else if(type == 2)
			{
				StringBuffer sb = new StringBuffer();
				for(int i = 0; i < str.length(); i++)
				{
					char c = str.charAt(i);
					if(c >= 97 && c <= 122)
					{
						sb.append(c);
					}else if(c >= 65 && c <= 90)
					{
						sb.append('_');
						sb.append((char)(c+32));
					}
				}
				System.out.println(sb.toString());
			}
				
		}

	}
	
	private static String FUpper(String str)
	{
		StringBuffer sb = new StringBuffer();
		
		sb.append((char)(str.charAt(0) - 32));
		if(str.length() > 1)
			sb.append(str.substring(1));
		return sb.toString();
	}
	
	private static int checkType(String str)
	{
		if(str.endsWith("_"))
			return -1;
		if(str.startsWith("_"))
			return -1;
		
		if(str.indexOf("_") != -1)
		{			
			for(int i = 0; i < str.length(); i++)
			{
				if((str.charAt(i) + 0) >= 65 && (str.charAt(i) + 0) <= 90)
					return -1;
				if(str.charAt(i) == '_' && i != 0 && i != str.length()-1)
					if(str.charAt(i-1) == '_' || str.charAt(i+1) == '_')
						return -1;
			}
			
			return 1;
		}
	
		if(str.charAt(0) >= 65 && str.charAt(0) <= 90)
			return -1;

		return 2;
	}
}

  • About Totoro

  • 近期文章

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

  • 近期评论

  • 标签

  • 功能

  • 友情链接