本文格式為Word版，下載可任意編輯——沖刺N(yùn)OIP2023模擬試題六沖刺N(yùn)OIP2023模擬試題六

（提高組復(fù)賽）

試題：1.油滴擴(kuò)展

在一個(gè)長(zhǎng)方形框子里，最多有N（0≤N≤6）個(gè)相異的點(diǎn)。在其中任何一個(gè)點(diǎn)上給一個(gè)很小的油滴，那么這個(gè)油滴會(huì)一直擴(kuò)展，直到接觸到其他油滴或者框子的邊界。必需等一個(gè)油滴擴(kuò)展完畢才能放置下一個(gè)油滴。那么應(yīng)當(dāng)依照怎樣的順序在這N個(gè)點(diǎn)上放置油滴，才能使放置完畢后所有油滴占據(jù)的總體積最大呢？（不同的油滴不會(huì)相互融合）注：圓的面積公式V=pi*r*r，其中r為圓的半徑。

第一行一個(gè)整數(shù)N。

其次行為長(zhǎng)方形邊框一個(gè)頂點(diǎn)及其對(duì)角頂點(diǎn)的坐標(biāo)，x，y，x’，y’。接下去N行，每行兩個(gè)整數(shù)xi，yi，表示盒子內(nèi)N個(gè)頂點(diǎn)的坐標(biāo)。以上所有的整數(shù)都在[-1000,1000]內(nèi)。

一行，一個(gè)整數(shù)，長(zhǎng)方形盒子剩余的最小空間（結(jié)果四舍五入輸出）。，20010103377

50

2.數(shù)列（sequence）

雖然msh長(zhǎng)大了，但她還是很喜歡找點(diǎn)游戲自?shī)首詷?lè)。有一天，她在紙上寫(xiě)了一串?dāng)?shù)字：1,1,2,5,4。接著他擦掉了一個(gè)1，結(jié)果發(fā)現(xiàn)剩下1,2,4都在自己所在的位置上，即1在第1為，2在第2為，4在第4位。她希望擦掉某些數(shù)后，剩下的數(shù)列中在自己的位置上的數(shù)盡量多。她發(fā)現(xiàn)這個(gè)游戲很好玩，于是開(kāi)始樂(lè)此不彼地玩起來(lái)…不過(guò)她不能確定最多能有多少個(gè)數(shù)在自己的位置上，所以找到你，請(qǐng)你幫忙計(jì)算一下！

第一行為一個(gè)數(shù)n，表示數(shù)列的長(zhǎng)度。

接下來(lái)一行為n個(gè)用空格隔開(kāi)的正整數(shù)，第i行表示數(shù)Ai。

一行一個(gè)整數(shù)，表示擦掉某些數(shù)后，最終剩下的數(shù)列中最多能有多少個(gè)數(shù)在自己的位置上，即Ai=i最多能有多少。sequence.in5

11254sequence.out3

數(shù)據(jù)規(guī)模

對(duì)于20%的數(shù)據(jù)，n≤20對(duì)于60%的數(shù)據(jù)，n≤100對(duì)于100%的數(shù)據(jù)，n≤1000

3.SOFTWARE

一個(gè)軟件開(kāi)發(fā)公司同時(shí)要開(kāi)發(fā)兩個(gè)軟件，并且要同時(shí)交付給用戶(hù)，現(xiàn)在公司為了盡快完成這一任務(wù)，將每個(gè)軟件劃分成m個(gè)模塊，由公司里的技術(shù)人員分工完成，每個(gè)技術(shù)人員完成同一軟件的不同模塊的多用的天數(shù)是一致的，并且是已知的，但完成不同軟件的一個(gè)模塊的時(shí)間是不同的，每個(gè)技術(shù)人員在同一時(shí)刻只能做一個(gè)模塊，一個(gè)模塊只能有一個(gè)人獨(dú)立完成而不能由多個(gè)人協(xié)同完成。一個(gè)技術(shù)人員在整個(gè)開(kāi)發(fā)期內(nèi)完成一個(gè)模塊后可以接著做任一軟件的任一模塊。寫(xiě)一個(gè)程序，求出公司最早能在什么時(shí)候交付軟件。

輸入文件第一行包含兩個(gè)有空格隔開(kāi)的整數(shù)n和m，其中1≤n≤100,1≤m≤100。接下來(lái)的n行每行包含兩個(gè)用空格隔開(kāi)的整數(shù)d1和d2，d1表示該技術(shù)人員完成第一個(gè)軟件中的一個(gè)模塊所需的天數(shù)，d2表示該技術(shù)人員完成其次個(gè)軟件中的一個(gè)模塊所需的天數(shù)，其中1≤d1，d2≤100。

輸出文件僅有一行包含一個(gè)整數(shù)d，表示公司最早能與d天后交付軟件。SODFTWARE.IN320

112416

SODFTWARE.OUT18

最快的方案是第一個(gè)技術(shù)人員完成其次個(gè)軟件的18個(gè)模塊，用時(shí)18天，第三個(gè)技術(shù)人員完成第一個(gè)軟件的18個(gè)模塊，用時(shí)18天，其余的模塊由其次個(gè)技術(shù)人員完成，用時(shí)12天，做完所有的模塊需要18天。假使第一個(gè)技術(shù)人員完成其次個(gè)軟件的17個(gè)模塊，第三個(gè)技術(shù)人員完成第一個(gè)軟件的17個(gè)模塊，其余的模塊由其次個(gè)技術(shù)人員完成，需要用時(shí)18天，做完所有的模塊依舊需要18天，所以少于18天不可能完成所有模塊。

4.黑匣子（blackbox）

BlackBox是一種原始的數(shù)據(jù)庫(kù)。它可以存儲(chǔ)一個(gè)整數(shù)數(shù)組，還有一個(gè)特別的變量i。最開(kāi)始的時(shí)候BlackBox是空的，而i等于0。這個(gè)BlackBox要處理一串命令。命令只有兩種：

ADD（x）：把x元素放進(jìn)BlackBox；

GET：i加1，然后輸出BlackBox中第i小的數(shù)。

記住：第i小的數(shù)，就是BlackBox里的數(shù)按從小到大的順序排序后的第i個(gè)元素。例如：

我們來(lái)演示一下一個(gè)有11個(gè)命令的命令串。（如下圖所示）

序號(hào)12345678910操作ADD(3)GETADD(1)GETADD(-4)ADD(2)ADD(8)ADD(-1000)GETGETi0112222234數(shù)據(jù)庫(kù)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現(xiàn)在要求找出對(duì)于給定的命令串的最好的處理方法。ADD和GET命令分別最多有200000個(gè)。

現(xiàn)在用兩個(gè)整數(shù)數(shù)組來(lái)表示命令串：

1.A(1),A(2)，…A(M)：一串將要被放進(jìn)BlackBox的元素。每個(gè)數(shù)都是絕對(duì)不超過(guò)2000000000的整數(shù)，M≤200000。例如上面的例子就是A=（3,1,-4,2,8,-1000,2）。

2.u(1),u(2),…u(N)：表示第u(j)個(gè)元素被放進(jìn)了BlackBox里后就出現(xiàn)了一個(gè)GET命令。例如上面的例子中的u=（1,2,2,6）。輸入數(shù)據(jù)不用判錯(cuò)。

第一行，兩個(gè)整數(shù)，M，N。

其次行，M個(gè)整數(shù)，表示A(1)…A(M)。第三行，N個(gè)整數(shù)，表示u(1)…u(N)。

輸出BlackBox根據(jù)命令串所得出的輸出串，一個(gè)數(shù)字一行。7