冲刺NOIP2023模拟试题六

本文格式为Word版，下载可任意编辑——冲刺NOIP2023模拟试题六冲刺NOIP2023模拟试题六

（提高组复赛）

试题：1.油滴扩展

在一个长方形框子里，最多有N（0≤N≤6）个相异的点。在其中任何一个点上给一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必需等一个油滴扩展完毕才能放置下一个油滴。那么应当依照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）注：圆的面积公式V=pi*r*r，其中r为圆的半径。

第一行一个整数N。

其次行为长方形边框一个顶点及其对角顶点的坐标，x，y，x’，y’。接下去N行，每行两个整数xi，yi，表示盒子内N个顶点的坐标。以上所有的整数都在[-1000,1000]内。

一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。，20010103377

50

2.数列（sequence）

虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1,1,2,5,4。接着他擦掉了一个1，结果发现剩下1,2,4都在自己所在的位置上，即1在第1为，2在第2为，4在第4位。她希望擦掉某些数后，剩下的数列中在自己的位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不彼地玩起来…不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！

第一行为一个数n，表示数列的长度。

接下来一行为n个用空格隔开的正整数，第i行表示数Ai。

一行一个整数，表示擦掉某些数后，最终剩下的数列中最多能有多少个数在自己的位置上，即Ai=i最多能有多少。sequence.in5

11254sequence.out3

数据规模

对于20%的数据，n≤20对于60%的数据，n≤100对于100%的数据，n≤1000

3.SOFTWARE

一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的多用的天数是一致的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能有一个人独立完成而不能由多个人协同完成。一个技术人员在整个开发期内完成一个模块后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。

输入文件第一行包含两个有空格隔开的整数n和m，其中1≤n≤100,1≤m≤100。接下来的n行每行包含两个用空格隔开的整数d1和d2，d1表示该技术人员完成第一个软件中的一个模块所需的天数，d2表示该技术人员完成其次个软件中的一个模块所需的天数，其中1≤d1，d2≤100。

输出文件仅有一行包含一个整数d，表示公司最早能与d天后交付软件。SODFTWARE.IN320

112416

SODFTWARE.OUT18

最快的方案是第一个技术人员完成其次个软件的18个模块，用时18天，第三个技术人员完成第一个软件的18个模块，用时18天，其余的模块由其次个技术人员完成，用时12天，做完所有的模块需要18天。假使第一个技术人员完成其次个软件的17个模块，第三个技术人员完成第一个软件的17个模块，其余的模块由其次个技术人员完成，需要用时18天，做完所有的模块依旧需要18天，所以少于18天不可能完成所有模块。

4.黑匣子（blackbox）

BlackBox是一种原始的数据库。它可以存储一个整数数组，还有一个特别的变量i。最开始的时候BlackBox是空的，而i等于0。这个BlackBox要处理一串命令。命令只有两种：

ADD（x）：把x元素放进BlackBox；

GET：i加1，然后输出BlackBox中第i小的数。

记住：第i小的数，就是BlackBox里的数按从小到大的顺序排序后的第i个元素。例如：

我们来演示一下一个有11个命令的命令串。（如下图所示）

序号12345678910操作ADD(3)GETADD(1)GETADD(-4)ADD(2)ADD(8)ADD(-1000)GETGETi0112222234数据库331,31,3-4,1,3,-4,1,2,3,-4,1,2,3,8-1000,-4,1,2,3,8-1000,-4,1,2,3,8-1000,-4,1,2,3,8输出331211ADD(2)4-1000,-4,1,2,2,3,8现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多有200000个。

现在用两个整数数组来表示命令串：

1.A(1),A(2)，…A(M)：一串将要被放进BlackBox的元素。每个数都是绝对不超过2000000000的整数，M≤200000。例如上面的例子就是A=（3,1,-4,2,8,-1000,2）。

2.u(1),u(2),…u(N)：表示第u(j)个元素被放进了BlackBox里后就出现了一个GET命令。例如上面的例子中的u=（1,2,2,6）。输入数据不用判错。

第一行，两个整数，M，N。

其次行，M个整数，表示A(1)…A(M)。第三行，N个整数，表示u(1)…u(N)。

输出BlackBox根据命令串所得出的输出串，一个数字一行。7