- 浏览: 611857 次
- 来自: ...
-
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ1696题意:
一只很特殊的蚂蚁,只能向坐转,并且不能经过已经走过的路。一张地图上有n个食物让蚂蚁去采集,求蚂蚁经过所有食物的顺序(找出一条最长的非右拐的路径)。
样例:
Sample Input
2 (二次测试)
10 (十个食物点)
1 4 5 (点的编号,x坐标,y坐标)
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
分析:
每次找到一个基准点p0,最开始的时候是最左下角的点,然后我们再从未访问的点中找到相对于p0最小极角的那个点,比较极角用叉积来计算,每次迭代总是用此次循环中找到的最小极角来代替p0,然后再以这个新的p0,找到剩下的点中的最小极角,这样我们找到的就是一条最大的不右转的路径了。
下面是AC过的代码:
源码下载:
一只很特殊的蚂蚁,只能向坐转,并且不能经过已经走过的路。一张地图上有n个食物让蚂蚁去采集,求蚂蚁经过所有食物的顺序(找出一条最长的非右拐的路径)。

样例:
Sample Input
2 (二次测试)
10 (十个食物点)
1 4 5 (点的编号,x坐标,y坐标)
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
分析:
每次找到一个基准点p0,最开始的时候是最左下角的点,然后我们再从未访问的点中找到相对于p0最小极角的那个点,比较极角用叉积来计算,每次迭代总是用此次循环中找到的最小极角来代替p0,然后再以这个新的p0,找到剩下的点中的最小极角,这样我们找到的就是一条最大的不右转的路径了。
下面是AC过的代码:
import java.util.Scanner; import java.util.Arrays; class point implements Comparable { int id ;//食物原始的编号 int ord ;//蚂蚁经过的顺序 double x;//食物的x坐标 double y;//食物的y坐标 public int compareTo(Object o) {//升序排列 return this.ord - ((point) o).ord; } } public class Main{ point[] p;//所有的食物点 boolean vis[] ;//标记是否被蚂蚁吃过了 int n ;//食物的个数 public Main(){ } //向量(x1,y1),(x2,y2)的叉积 public double det(double x1,double y1,double x2,double y2){ return x1*y2 - x2*y1; } //小于0,说明向量ab的极角大于ac的极角 double cross(point a,point b,point c){ return det(b.x - a.x, b.y - a.y, c.x - a.x,c.y - a.y); } //求距离 double dis(point a,point b) { double x1 = a.x; double y1 = a.y; double x2 = b.x; double y2 = b.y ; return (x2 - x1 )*(x2 - x1) + (y2-y1)*(y2 - y1); } //pre:蚂蚁开始的位置,num:蚂蚁经过的顺序 void dfs(int pre,int num){ if(num == n) return ; int mi = 1; while(vis[mi]) mi++;//找一个没有被蚂蚁吃过的点 //在没有吃完的点中找出极角最小的点 for(int i = mi + 1 ;i <= n;i++){ if(vis[i]) continue ;//再找一个没有被蚂蚁吃过的点 double w = cross(p[pre],p[mi],p[i]);//计算叉积 if(w < 0) mi = i;//记录极角小的那个点,极角相同取距离近的点 if((w ==0) && dis(p[pre],p[i]) < dis(p[pre],p[mi])) mi = i; } p[mi].ord = num + 1;//记录吃的顺序 vis[mi] = true ;//标记为已吃过 dfs(mi,num + 1) ;//递归 } public static void main(String args[]){ Main ma=new Main(); ma.go(); } public void go(){ Scanner in=new Scanner(System.in); int t; t=in.nextInt(); while(t-->0){ n=in.nextInt(); int mi = 1 ; vis=new boolean[n+1]; p=new point[n+1]; p[0]=new point();//这个点无用。 for(int i = 1 ; i<= n;i++){//从命令行输入食物信息 p[i]=new point(); p[i].id=in.nextInt();//食物的编号 p[i].x=in.nextDouble();//x坐标 p[i].y=in.nextDouble(); //y坐标 //找y最小的食物点,也即蚂蚁应该第一个吃的点 if(p[mi].y > p[i].y) mi = i; } vis[mi] = true;//蚂蚁最先吃的食物点 p[mi].ord = 1 ;//蚂蚁经过的顺序为1 dfs(mi,1);//从这点开始深搜 Arrays.sort(p);//全部解决,按蚂蚁经过的顺序排序所有点 System.out.printf("%d",n); for(int i = 1;i <=n;i++){ System.out.printf(" %d",p[i].id) ; } System.out.println(); } } }
源码下载:
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3810题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1707POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3092POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1502POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1953题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1670关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1902关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1918POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1941POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)
2012-12-22 13:57 1615一种形象的理解是 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1694分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(四):Graham 扫描法
2012-12-17 16:33 2321Graham扫描法 基本思想:通过设置一个关于候选点的 ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2308接上文:学习凸包(二) ... -
学习凸包(二):分治法求解
2012-12-16 14:32 3494接上文:学习凸包(一):暴力算法求解http://128kj. ... -
学习凸包(一):暴力算法求解
2012-12-15 17:06 2150凸包:令S是平面上的一个点集,封闭S中所有顶点的最小凸多边 ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1572关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1411接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1873关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1882关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1838关于树状数组,请参考:http://128kj.iteye.c ...
相关推荐
Rocky Linux 8.10内核包
内容概要:本文档详细介绍了如何在Simulink中设计一个满足特定规格的音频带ADC(模数转换器)。首先选择了三阶单环多位量化Σ-Δ调制器作为设计方案,因为这种结构能在音频带宽内提供高噪声整形效果,并且多位量化可以降低量化噪声。接着,文档展示了具体的Simulink建模步骤,包括创建模型、添加各个组件如积分器、量化器、DAC反馈以及连接它们。此外,还进行了参数设计与计算,特别是过采样率和信噪比的估算,并引入了动态元件匹配技术来减少DAC的非线性误差。性能验证部分则通过理想和非理想的仿真实验评估了系统的稳定性和各项指标,最终证明所设计的ADC能够达到预期的技术标准。 适用人群:电子工程专业学生、从事数据转换器研究或开发的技术人员。 使用场景及目标:适用于希望深入了解Σ-Δ调制器的工作原理及其在音频带ADC应用中的具体实现方法的人群。目标是掌握如何利用MATLAB/Simulink工具进行复杂电路的设计与仿真。 其他说明:文中提供了详细的Matlab代码片段用于指导读者完成整个设计流程,同时附带了一些辅助函数帮助分析仿真结果。
内容概要:该题库专为研究生入学考试计算机组成原理科目设计,涵盖名校考研真题、经典教材课后习题、章节题库和模拟试题四大核心模块。名校考研真题精选多所知名高校的计算机组成原理科目及计算机联考真题,并提供详尽解析,帮助考生把握考研命题趋势与难度。经典教材课后习题包括白中英《计算机组成原理》(第5版)和唐朔飞《计算机组成原理》(第2版)的全部课后习题解答,这两部教材被众多名校列为考研指定参考书目。章节题库精选代表性考题,注重基础知识与重难点内容,帮助考生全面掌握考试大纲要求的知识点。模拟试题依据历年考研真题命题规律和热门考点,精心编制两套全真模拟试题,并附标准答案,帮助考生检验学习成果,评估应试能力。 适用人群:计划参加研究生入学考试并报考计算机组成原理科目的考生,尤其是需要系统复习和强化训练的学生。 使用场景及目标:①通过研读名校考研真题,考生可以准确把握考研命题趋势与难度,有效评估复习成效;②通过经典教材课后习题的练习,考生可以巩固基础知识,掌握解题技巧;③通过章节题库的系统练习,考生可以全面掌握考试大纲要求的各个知识点,为备考打下坚实基础;④通过模拟试题的测试,考生可以检验学习成果,评估应试能力,为正式考试做好充分准备。 其他说明:该题库不仅提供详细的题目解析,还涵盖了计算机组成原理的各个方面,包括计算机系统概述、数据表示与运算、存储器分层、指令系统、中央处理器、总线系统和输入输出系统等。考生在使用过程中应结合理论学习与实践操作,注重理解与应用,以提高应试能力和专业知识水平。
__UNI__DB9970A__20250328141034.apk.1
rust for minio
国网台区终端最新规范
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
一个简单的机器学习代码示例,使用的是经典的鸢尾花(Iris)数据集,通过 Scikit-learn 库实现了一个简单的分类模型。这个代码可以帮助你入门机器学习中的分类任务。
pyqt离线包,pyqt-tools离线包
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
SQL常用日期和时间函数整理及在sqlserver测试示例 主要包括 1.查询当前日期GETDATE 2.日期时间加减函数DATEADD 3 返回两个日期中指定的日期部分之间的差值DATEDIFF 4.日期格式转换CONVERT(VARCHAR(10),GETDATE(),120) 5.返回指定日期的年份数值 6.返回指定日期的月份数值 7.返回指定日期的天数数值
GSDML-V2.3-Turck-BL20_E_GW_EN-20160524-010300.xml
T_CPCIF 0225-2022 多聚甲醛.docx
《基于YOLOv8的智能仓储货物堆码倾斜预警系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计
蚕豆脱壳机设计.zip
台区终端电科院送检文档
Y6一39一No23.6D离心通风机 CAD().zip
django自建博客app
台区终端电科院送检文档