OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【CQOI2015】网络吞吐量

【题目描述】

路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中,路由器会使用经典的Dijkstra算法计算最短路径,然后尽量沿最短路径转发数据包。现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),假设所有数据包一定沿最短路径转发,试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据...

【SCOI2013】泡泡鱼

【题目描述】

Fish是一条生活在海里的鱼,有一天他很无聊,想起了一个人类玩的游戏泡泡龙,于是他打算玩一把泡泡鱼。

Fish并不是特别清楚泡泡龙的规则(我们也是),于是他采用自己定的近似规则。

这里我们把海底想象成一个平面区域,它的上边界离发射点距离为H,左右边界离发射点的距离均为W。起初时在这个区域的某些位置上有一些各种颜色的泡泡, 且每个泡泡的直径为2(这里视泡泡为圆形)。如果两个相同颜色的泡泡相切,我们就说这两个泡泡相邻。 如果两个相同颜色的泡泡相邻或者可以通过第三个相同颜色的泡泡相连,我们就说这两个泡泡相连。

为了方便描述,我们定义发射点的坐标为(0,0...

【NOI2013】矩阵游戏

【题目描述】

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:

F[1][1]=1

F[i,j]=a*F[i][j-1]+b (j!=1)

F[i,1]=c*F[i-1][m]+d (i!=1)

递推式中a,b,c,d都是给定的常数。

现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,000,000,007的余数。

【输入】

输入包含一行有六个整数n,m,...

【CQOI2011】动态逆序对

【题目描述】

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

【输入】

输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。

【输出】

输出包含m行,依次为删除每个元素之前,逆序对的个数。

【输入样例】

5 4

1

5

3

4

2

5

1

4

2

【输出样例】

5

2

2

1

【题解】

首先统...

【CQOI2015】任务查询系统

【题目描述】

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。

超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范...

© OI技术宅 | Powered by LOFTER