NOIP2010模拟试题

1、NOIP2010模 故事背景： 小 FF 在 了上次“ 找古代王族 ”的探 后，成 了世界上最 大的探 家并 有了一大笔 富。当然他不能坐吃山空，必 造 富！ ！ 于是他 下了 中的GreedIsland 并 先 展那里的采 他 将其称 Greed Island 的“ NewBe_One ” 划。 一：新的开始【 目描述】 展采 当然首先得有 井，小 FF 花了上次探 得的千分之一的 富 人在 上挖了 n 口 井，但他似乎忘 考 的 井供 了保 力的供 ，小 FF 想到了两种 法：1、 在 一口 井上建立一个 站， 用 v（ 站的 出功率可以供 任意多个 井）。2、 将 口 井与另外的已 有

2、力供 的 井之 建立 网， 用 p。小 FF 希望身 ” NewBe_One 划首席工程 的你帮他想出一个保 所有 井 力供 的最小花 。【 入格式】第一行一个整数 n， 表示 井 数。第 2 n+1 行，每行一个整数，第 i 个数 vi 表示在第i 口 井上建立 站的 用。接下来 一个n*n 的矩 P， 其中 p i , j 表示在第i 口 井和第j 口 井之 建立 网的 用（数据保 有p i, j = p j, i ,且 p i, i =0 ）。【 出格式】 一个整数，表示 所有 井 得充足 能的最小花 。【 入 例】454430 2 2 22 0 3 32 3 0 42 3 4 0【 出

3、 例】9 出 例 明：小 FF 可以 在4 号 井建立 站然后把所有 井都与其建立 网， 花 是3+2+2+2= 9。【数据范 】 于 30%的数据： 1=n=50; 于 100% 的数据：1=n=300; 0=vi, pi,j =105.1 二工 代【 描述】小 FF 的第一片 区已 开始运作了，他着手开展第二片 区小 FF 的第二片 区， 也是” NewBe_One “ 划的核心部分，因 在 片 区里面有全宇宙最稀有的两种 物，科学家称其 NEW 和 BE 。 区是被划分成一个 n*m 的矩形区域。 小 FF 探明了每一小 区域里的NEW 和 BE 的 藏量， 并且小 FF 在 区的北 和

4、西 分 置了NEW 和 BE 的收集站。你的任 是 一个管道运 系 ，使得运送的NEW 和 BE 的 量最多。管道的型号有两种， 一种是 西向， 一种是南北向。在一个格子内你能建造一种管道，但不能两种都建。如果两个同 型管道首位相接，它 就可以被 接起来。另外 些 物都十分不 定， 因此它 在运送 程中都不能拐弯。 就意味着如果某个格子上建有南北向管道， 但是它北 的格子建有 西向管道，那么 根南北向管道内运送的任何 西都将 失。 一步地，运到 NEW 收集站的 BE 也会 失， 运到 BE 收集站的 NEW 也会 失。【 入格式】第一行包含两个整数 n 和 m，表示 区大小。以下 n 行，每

5、行 m 个整数，其中第 i行第 j 个整数 G i , j 描述各个格子上的 BE 数量。接下来以 似的矩 表示各个格子上的NEW 数量。【 出格式】 一个整数， 表示最多可以采集到的NEW 和 BE 的 量。【 入 例】4 40 0 10 91 3 10 04 2 1 31 1 20 010 0 0 01 1 1 300 0 5 55 10 10 10【 出 例】98【数据范 】 于 30%的数据：0= n ， m =100; 于 100% 的数据：0= n, m =1000;0= G i, j =1000. 三：杀蚂蚁【 目描述】 “善有善 ， 有 ，不是不 ”。 小 FF 一心只 自己企

6、 的壮大而没 及自己的采 Greed Island 上生 境的破坏，Greed Island 的 境日益 劣。 于， 上的 异了，它 决定 小FF 的 区 行攻 ，欲将 上的人 逐出去面 2 的 攻，人 退。无奈之下，小 FF 来了全宇宙最 的防御系 制造商派来的工程机器人 SCV ，希望能 阻 的攻 。 小 FF 的研究，他 每次都走同一条 度 n 个 位的路 攻，且 的 一个 位 度所需的 T 秒。也就是 ，只要小FF 在条路 上布防且 造成沉痛 害就能阻止 的 。SCV 擅 制造的防御塔有三种，分 是激光塔，放射塔和干 塔，他 可以在一个 位 度内修建一座防御塔。三种防御塔的作用如下：激

7、光塔：使用高能激光，当 从塔前 每秒 造成r 点 害。放射塔： 放放射性元素，当 座塔后，每一秒受到g 点 害。干 塔：干 塔 干 的信息素，使得 在 座塔后， 之后每一个 位 度的 成T+b 。当然， 放射塔和干 塔的效果是可以叠加的，也就是 如果 人 x 座放射塔， 那么 人每秒 会受到 x*g 点 害； 同理，如果 人 y 座干 塔， 那么 人 一个 位 度的 将 T+y*b 。 在距离 的下一 攻 有足 的 ，你 个“NewBe_One ” 划的首席工程 在被任命 略 参 ，因此你必 一个 造成最大 害的布塔方案。【 入格式】 入数据 一行， 5 个整数 n, r, g, b, T 中

8、 用一个空格隔开。 它 分 表示你可以布防的 度， 激光塔的效果、 放射塔的效果和干 塔的效果。【 出格式】 出 一个整数，代表你的方案 人 来的最大 害 。【 入 例】5 4 3 2 1【 出 例】82 出 例解 ：第 1 号位置 放射塔，第 2，3 号位置建造干 塔，第4， 5 号位置建造激光塔。【数据范 】 于 30%的数据：1=n=20; 于 60%的数据：1=n=1024;0=r, g, b=65536;0=T=3; 于另外40%的数据：1=n=400;0=r, g, b=231-1;0=t=1000. 四 婪大 【 目描述】面 的 狂 攻，小FF 的 Tower defence 宣

9、告失 人 被 逼到了GreedIsland 上的一个海湾。 在，小FF 的后方是一望无 的大海，前方是 异了的超 。3小 FF 还有大好前程，他可不想命丧于此，于是他派遣手下最后一批改造SCV 布置地雷以阻挡蚂蚁们的进攻。小 FF 最后一道防线是一条长度为N 的战壕， 小 FF 拥有无数多种地雷，而SCV 每次可以在 L , R 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小FF 在某些时候可能会询问你在 L , R区间内有多少种不同的地雷，他希望你能尽快的给予答复。【输入格式】第一行为两个整数 n 和 m； n 表示防线长度， m 表示 SCV 布雷次数及小FF 询问的次数总和。接下来有 m 行， 每行三个整数Q， L , R ； 若 Q=1 则表示 SCV 在 L , R 这段区间布上一种地雷， 若 Q=2 则表示小 FF 询问当前 L ,