IOI2014解题报告
信息学奥赛的重要资料。对于爱好信息学奥赛的青少年而言，此报告十分难得。Chapter 1Day 11.1 Day 1 rail11.1题目大意有两条平行的单向铁路(上方的从右到左,下方的从左到右),分为m段有η个车站,每个车站为C类型(只能从上往下)或D类型(只能从下往上),分布在某些段中,每个段最多一个车站。已知0号车站是C类型,并给出0号车站的位置,最多可以询问两车站之间的距离3(n-1)次(距离指经过段与段连接处的次数,例如上图0号车站到2号车站的距离为5),要求确定每个车站的位置和类型。保证车站两两可达11.2算法讨论先询问得到0号车站到其他车站的距离,而最近的一个,就是0号车站右侧第一个D类型的(称之为j号车站)然后询问得到号车站到其他车站的距离,其中最近的一个,可能是0号车站,也可能是其他车站(都称之为k号车站),显然和k之间不会冉有其他车IOI2014解题报告Day 1 Wall站,而0和k之间也不会有其他的D类型的车站,所有k号车站到其他车站的距离可直接算出有了和k到其他车站的距离,那就可以轻松分出左右了(离j号近,就在k的左侧,否则在j的右侧)。但分出左右后还是不能确定具体位置,而这时对于每个车站我们还留下次询问的机会。接下来称当前车站为号车站而这次询问一定是留给特殊位置的车站,假设当前车站在左侧,则考虑当前确定的最左侧的车站(称之为L号)。按离(或k)号车站的距离从近到远的顺序处理剩下的车站,那么只有这两和情况:L k j以及(注意下面这种L和之间还会有C类型的车站)L i k两者都会有以下关系式:dst(j,L)+|0s;-pos|=dist(j.)+x(x≥0)第一种情况多出来的是L到它右侧第一个D类型车站的距离×2,而第二种情况多出来的是L到它右侧第一个C类型车站的距离×2。所以,算出x之后,只要到L右侧的c/2的距离处看下车站的类型就可以确定位置了。这样问题就解决了如果当前车站在右侧,那么询问与已确定的最右侧车站的距离,类似讨论即可。1.2 Day 1 Wall21题目大意维护一个长度为的整数序列,一开始每个元素均为0,支持以下两种操作将连续一段中小于k的元素修改为k将连续段中大于k的元素修改为k问所有m个操作进行完之后序列各元素的值。3IOI2014解题报告Day 1 Game1.22算法讨论不难发现对某一个元素的操作是可加的,即说对于某一个元素来说,应用在其上的每一个操作可以都表示为“如果它的初值小于L,那么最终它等于l;如果它的初值大于γ,那么最终它等于η;否则它最终等于初值”这样的形式,并且多个这样的形式是可以合并的。于是我们可以把每个操作都看成一个值,这样原问题就转化成“维护一个序列,每次对一段区间加上一个值,问最后每个元素的值”。这是可以用带标记的线段树直接维护的。该算法的时间复杂度为O(m+ m log n)对于“维护一个序列,每次对一段区间加上一个值,问最后每个元素的值”这个问题,我们也可以使用扫描线进行维护。但本题中的值是不可减也不满足交换律的,因此在扫描过程中我们需要使用一个线段树来维护覆盖到当前点的值并将它们按时间顺序依次求和。该算法的时间复杂度为O(m+ m log m)1.3 Day 1 game131题目大意有一张n个点的无向图,小B每次会询问某两个点之间是否有边相连,小A每次回答yes或no。如果在小B把所有(条边间完之前,小B就能确定这整张图是否联選,小A就输了。现在让你当小A,依次对每个询问回答yes或no求一种获胜方案。1
- 2020-12-09下载
- 积分：1
MATLAB仿真在现代通信中的应用
MATLAB仿真在现代通信中的应用,特别是无线通信仿真详细具体，适合无线通信研发人员使用。内容简介本书以现代无线电通信中的关键技术:扩频、跳频、OFDM、3G系统、无线接入系统以及常见无线通信系统作为对象,以 MATLAB/ Simulink作为仿真工具,对上述系统进行了仿真实验还对数字信号通过各种调制方式,发送滤波器后的频谱特性,以及应用各种差错控制方式后的传输特性给出了系列仿真实例。并对上述仿真内容进行了简单的原理性介绍,对于建模和仿真编程中出现的主要问题与注意事项做了相应敏讲解。仝书源程序附有光盘本书可作为高等学校通信专业的教学、科硏参考书,也可供管理部门作为参考资料、图书在版编目C|P)数据MATLAB仿真在现代通信中的应用徐明远,邵玉斌编著一西安:西安电子科技大学出版社,20114ISBN978-7-56062554-6Ⅰ①M…Ⅱ①徐…②邵…Ⅲ①通信系统一系统仿真一软件包, MATLABⅣ①TN914中国版本图书馆CP数据核字(2011第027693号策划臧延新责任编辑杨宗周出版发行西安电子科技大学出版社(西安市太白南路2号)电话(029)8824288588201467邮编70071网址www.xduph.com电子邮箱 xdupfxb00@163com经销新华书店印刷单位陕西天意印务有限责任公版次2011年4月第1版20ll年4月第1次印刷开本787毫米×1092毫米116印张13625数315千字印数1~2000册定价30.00元(含光盘)ISBN978-7-5606-25546/N·0594XDUP2846001-1煮如有印装问题可调换*本社图书封面为激光防伪覆膜,谨防盗版。前言近十年来,无线电技术突飞猛进,无线电事业快速发展。扩频、跳频、OFDM技术3G系统、蓝牙、IEEE802.11a、数字电视、智能天线等技术的出现,让人目不暇接。无线电成了现代文明的重要组成部分。人们在享受现代文明带来的方便与效率时,想到了应该对这些新技术和新系统多一些了解,然而,深奧的理论、复杂的技术、昂贵的设备与仪器给学习带来了不少的困难。人们在寻找与快速进步的技术相适应的学习与研究方法时,MATLAB仿真在新技术的学习与新系统的研发中成了有力的工具。应用 MATLAB的编程方法和功能模块,可以搭建各种仿真系统,还可以应用丰富的时间域、频率域、相位域的仿真测量仪器。许多新一代通信系统的系统级的仿真程序出现在 MATLAB软件的演示实例中,这使得学习的效率大为提高,对技术与系统的理解已经从概念深入到电路方案和参数选取的层面。建立和谐的电磁环境,需要了解各种无线电通信系统的特性,其中包括时间域、频率域、相位域以及传输特性。特别是它们之间的定量关系可以从仿真实例运行的结果中得到。也可以说,每个仿真实例就是一个小实验平台,实验中可以对通信的相关原理,甚至通信系统进行研究,其中的分类结果也可以作为资料备查。本书应用 MATLAB仿真工具对常见的调制方式、发送滤波器、差错控制方式以及各种通信系统(包括新一代的通信系统)的相关特性进行研究。可以运行的大量仿真实例,一方面给出了仿真的结果;另一方面还给出了部分仪表测量的结果可供比对。仿真实例大部分是作者在教学与科研实践中自行编制的,小部分是 MATLAB软件中的演示仿真实例全书分以下五部分:第一部分基础知识,包括数字调制、发送滤波器、通信信号的测量与表达。第二部分常用无线电通信系统,包括公众移动通信系统、专用移动通信系统、卫星通信系统。第三部分新技术与3G,包括扩频、跳频、OFDM以及3G系统。第四部分无线接入系统与数字电视,包括蓝牙、802.1a与数字电视。第五部分天线与射频技术,包括天线阵列、射频传输线、滤波器。书中给出了简单的原理介绍、 MATLAB仿真的系统、程序(光盘)以及程序运行结果。对编程中的主要问题与注意事项作了讲解。着重讨论了各种系统及输出信号的频谱特性。对于系统的传输特性,以及影响系统传输特性的因素,譬如调制方式、差错控制方式也进行了较系统的讨论。为了保持本书简练的篇幅,没有在书中详细介绍所有仿真系统中各个模块的参数设置,也没有将雷同的系列仿真系统的程序在书中展示。购书所附的光盘提供了书中提到的全部软件。点击模块打开对话框可以仔细研究其中每个模块的参数设置。若需要还可以将其拷贝出来后按照读者的意愿,遵循 MATLAB的相关规则更改参数后进行学习研究。本书可作为高等学校通信专业的教学、科研参考书,也可供管理部门作为参考资料。本书编写中的不妥和疏漏之处,还望读者给予指出。作者的联系方式:xumil@163com,shaoyun99@sina.com徐明远邵玉斌2011年1月说明1.用 MATLAB m文件编写的程序序号在本书中是这样表示的:比如程序35表示第3章的序号为5的程序。在 MATLAB软件中用CHX35表示。2. MATLAB/Simulink程序在本书及 MATLAB软件中都用SCHX3_10表示(第3章的序号为10的程序),该仿真系统框图在本书中用图3-10表示。3.本书的程序可运行在 MATLAB2008B版本目录第一部分基础知识第1章数字调制1.1非连续相位的角度调制31.1.1FSK信号的仿真1.1.2PSK信号的仿真1412连续相位的角度调制.1.3正交幅度调制29第2章发送滤波器,·,2.1概论322.2升余弦脉冲滤波器.332.3平方根升余弦滤波器4124高斯滤波器…46第3章通信信号的测量与表达3.1通信仿真中常用的信号测量模块3.1.1 Simulink基本模块中的 Sinks子库简介,,,,,,,,,,,,,,,,,513.12 Simulink通信工具箱中的 Comm sinks子库简介….52313 Simulink信号处理工具箱中的 Signal Processing Sinks子库简介533.2信号的测量…623.21窄带随机信号的产生和波形测量3.2.2各种信号的表示和测量633.3差错控制传输特性的测量与表达72331线性码……1733.32循环码.753.33里德-索洛蒙码773.34卷积码335汉明码3.3.6BCH码3.37循环冗余码8534信号统计参数的测量.…863.4.1统计模块库86342概率密度函数873.4.3瑞利衰落信道的仿真测试……344图像的灰度直方图3.5图像和视频信号的测量与表达3.5.1模块库…3.52图像的读出与显示933.53图像加噪与滤波…,.,,,·943.54图像的二维变换与反变换963.5.5图像有损压缩“““第二部分常用无线电通信系统第4章公众移动通信系统1014.1公众通信系统概述…….1014.1.1最早期的移动通信系统014.1.2第1代移动通信系统….4.1.3第2代移动通信系统1024.1.4第2.5代移动通信系统……,,,,,,,1044.1.5第3代移动通信系统1064.1.6第4代移动通信系统…1084.2GSM全球移动通信系统.,,非1094.3CDPD蜂窝数字分组数据网……11144NADC北美数字蜂窝网1134.5PDC个人数字蜂窝电话144.6 CDMA IS-95码分多址通信系统1174.7CT-2第2代无绳电话系统184.8数字增强型无绳通信标准12049PHS个人手持式电话系统12第5章专用移动通信系统12451集群通信系统…12452APCO数字集群通信系统1255.3 TETRA欧洲数字集群通信系统12754THTS地面航空电话系统…129第6章卫星通信系统1316.1铱星系统.1316.2美国ICO卫星通信系统13363甚小孔径终端卫星通信系统…135第三部分新技术与3G第7章新技术…1417.1扩频1417.2多元扩频7.3跳频…14674正交多载波调制OFDM.150第8章3G系统15281 WCDMA码分多址通信系统15282CDMA2000码分多址通信系统157第四部分无线接入系统与数字电视第9章无线接入系统…91蓝牙系统 BLUE TOOTH16592无线局域网 HiperLAN216993无线局域网802.11标准,.非,,,,,,,,,,,,,,,,甲174第10章数字电视系统10.1数字电视广播系统…17910.2卫星广播系统182第五部分天线与射频技术第11章天线187111天线方向图18711.2均匀直线阵的波束扫描…11111187113均匀圆形阵的波束扫描189114非均匀直线阵的波达方向估计19211.1 Capon法194114.2 Music法195第12章射频…19612.1波导19612.2传输线19812.3滤波器205参考文献207
- 2021-05-06下载
- 积分：1
