5588葡京线路【noip 2013】车站分别

题目叙述

无异于长就为的铁路线上,依次有号也 1, 2, …,
n 的 n 个火车站。每个火车站都有一个级别,最低呢 1 级。现有若干和车次在马上长达路线及行驶,每一样次都满足如下要求:如果这水车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的还得靠。(注意:起始站和终点站自然为不失为事先都解要靠的站点)

像,下表是 5 趟车次的运作状态。其中,前 4 巡车次均满足要求,而第 5 和车次由停靠了 3 声泪俱下火车站(2 级)却无停过的 6号火车站(亦也 2 级)而不满足要求。

 5588葡京线路 1

幸存 m 趟车次的运转状态(全部满足要求) ,试推算这 n 独火车站至少分为几个不同的

级别。

【输入】

输入文件为 level.in。

第一尽包含 2 个刚刚整数 n, m,用一个空格隔开。

第 i +
1 行(1 ≤ i ≤ m)中,首先是一个正整数 si (2 ≤ si≤ n),表示第 i 趟车不成发生 si 单停靠站;接下有 si 独正整数,表示有停靠站的号子,从小到充分排列。每半只数里因此一个空格隔开。输入保证拥有的车次都满足要求。

【输出】

出口文件呢 level.out。

出口只发一行,包含一个刚整数,即 n 个火车站最少划分的级别反复。

欠篇属于<简书 — 刘小壮>原创,转载请注明:

<简书 — 刘小壮>
http://www.jianshu.com/p/41179be5893a


自我现就职于国内有地图导航公司,这首稿子是自前段时间在信用社组织技术分享的一个PPT,文章内容也重点出于是PPT的情为主,通过这篇文章好挺好之救助您了解地图导航是行业之相干技能。

PPT内容要概括地图相关专业知识、百度和高德SDK整体框架、数据来源、行业概览等组成。其中关于地图引擎相关的技巧知识,我为商家地图引擎开发同事求证过,这个PPT也被他们扣押罢,也协助指出了里的有的题材。

及时首稿子要用以分享,其中倘发生什么问题,还恳请多指出,谢谢!


输入输出样例

输入样例#1:

9 2 
4 1 3 5 6 
3 3 5 6 

出口样例#1:

2

输入样例#2:

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9 

输出样例#2:

3

地图开发专业知识

说明

对于 20%的数据,1 ≤ n, m ≤ 10;

对于 50%的数据,1 ≤ n, m ≤ 100;

对于 100%的数据,1 ≤ n, m ≤ 1000。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 1001
 6 using namespace std;
 7 bool a[1001],f[1001],e[1001][1001];
 8 int r[1001],b[1001],sk[1001];
 9 int main(){
10     int n,m,s;
11     cin>>n>>m;
12     for(int i=1;i<=m;i++){
13         memset(a,0,sizeof(a));
14         cin>>s;
15         for(int j=1;j<=s;j++){
16             cin>>b[j];
17             a[b[j]]=1;
18         }
19         for(int j=b[1];j<=b[s];j++)
20             if(!a[j])
21                 for(int k=1;k<=s;k++){
22                     if(!e[j][b[k]]){
23                         e[j][b[k]]=1;
24                         r[b[k]]++;
25                     }
26                 }
27     }
28     int ans=0,top;
29     while(1){
30         top=0;
31         for(int i=1;i<=n;i++)
32             if(!r[i]&&!f[i]){
33                 sk[++top]=i;
34                 f[i]=1;
35             }
36         if(top==0) break;
37         for(int j=1;j<=top;j++){
38             for(int i=1;i<=n;i++){
39                 if(e[sk[j]][i]){
40                     e[sk[j]][i]=0;
41                     r[i]--;
42                 }
43             }
44         }
45         ans++;
46     }
47     cout<<ans<<"\n";
48     return 0;
49 }

 

经纬度

经纬度

透过纬度是相同栽地理坐标系统,主要为此来代表地球之球面坐标系,经纬度可以稳定地球之另一个岗位。南北方向的名为纬度,东西方向称为经度

纬度:赤道纬度周长最丰富,离赤道越远纬度周长越欠,也不怕越贴近南北极。赤道以南称为南纬,赤道以北称为北纬纬度取值范围是0-90,赤道纬度最为小也0,两层最要命。

经度:经度啊叫子午线,任意两久经线长度等,起始点都以南北极。经度盖本初子午线为分,以东称为东经,以西称为西经东经为正数,西经为负数。经度取值范围以0-180,本初子午线为0。东经180度过也即是西经180度便是白令海峡,白令海峡就是国际换日线,日期去一龙。

按照经度,地球被分为24个时区,每个时区又有分,分以富含秒。

投影

投影

投影

做地图,投影的定义特别要紧。我们的地是周的,地球之坐标是一个球面坐标,球面坐标是三维坐标(x、y、z),而我们的地形图是是二维的(x、y),需要用球面的老三维坐标转换为面的老二维坐标。

坐标转换久用到了投影的概念,常用的投影有:圆柱投影圆锥投影方位投影,而当我们地图导航中行使墨卡托投影

墨卡托影子

墨卡托影

百度、高德、Google都使用墨卡托投影墨卡托投影起一个大特别之弊病,就是当高纬度(南纬北纬)地区产生巨大的变形。变形比较严重的地方在俄罗斯、格林兰岛、非洲、南极洲等于高纬度地区。

墨卡托影子

地方五个邦独家是:俄罗斯、澳大利亚、中国、巴西、加拿大
我们拿即时五个国家在一个纬度,来比较及时五独国家,发现相差并无顶非常。但是要是在上面那张图中,俄罗斯顶好几独中国大大小小。

国外开发者开发了一个网站,这个网站可以拿不同国度拉至跟一个纬度,这时候就能显示出真正比例的国家面积。
网站地址:http://thetruesize.com/

古德投影

古德投影

古德投影足避免地图变形的题目,这种投影以地图分为几只有,然后沿着赤道将几个组成部分连接于协同。我们发现上面的格林兰岛已经深受分为两片段,这种投影并无适合用于支付,而且看起效果呢无太尴尬。

金字塔型

金字塔型

把同布置世界地图显示到手机里是休可能的,所以便引入了金字塔模型的概念(也就是比例尺),我们得以因不同的缩放比例,显示不同的分辨率。

当地形图应用中,我们因此指尖缩放和加大地图,地图显示大小的易,都是依据金字塔模型来组织瓦片图的。

瓦片坐标系

瓦片坐标系

金字塔模型相当下的饶是瓦片坐标系,在不同的缩放等级下,同一块区域瓦片个数也是免同等的。

瓦片越是多就是意味着就无异区域显示更加详细,缩放比例也不怕更为充分。瓦片坐标系在2D及3D的状况下还见面于以,我们当网不好的情况下足见见地图瓦片的加载过程与瓦片的大小、位置。

坐标加密
  • CLLocationManager遭的中纬度加密(WGS-84)
  • MKMapView吃之中纬度加密(GCJ-02)
  • 高德SDK中之经纬度加密(GCJ-02)
  • 百度SDK中的中纬度加密(使用GCJ-02重新加密,叫做BD-09)

冲中华法律规定,地图提供商得对地图经纬度进行偏移,国测局制定了同样仿加密标准,就是常用之GCJ-02经纬度坐标加密主要出个别栽格式,GPS坐标系
(WGS-84) 和火星坐标系 (GCJ-02) ,加密算法是开源之,可以搜寻到。

国际经纬度坐标标准为WGS-84,国内必须至少用国测局制定的GCJ-02,对地理位置进行首不好加密。由于每家导航SDK提供方加密都无合并,所以百度、高德、谷歌多下地图数据并无合并,需要重开展换。

地图定位

地图定位

走端固定法要有三栽:GPSWi-Fi基站,但是androidiOS还免极端一致,android可以叫用户选择与装置那种定位法,但是iOS大凡由系统吧我们选取的,我们尚无操作定位法的权力。iOS不允许发生第三正定位,所以现在地图应用还是本着系统定点进行的包。如果有GPS信号,iOS网会事先挑选GPS道固定,然后是Wi-Fi定位,如果Wi-Fi信号不好就是会选取基站定位。

当固定中精确度最高的凡GoogleGoogle采取大数量解析,记录每一样浅利用Google地图的一定。下次更定位时,直接冲Mac地址齐信息进行辨析,提高一定精确度。

较悲催的一个问题就是,有一部分比较一直的iOS机器,没有GPS定位模块,例如有一直版本iPad,这种设施以从来不Wi-Fi的事态下是无法稳定的。

地理编码和逆地理编码

演示图片

地理编码:即地理解析,由详细的结构化地址得到相应之经纬度信息,例如北京市海淀区中关村南大街27号的地方,就好获到一个唯一的中纬度信息。

逆地理编码:即逆地理解析,由一个经纬度信息得到一个结构化地址信息,例如lng:116.31985,lat:39.959836由此纬度,就可以获得到接近于面的地理信息。

iOS系统API、高德SDK、百度SDK中,都为我们提供了地理编码逆地理编码API,但是用留意通过纬度的换,不同地图SDK返回的经纬度加密方法不同,我们于传诵经纬度参数与收取经纬度参数时,都需开转换。

地图数据来源

高德

四维图新

境内比较外向的数额采集商主要是高德以及四维图新两小,百度没有多少收集资质(最近买断了道道通),所以数据要依赖让四维图新。

四维图新与国测绘局合作比较缜密,数据来自主要是国家测绘局资,也有部分好测绘的数。高德测绘和航拍能力还不易,主要自己测绘数据,部分数据为借助国测局提供。数据测绘单位互相之间还来合作,会彼此购买好从来不的数量。

在中原,谷歌地图或苹果地图等地图开发商,数据来源于几乎都是立简单小商厦。

POI数据

POI

POI数量是一律种矢量数据,包括美食、商店、银行、加油站等还是POI数据,在地图上相似还坐气泡或大头针表示。

数码收集可以透过车载GPS摄像机采集,或由服务性互联网企业抓取或市,由于百度和高德提供了对外的SDK,通过用户用地图SDK也可以收获有数量。

百度的地形图数据要依赖让四维图新以及道道通,高德地图主要因为自采为主。一般这些数量为会与大众点评、携程、口碑等互联网服务商购买,相互之间也会见买POI数据。

栅格-2D地图

珊格图

珊格图

2D状况:轻地图应用,简单的职分享、兴趣点标注、线路展示等。2D模型著力量不极端好,在缩放比例比小的图景下,看起比较模糊(缩放比例很有拘禁起清晰度还足以)。

栅格模型对有一个地方的讲述,是通过多重叠图片叠加成的,每层代表不跟信息(例如道路)。栅格模型诚如还见面预先渲染一个底图,然后是于底图的功底及折加路况、POI等图层。

珊格图都是以服务器预处理的图片,从服务器下载处理好之图及本地开展拼接即可,由于生充斥到地方是图,本地未克再对图层进行更改。对于性达到的话,服务器进行图片合成性能消耗比较充分,但是客户端性能消耗比较粗,内存占用呢正如小,用起来会比流利。

矢量-3D地图

矢量地图

矢量地图

3D场景:重地图应用,以LBS呢基本功能,需要离线地图、更好之渲染效果、app内导航的。比如打车用、出行导航类应用,3D模型渲染后底效力比较好,一般以导航功能都得用是3D模型

矢量数据是由服务器将地图数据下载下来,然后以客户端进行合成绘制的,所以我们可以对地图的亮进行控制,可定制性更胜似。矢量图看起再优秀清晰,渲染效果比好。但是矢量图对手机特性消耗大厉害,手机内存占用比较高,CPUGPU消耗都好酷。对于服务器性能消耗就较2D场景性小一些,因为服务器就是加载原始数据与向阳客户端进行传输,将合成绘制等这些图层渲染的绘图处理交给客户端来举行。提高了客户端灵活性与另行好的成效,牺牲了客户端的属性,有利有弊。

三维地图

三维地图

三维地图凡以三维地图数据为底蕴开发之,三维地图扣押起再佳立体化,地图及得展现出立体建筑及影子的效能,而且地图随着用户的操作,楼宇的角度、阴影等效果啊会见随着发生变化。

三维地图对接进程被,也出现过假三维地图。这种地图只能进行平面平移,不能够拓展盘操作,是数据平面地图三维地图连接的名堂。

域外地图

国外地图

百度地图目前早就得以支撑有国的国外地图服务,例如新加坡、韩国、日本、泰国顶国家。可以于新型的百度地图app上直接翻、搜索这些国家之有些POI,以及以导航等功效。

目前为止只发百度一小支撑海外地图服务,高德暂时无支持这项服务。在百度和高德不支持的地方,由于服务器并未数,所以未见面开渲染,看起白白的同等片。

实景地图

实景地图

实景地图极端开始是Google研发的,这项技艺需要软件与硬件相互的配合,以及大量底数码处理才能够完成。

采访实景需要各式实景采集工具,包括汽车采集、自行车采集、人力采集等,这根本是由于需要报各种采集地点。采集时以数据实时绑定GPS职务,这样便了解是以哪个岗位采集的。

多少搜集后待工程师将数据开展复杂处理,才能够形成我们看出底实景数据。实景数据一般还是静态的,而且不是实时更新的。实景数据为保护为采集人的用户隐私,需要对关键部位进行模糊处理,例如脸、车牌照等。

室内地图

室内地图

室内定位凡一律种组成3D定位的定位模式,这种稳定好以室内进行定位。室内定位一直固定某个商铺于几楼的某某位置,而且可择楼层。

于风的恒被,楼内由是基本上重合,会造成定位重叠的题材,而且楼内GPS信号吧未极端好还没有。所以出现了有的初技巧来实现楼内一定:AGPS(辅助全球卫星定位系统)、Wi-Fi指纹定位、zigbee芯片定位、RFID智能标签技术、以及苹果推出的ibeacon,其中高德用的是Wi-Fi指纹定位技术。

百度热力图

百度热力图

首先是由于百度率先支持热力图功能,热力图效能预示着那个数目时更加贴近。热力图是基于百度地图移动客户端和SDK在这些地方的使状况想出来的,这些推断数据好是网要、打开次数等于,通过这些数据推测出人员分布。通过前百度在CCTV的报导来拘禁,通过这些多少还足以预计景区人山人海,防止大型踩踏等群体性事件。

热力图乘同一区域5588葡京线路的密集程度变化,颜色就转移死。但是出于统计方法的性状,统计的多寡并无极端可靠,例如白天和夜间尽管产生良老分别,只是当参考。


地图SDK架构

高德SDK结构

高德SDK结构

Annotation:单点标注,继承自UIView,可以运用UIView的有些基础属性,引入了选定机制(百度也是一模一样的兑现,包括部分打车软件的手推车,都是动Annotation实现)。

Overlay:多点标注,引擎直接渲染,可以由此SDK的API自定义UI,多碰标注用于标识路线要某一个区域。

Other:云搜索,地理编码和逆地理编码,导航路径设计,定位,POI搜索等。

MapKit和高德SDK区别

对比

右边图片的高德logo是黑色,并且出示在右下角,这是iOS系统的MapKit.framework

左手图片的高德logo是蓝色,并且显示在左下角,这是高德自己之SDK。

苹果的MapKit只是使用了高德的数据,但是API是苹果好开发之。

百度地图SDK框架

百度地图SDK框架

跨越平台引擎:
  • 百度地图的地图引擎使用openGLES绘制
  • 能运转于支持C++的手机系统平台
  • 不同平台对应用层保持一致的API接口
  • 提供能够满足应用层的功底数据结构
  • 尽可能少的乘系统接口,提高可移植性
  • 世故和可扩展性

百度地图对于高德地图来说,增加了有实用性的成效,例如热力图、骑行、个性化地图等。这些意义都是高德所没有的,当然高德为闹有大对的机能,两者各发生独到之处。

百度地图跟高德地图还发2D及3D功能,2D纯粹平面展示,没有楼宇拔高效果。

百度地图SDK框架

百度地图SDK框架

百度SDK主要模块划分:

  • 地图(基础意义,地图显示和操作及各种覆盖物图层)
  • 检索(POI,地理编码、路径设计等)
  • 定点(提供单身稳定模块,经纬度根据国测局二坏加密)
  • 工具(调用百度客户端,坐标转换等)
  • 普遍雷达(检索用户信息,查找附近的丁,主要用于社交)
  • LBS云(区域搜索,百度服务器存储数据,可以协调操作,属于开发者自来多少)

百度SDK分为六单特别之模块,可以遵循需求下载对应之模块,这样要下载下来的SDK体积变小。

百度鉴权认证策略:用户可通过简单种方法与百度开放云进行交互,包括认证方式匿名方式。在SDK中过多地方都为此到了鉴权认证,例如加载地图时证实不经不会见展示地图,百度比较青睐SDK的鉴权

祈求层渲染

希冀层渲染

百度地图渲染分为多单图层渲染,每个图层渲染之目标吗无一样,地图及于定义标注和掩盖物统称为地图覆盖物,多只图层叠加起来形成矢量图。百度地图SDK地图等时也19级,可以因缩放等级的异渲染建筑物、道路、河流、学校、公园等内容。

百度地图支持多接触触摸、双击放大、多触及缩小、旋转等手势操作。并且支持画点、折线、圆、多边形等操作,并且可以起定义热力图瓦片图等。

百度个性化地图

百度个性化地图

百度地图在16年1月份生产了个性化地图,SDK提供了只性化地图模版,通过地图模版更改底图颜色和体裁。从百度开发者平台下充斥及模版,通过地图模版可以改本地、水系、草地、道路、铁路、地铁、POI等颜色跟体,然后调用SDK提供的方式读博该模版即可。


地图产业链

地图产业链

生龙活虎统计

首先摆放图是同等卖14年的统计报告,这卖统计报告统计不顶周到,部分导航应用尚未给含有在内。

于即时卖统计报告被,我们发现高德是唯一一个蒙整条产业链的庄,在产业链的每个环节都在高德的人影。

2014年4月,阿里针对高德就了15亿美元之收买,高德成为阿里旗产都资子公司。