2013编程之美资格赛之树上的三角形(Java实现)

本文涉及的产品
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
简介: 树上的三角形 时间限制: 2000ms 内存限制: 256MB 描述 有一棵树,树上有只毛毛虫。它在这棵树上生活了很久,对它的构造了如指掌。所以它在树上从来都是走最短路,不会绕路。它还还特别喜欢三角形,所以当它在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢? 输入 输入数据的第一行包含一个整数 T,表示数据组数。 接下
树上的三角形


时间限制: 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


主要算法:
define results
get T
for 1 to T
get N
for 1 to N-1
get 边
getStruct 边s //构造类树
get M
define result
for 1 to M
get S,E
get S,E 到树根的路劲
get S,E 到树根的路劲的非公共节点
get S,E 间的路劲
get values S,E间路劲的段长度集合
sort(values)
result+=Test values //测试是否为三角形
results add result
print results


Test 算法
for i=2 to values.length
if values[i-2]+vaules[i-1]>values[i]
return true
return false


程序:


import java.util.*;

public class Main {

	public static void main(String[] args){
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		
		String[] results=new String[T];
		for(int i=0;i<T;i++){
			int N=sc.nextInt();			
			int tempN=N-1;
			int[][] nodes=new int[tempN][3];
			for(int j=0;j<tempN;j++){
				nodes[j][0]=sc.nextInt();
				nodes[j][1]=sc.nextInt();
				nodes[j][2]=sc.nextInt();
			}
			List<ArrayList<Integer>> struct=getStruct(nodes);
			int M=sc.nextInt();
			String result="";
			for(int j=0;j<M;j++){
				int start=sc.nextInt();
				int end=sc.nextInt();
				result=result+" "+getResult(start,end,struct,nodes);
			}
			results[i]=result.trim();
		}
		
		printResult(results);
	}

	private static List<ArrayList<Integer>> getStruct(int[][] nodes) {
		ArrayList<Integer> num01s=new ArrayList<Integer>(nodes.length);
		int[] temp=new int[nodes.length+1];
		for(int i=0;i<temp.length;i++){
			temp[i]=0;
		}
		for(int i=0;i<nodes.length;i++){
			temp[(nodes[i][0]-1)]++;
			temp[(nodes[i][1]-1)]++;
		}
		for(int i=0;i<temp.length;i++){
			if(temp[i]==1)
				num01s.add(i+1);
		}
		int structLength=num01s.size()-1;
		List<ArrayList<Integer>> struct=new ArrayList<ArrayList<Integer>>(structLength);
		
		boolean[] flags=new boolean[structLength+1];
		for(int i=0;i<flags.length;i++){
			flags[i]=true;
		}
		List<Integer> success=new ArrayList<Integer>(nodes.length+1);
		for(int i=0;i<structLength;i++){
			ArrayList<Integer> list=new ArrayList<Integer>(nodes.length+1);
			for(int j=0;j<flags.length;j++){
				if(flags[j]){
					flags[j]=false;
					list.add(num01s.get(j));
					success.add(num01s.get(j));
					break;
				}
			}
			int node=list.get(0);
			boolean flag=true;
			while(flag){
				for(int k=0;k<nodes.length;k++){
					if((node==nodes[k][0])&&(!success.contains(nodes[k][1]))){
						list.add(nodes[k][1]);
						node=nodes[k][1];
						success.add(node);
						break;
					}else if((node==nodes[k][1])&&(!success.contains(nodes[k][0]))){
						list.add(nodes[k][0]);
						node=nodes[k][0];
						success.add(node);
						break;
					}
				}
				if(i!=0){
					int add=list.get(list.size()-1);
					for(int suc:success){
						for(int j=0;j<nodes.length;j++){
							if((suc==nodes[j][0] && add==nodes[j][1])||(suc==nodes[j][1] && add==nodes[j][0])){
								if(!list.contains(suc)){
									list.add(suc);
									flag=false;
									list=swap(list);
									break;
								}
							}
						}
					}
				}
				if(num01s.contains(node)){
					flags[num01s.indexOf(node)]=false;
					flag=false;
				}
			}
			struct.add(list);
		}
		return struct;
	}


	private static ArrayList<Integer> swap(ArrayList<Integer> list) {
		ArrayList<Integer> temp=new ArrayList<Integer>(list.size());
		for(int i=list.size()-1;i>=0;i--){
			temp.add(list.get(i));
		}
		return temp;
	}

	private static String getResult(int start, int end,
			List<ArrayList<Integer>> struct, int[][] nodes) {
		ArrayList<Integer> startPath=getNodePath(start,struct);
		ArrayList<Integer> endPath=getNodePath(end,struct);
		ArrayList<Integer> SE=new ArrayList<Integer>(nodes.length+1);
		int common=getCommonNode(startPath,endPath);
		if(startPath.indexOf(common)==0){
			SE=getPath(common,endPath);
		}else if( endPath.indexOf(common)==0){
			SE=getPath(common,startPath);
		}else {
			SE=getPath(common,startPath,endPath);
		}
		
		int[] values=getValue(SE,nodes);
		sort(values);
		return echo(values);
	}

	private static ArrayList<Integer> getPath(int common,
			ArrayList<Integer> list) {
		ArrayList<Integer> l=new ArrayList<Integer>(list.size());
		int n=list.indexOf(common);
		for(int i=0;i<=n;i++){
			l.add(list.get(i));
		}
		return l;
	}

	private static void sort(int[] values) {
		for(int i=0;i<values.length;i++){
			int min=i;
			for(int j=i+1;j<values.length;j++){
				if(values[j]<values[min])
					min=j;
			}
			if(i!=min){
				int temp=values[i];
				values[i]=values[min];
				values[min]=temp;
			}
		}
	}

	private static String echo(int[] values) {
		if(values.length<3)
			return "No";
		String result="No";
		for(int i=2;i<values.length;i++){
			if(judge(values[i-2],values[i-1],values[i])){
				result="Yes";
				break;
			}
		}
		return result;
	}

	private static boolean judge(int i, int j, int k) {
		return ((i+j)>k);
	}

	private static int[] getValue(ArrayList<Integer> sE,int[][] nodes) {
		int[] values=new int[sE.size()-1];
		for(int i=0;i<values.length;i++){
			for(int j=0;j<nodes.length;j++){
				int x=sE.get(i);
				int y=sE.get(i+1);
				if(nodes[j][0]==x && nodes[j][1]==y){
					values[i]=nodes[j][2];
					break;
				}else if (nodes[j][1]==x && nodes[j][0]==y){
					values[i]=nodes[j][2];
					break;
				}
			}
		}
		return values;
	}

	private static ArrayList<Integer> getPath(int m, 
			ArrayList<Integer> xList, ArrayList<Integer> yList) {
		ArrayList<Integer> path=new ArrayList<Integer>(xList.size()+yList.size());
		int xindex=xList.indexOf(m);
		int yindex=yList.indexOf(m);
		for(int i=0;i<xindex;i++){
			path.add(xList.get(i));
		}
		for(int i=yindex;i>=0;i--){
			path.add(yList.get(i));
		}
		return path;
	}

	private static int getCommonNode(ArrayList<Integer> xList,
			ArrayList<Integer> yList) {
		int max=xList.size();
		int c=-1;
		for(int i=0;i<max;i++){
			int temp=xList.get(i);
			if(yList.contains(temp)){
				c=temp;
				break;
			}
		}
		return c;
	}

	private static ArrayList<Integer> getNodePath(int start,
			List<ArrayList<Integer>> struct) {
		ArrayList<Integer> temp=new ArrayList<Integer>();
		temp.add(start);
		int s=start;
		int head=struct.get(0).get(0);
		int slength=struct.size();
		boolean flag=true;
		while(flag){
			for(int i=0;i<slength;i++){
				if(struct.get(i).contains(s) && s!=struct.get(i).get(0)){
					int x=struct.get(i).indexOf(s);
					
					for(int j=(x-1);j>=0;j--){
						temp.add(struct.get(i).get(j));
					}
					s=struct.get(i).get(0);
					break;
				}
			}
			if(head==s){
				flag=false;
			}
		}
		return temp;
	}

	private static void printResult(String[] result) {
		
		for(int i=0;i<result.length;i++){
		
			System.out.println("Case #"+(i+1)+":");
			
			String[] words=result[i].split(" ");
			for(String word:words)
				System.out.println(word);
		}
	}
}

这也是同样了,通过了比赛系统小数据测试,大数据测试未知。

——20130408



PS:

今天早晨数据出来了,这道题的大数据测试时TLE,超时。在情理之中。原因见博文《2013编程之美资格赛之大数据测试(Java实现)》

——20130409

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
相关文章
|
2天前
|
存储 Java
JAVA并发编程AQS原理剖析
很多小朋友面试时候,面试官考察并发编程部分,都会被问:说一下AQS原理。面对并发编程基础和面试经验,专栏采用通俗简洁无废话无八股文方式,已陆续梳理分享了《一文看懂全部锁机制》、《JUC包之CAS原理》、《volatile核心原理》、《synchronized全能王的原理》,希望可以帮到大家巩固相关核心技术原理。今天我们聊聊AQS....
|
2天前
|
Java 程序员 数据库连接
Java编程中的异常处理:从基础到进阶
【9月更文挑战第18天】在Java的世界里,异常处理是每个程序员必须面对的挑战。本文将带你从异常的基本概念出发,通过实际的代码示例,深入探讨如何有效地管理和处理异常。我们将一起学习如何使用try-catch块来捕捉异常,理解finally块的重要性,以及如何自定义异常类来满足特定需求。无论你是初学者还是有经验的开发者,这篇文章都将为你提供新的见解和技巧,让你的Java代码更加健壮和可靠。
|
2天前
|
Java 数据库连接 UED
掌握Java编程中的异常处理
【9月更文挑战第18天】在Java的世界中,异常是那些不请自来的客人,它们可能在任何时候突然造访。本文将带你走进Java的异常处理机制,学习如何优雅地应对这些突如其来的“访客”。从基本的try-catch语句到更复杂的自定义异常,我们将一步步深入,确保你能够在面对异常时,不仅能够从容应对,还能从中学到宝贵的经验。让我们一起探索如何在Java代码中实现健壮的异常处理策略,保证程序的稳定运行。
|
2天前
|
Java 数据库
JAVA并发编程-一文看懂全部锁机制
曾几何时,面试官问:java都有哪些锁?小白,一脸无辜:用过的有synchronized,其他不清楚。面试官:回去等通知! 今天我们庖丁解牛说说,各种锁有什么区别、什么场景可以用,通俗直白的分析,让小白再也不怕面试官八股文拷打。
|
2天前
|
安全 Java 调度
Java 并发编程中的线程安全和性能优化
本文将深入探讨Java并发编程中的关键概念,包括线程安全、同步机制以及性能优化。我们将从基础入手,逐步解析高级技术,并通过实例展示如何在实际开发中应用这些知识。阅读完本文后,读者将对如何在多线程环境中编写高效且安全的Java代码有一个全面的了解。
|
1天前
|
Java
JAVA并发编程ReentrantLock核心原理剖析
本文介绍了Java并发编程中ReentrantLock的重要性和优势,详细解析了其原理及源码实现。ReentrantLock作为一种可重入锁,弥补了synchronized的不足,如支持公平锁与非公平锁、响应中断等。文章通过源码分析,展示了ReentrantLock如何基于AQS实现公平锁和非公平锁,并解释了两者的具体实现过程。
|
2天前
|
Kubernetes Cloud Native Java
探索未来编程新纪元:Quarkus带你秒建高性能Kubernetes原生Java应用,云原生时代的技术狂欢!
Quarkus 是专为 Kubernetes 设计的全栈云原生 Java 框架,凭借其轻量级、快速启动及高效执行特性,在 Java 社区脱颖而出。通过编译时优化与原生镜像支持,Quarkus 提升了应用性能,同时保持了 Java 的熟悉度与灵活性。本文将指导你从创建项目、编写 REST 控制器到构建与部署 Kubernetes 原生镜像的全过程,让你快速上手 Quarkus,体验高效开发与部署的乐趣。
8 0
时间轮-Java实现篇
在前面的文章《[时间轮-理论篇](https://developer.aliyun.com/article/910513)》讲了时间轮的一些理论知识,然后根据理论知识。我们自己来实现一个简单的时间轮。
|
6天前
|
存储 缓存 安全
【Java面试题汇总】多线程、JUC、锁篇(2023版)
线程和进程的区别、CAS的ABA问题、AQS、哪些地方使用了CAS、怎么保证线程安全、线程同步方式、synchronized的用法及原理、Lock、volatile、线程的六个状态、ThreadLocal、线程通信方式、创建方式、两种创建线程池的方法、线程池设置合适的线程数、线程安全的集合?ConcurrentHashMap、JUC
【Java面试题汇总】多线程、JUC、锁篇(2023版)
|
17天前
|
监控 Java 调度
【Java学习】多线程&JUC万字超详解
本文详细介绍了多线程的概念和三种实现方式,还有一些常见的成员方法,CPU的调动方式,多线程的生命周期,还有线程安全问题,锁和死锁的概念,以及等待唤醒机制,阻塞队列,多线程的六种状态,线程池等
79 6
【Java学习】多线程&JUC万字超详解