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
cpu设计实例-verilog
cpu设计实例-verilog,通过这个文档 你可以很快的入手如何设计一份8位的cpu,其中的指令码位16位什么是CPU?CPU即中央处理单元的英文缩写,它是计算机的核心部计算机进行信息处理可分为两个步骤1)将数据和程序(即指令序列)输入到计算机的存储器中2)从第一条指令的地址起开始执行该程序,得到所需结果,结束运行。CPU的作用是协调并控制计算机的各个部件执行程序的指令序列,使其有条不紊地进行。因此它必须具有以下基本功能a)取指令:当程序已在存储器中时,首先根据程序入口地址取出一条程序,为此要发出指令地址及控制信号b)分析指令:即指令译码。是对当前取得的指令进行分析,指出它要求什么操作,并产生相应的操作控制命令c)执行指令:根据分析指令时产生的操作命令形成相应的操作控制信号序列,通过运算器,存储器及输入/输出设备的执行,实现每条指令的功能,其中包括对运算结果的处理以及下条指令地址的形成将其功能进一步细化,可概括如下1)能对指令进行译码并执行规定的动作;2)可以进行算术和逻辑运算;3)能与存储器,外设交换数据4)提供整个系统所需要的控制尽管各种CPU的性能指标和结构细节各同出功能分析,可知任何一种内目部结构至少应包含下面这些部件:1)算术逻辑运算部件(ALU)2)累加器;3)程序计数器;4)指令寄存器,译码器;5)时序和控制部件RISC即精筲指令集计算机( Reduced instruction seComputer)的缩写。它是一种八十年代才出现的CPU,与一般的CPU相比不仅只是筒化了指令系统,而且是通过筒化指令系统使计算机的结构更加筒单合理,从而提高了运算速度。从实现的途径看, RISC-CPU与一般的CPU的不同处在于:它的时序控制信号形成部件是用硬布线逻辑实现的而不是采用微程序控制的方式。所谓硬布线逻辑也就是用触发器和逻辑门直接连线所构成的状态机和组合逻辑,故产生控制序列的速度比用微程序控制方式快得多,因为这样做省去了读取微指令的时间RISC_CPU也包括上述这些部件,下面就详细介绍一个筒化的用于教学目的的 RISC-CPU的可综合 Veriloghdl模型的设计和伤真过程RISC CPU结构RISC_CPI是一个复杂的数字逻辑电路,但是它的基本部件的逻辑并不复杂。可把它分成八个基本部件:1)时钟发生器2)指令寄存器3)累加器4) RISC CPU算术逻辑运算单元5)数据控制器6)状态控制罨D7)程序计数器8)地址多路器中各部件的相互连接关系1时钟发生器时钟发生器时钟发生器利用外来时钟信号米生成一系列时钟信号送往的其他部件。其中是外来时钟的八分频信号。利用的上升沿来触发控制器开始执行一条指令,同时信号还将控制地址多路器输出指令地址和数据地址。信号用作指令寄存器、累加器、状态控制器的时钟信号则用于触发算术逻辑运算单元。时钟发生器c1kgen的波形
- 2020-11-30下载
- 积分:1