本文格式為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