NOIP2010 模拟试题
故事背景：
话说小FF在经历了上次“寻找古代王族遗产”的探险后，成为了世界上最伟大的探险家并拥有了一大笔财富。

当然他不能坐吃山空，必须创造财富！！于是他买下了传说中的Greed Island并优先发展那里的采矿业……他还将其称为Greed Island的“NewBe_One”计划。

试题一：
新的开始
【题目描述】
发展采矿业当然首先得有矿井，小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应，小FF想到了两种办法：
1、在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。

2、将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为p。

小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。

【输入格式】
第一行一个整数n，表示矿井总数。

第2～n+1行，每行一个整数，第i个数v[i]表示在第i口矿井上建立发电站的费用。

接下来为一个n*n的矩阵P，其中p[ i , j ]表示在第i口矿井和第j口矿井之间建立电网的费用（数据保证有p[ i, j ] = p[ j, i ], 且p[ i, i ]=0）。

【输出格式】
仅一个整数，表示让所有矿井获得充足电能的最小花费。

【输入样例】
4
5
4
4
3
0 2 2 2
2 0
3 3
2 3 0 4
2 3 4 0
【输出样例】
9
输出样例说明：
小FF可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网，总花费是3+2+2+2 = 9。

【数据范围】
对于30%的数据：1<=n<=50;
对于100%的数据：1<=n<=300; 0<=v[i], p[i,j] <=10^5.
试题二
工业时代
【试题描述】
小FF的第一片矿区已经开始运作了，他着手开展第二片矿区……
小FF的第二片矿区，也是”NewBe_One“计划的核心部分，因为在这片矿区里面有全宇宙最稀有的两种矿物，科学家称其为NEW矿和BE矿。

矿区是被划分成一个n*m的矩形区域。

小FF探明了每一小块区域里的NEW矿和BE矿的蕴藏量，并且小FF还在矿区的北边和西边分别设置了NEW矿和BE矿的收集站。

你的任务是设计一个管道运输系统，使得运送的NEW矿和BE矿的总量最多。

管道的型号有两种，一种是东西向，一种是南北向。

在一个格子内你能建造一种管道，但不能两种都建。

如果两个同类型管道首位相接，它们就可以被连接起来。

另外这些矿物都十分不稳定，因此它们在运送过程中都不能拐弯。

这就意味着如果某个格子上建有南北向管道，但是它北边的格子建有东西向管道，那么这根南北向管道内运送的任何东西都将丢失。

进一步地，运到NEW矿收集站的BE矿也会丢失，运到BE矿收集站的NEW 矿也会丢失。

【输入格式】
第一行包含两个整数n和m，表示矿区大小。

以下n行，每行m个整数，其中第i行第j个整数G[ i , j ] 描述各个格子上的BE矿数量。

接下来以类似的矩阵表示各个格子上的NEW矿数量。

【输出格式】
仅一个整数，表示最多可以采集到的NEW矿和BE矿的总量。

【输入样例】
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
【输出样例】
98
【数据范围】
对于30%的数据：0<= n，m <=100;
对于100%的数据：0<= n, m <=1000;
0<= G[ i, j ] <=1000.
试题三：
杀蚂蚁
【题目描述】
说“善有善报，恶有恶报，不是不报……”。

小FF一心只顾自己企业的壮大而没顾及自己的采矿业对Greed Island上生态环境的破坏，Greed Island的环境日益恶劣。

终于，岛上的蚂蚁们变异了，它们决定对小FF的矿区进行攻击，欲将岛上的人类驱逐出去……面对蚂蚁
们的进攻，人类节节败退。

无奈之下，小FF请来了全宇宙最强的防御系统制造商派来的工程机器人——SCV，希望能够阻挡蚂蚁的攻势。

经过小FF的研究，他发现蚂蚁们每次都走同一条长度为n个单位的路线进攻，且蚂蚁们的经过一个单位长度所需的时间为T秒。

也就是说，只要小FF在条路线上布防且给蚂蚁造成沉痛伤害就能阻止蚂蚁的进军。

SCV擅长制造的防御塔有三种，分别是激光塔，放射塔和干扰塔，他们可以在一个单位长度内修建一座防御塔。

三种防御塔的作用如下：
激光塔：使用高能激光，当蚂蚁从塔前经过时每秒对蚂蚁造成r点伤害。

放射塔：释放放射性元素，当蚂蚁经过这座塔后，每一秒受到g点伤害。

干扰塔：干扰塔负责干扰蚂蚁们的信息素，使得蚂蚁在经过这座塔后，经过之后每一个单位长度的时间变成T+b。

当然，放射塔和干扰塔的效果是可以叠加的，也就是说如果敌人经过x座放射塔，那么敌人每秒钟会受到x*g点伤害；同理，如果敌人经过y座干扰塔，那么敌人经过一个单位长度的时间将变为T+y*b。

现在距离蚂蚁的下一轮进攻还有足够长的时间，你这个“NewBe_One”计划的首席工程师现在被任命为战略总参谋长，因此你必须设计一个给蚂蚁们造成最大伤害的布塔方案。

【输入格式】
输入数据仅一行，5个整数n, r, g, b, T中间用一个空格隔开。

它们分别表示你可以布防的总长度，激光塔的效果、放射塔的效果和干扰塔的效果。

【输出格式】
输出仅一个整数，代表你的方案给敌人带来的最大伤害值。

【输入样例】
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<=2^31-1;
0<=t<=1000.
试题四
贪婪大陆
【题目描述】
面对蚂蚁们的疯狂进攻，小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。

现在，小FF的后方是一望无际的大海，前方是变异了的超级蚂蚁。

小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 , R ]区间总共有多少种地雷。

【输出格式】
对于小FF的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

【输入样例】
5 4
1 1 3
2 2 5
1 2 4
2 3 5
【输出样例】
1
2
【数据范围】
对于30%的数据：0<=n, m<=1000;
对于100%的数据：0<=n, m<=10^5.。