下载文档原格式
冲刺NOIP2010模拟试题六（提高组复赛）试题：1.油滴扩展【问题描述】在一个长方形框子里，最多有N（0≤N≤6）个相异的点。
在其中任何一个点上给一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。
必须等一个油滴扩展完毕才能放置下一个油滴。
那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）注：圆的面积公式V=pi*r*r，其中r为圆的半径。
【输入】第一行一个整数N。
第二行为长方形边框一个顶点及其对角顶点的坐标，x，y，x’，y’。
接下去N行，每行两个整数xi，yi，表示盒子内N个顶点的坐标。
以上所有的整数都在[-1000,1000]内。
【输出】一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。
【输入样例】，20 0 10 103 37 7【输出样例】502.数列（sequence）【问题描述】虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。
有一天，她在纸上写了一串数字：1,1,2,5,4。
接着他擦掉了一个1，结果发现剩下1,2,4都在自己所在的位置上，即1在第1为，2在第2为，4在第4位。
她希望擦掉某些数后，剩下的数列中在自己的位置上的数尽量多。
她发现这个游戏很好玩，于是开始乐此不彼地玩起来…不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！【输入】第一行为一个数n，表示数列的长度。
接下来一行为n个用空格隔开的正整数，第i行表示数Ai。
【输出】一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即Ai=i最多能有多少。
【样例】sequence.in51 12 5 4sequence.out3数据规模对于20%的数据，n≤20对于60%的数据，n≤100对于100%的数据，n≤10003.SOFTW ARE一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的多用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能有一个人独立完成而不能由多个人协同完成。
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）。
【输出格式】仅一个整数，表示让所有矿井获得充足电能的最小花费。
【输入样例】454430 2 2 22 03 32 3 0 42 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矿。
Noip2010模拟题由朱全民老师提供PROBLEM 1. SHLQSH数问题描述：我们把t1 , t2 (包括t1 , t2 (1<=t1<t2<=10000000))之间的所有数的约数个数和n 称为t1 , t2的shlqsh数;问题是给出数据t1 , t2后,求t1 , t2的shlqsh数；输入输入文件 shlqsh.in 仅包含一行，共有两个整数，表示t1 t2 (用空格分开)输出输出文件shlqsh.out 仅有一个整数，表示t1 , t2之间的shlqsh数。
输入样例：2 6输出样例：13样例说明：(说明部分不必输出)2的约数有1,2 (2个)；3的约数有1,3 (2个)；4的约数有1,2,4 (3个)；5的约数有1,5 (2个)；6的约数有1,2,3,6 (4个)。
所以2 6 的shlqsh数为13【数据规模】对于50 %的数据,保证有t1,t2<=5000000对于全部的数据,保证有t1,t2<=10000000PROBLEM 2.石材切割问题描述：某人得到一块N*M个小格的矩形石材（可能是玉石），经专家分析，把这个矩形石材的每个小格都有一个价值（使用一个绝对值不大于10的整数来描述），现在将这块石材切割成两块矩形石材，注意，切割只能与该矩形边平行，也就是说不能把矩形的小格切碎，假设每块矩形石材的价值为该矩形中所有小格子价值之和。
问怎样切割，才能使得这两个矩形的价值乘积最大。
如下图是一种比较好的切割方式。
输入格式：输入文件BRICK.IN的第一行为2个正整数N和M，表示石材被划分为N*M个格子。
接下来N行，每行有M个整数，代表这个格子的价值。
输出格式：输出文件BRICK.OUT只有一行，包含一个整数，为两个矩形的价值的最大乘积。
数据范围对于30%的数据，满足N,M≤5。
对于100%的数据，满足N,M≤100。
每个小格的伤害值的绝对值不超过10。
一切数据及中间变量不超过longint范围。
全国信息学奥林匹克联赛全国信息学奥林匹克联赛（（NOIP2010NOIP2010））复赛模拟题复赛模拟题提高组提高组————出题人：pty题目概览 中文题目名称 阳光之春 仲夏之夜 一叶知秋 白雪皑皑 英文题目名称 spring spring summer summer autumn autumn winter winter 可执行文件名 spring spring summer summer autumn autumn winter winter 输入文件名 spring spring..in in s ummer ummer.in .in .in autumn autumn.in .in .in w inter inter.in .in .in 输出文件名 spring spring.out .out .out s ummer ummer.out .out .outa utumn utumn.out .out .out winter winter.out .out .out 每个测试点时限 1秒1秒1秒1秒测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 比较方式 全文比较 全文比较 全文比较 全文比较 题目类型 传统 传统 传统 传统 运行内存上限256M256M256M256M注意事项注意事项：：1. 1. 文件名文件名文件名（（程序名和输入输出文件名程序名和输入输出文件名）。
）。
C/C++2. C/C++中函数中函数main()main()的返回值类型必须是的返回值类型必须是int int，，程序正常结束时的返回值必须是0。
1、阳光之春阳光之春spring.pas/c/cpp).pas/c/cpp)(spring.pas/c/cpp)【问题描述】春天静悄悄地来了。
HJ站在窗前，欣赏着这和谐的万物。
他背着手，慢步踱行，吟诵道：“春色满园关不住，一枝红杏出墙来”，好诗啊！（HJ不愧是有知识的人）。
金华一中信息学奥林匹克联赛（NOIP2010）复赛模拟试题（十八）一、题目概览二、运行内存限制1.买鱼方案(fish.pas)【问题描述】对于每种鱼，每个人最多每一条，并且有些鱼不能一起买，因为他们之间会互相争斗吞食。
现在资金有限，希望买最多的鱼，如果有多个方案都能买最多的鱼，输出花费资金最多的方案。
【输入格式】第一行两个正整数M（M<=1000）和N(N<=30)，分别表示资金和鱼的种类数。
一下N行，每行两个正整数，S（1<=S<=N）和T(T<=1000)，分别表示某种鱼的编号和价格。
接下来每行有两个整数数P和Q。
当P，Q均大于0时，表示P，Q不能共处，当P，Q均等于0时，表示输入文件的结束。
【输出格式】第一行两个正整数X,Y，分别表示所买鱼的条数和总花费。
接下来X行，每行一个正整数，表示所买鱼的编号，编号按升序排列输出。
若存在多解，只需要输出其中的一种。
【输入样例】170 71 702 503 304 405 406 307 201 41 73 43 55 76 70 0【输出样例】4 16024562. 公路建设(road.pas)【问题描述】A国有N个城市，按1，2，3…，N编号。
政府想大搞公路建设，提供了优惠政策：对于每一个投资方案的预计总费用，政府负担50%，并允许投资的公司对过往的汽车收取连续5年的养路费。
世界各地的大公司纷纷投资，并提出了自己的建设方案，方案内容包括：公路连接的两座城市的编号，预计的总费用（假设他们的预计总是准确的）。
作为A国公路规划局的总工程师，有权利决定每一个方案是否接受，但是政府的要求是：（1）要保证各个城市之间都有公路直接或者间接相连（2）政府负担最少的费用（3）因为大公司并不是同时提出方案，政府希望每接到一个方案，就可以知道当前需要负担的最小费用和接受的投资方案，以便随时开工。
关于你给投资公司的回复可以等到开工以后再给。
A国一开始是没有公路的。
NOIP2010初赛模拟试题（六）（普及 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●一．单项选择题（共20题,每题1.5分,共计30分。
每题有且仅有一个正确答案。
）1、.在所有由两个1和六个0组成的8位二进制整数（补码）中，最小的数是：（）A．-127B．-64 C．-128 D．-652、.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同3、下面有效的IP地址是：（）A．202.280.130.45 B．130.192.33.45C．192.256.130.45 D．280.192.33.4564、一台具有1024*768分辨率、可显示65 536种颜色的显示器，其显示适配器（显示卡）上显示存储器容量的配置为：（）A．512K B．1MB C．大于1.6MB，小于2MB D．2MB5、进行二分法查找，则线性表（）A．必须顺序方式存储B．必须以链接方式存储，且数据元素已按值排好序C．必须以链接方式存储D．必须以顺序方式存储，且数据元素已按值排好序6、机器语言是用（）编写的。
A．二进制码B．ASCII码C．十六进制码D．国标码7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若 A[k]是叶子结点,则k的最小值是：（）A．51 B．50 C．49 D．488、不同的计算机，其指令系统也不相同，这主要取决于（）A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言9、计算机主机是由CPU 与（）构成的。
A．控制器B。
输入、输出设备C．运算器D．内存储器10、计算机系统总线上传送的信号有（）。
A．地址信号与控制信号B．数据信号、控制信号与地址信号C．控制信号与数据信号D．数据信号与地址信号11、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。
冲刺Noip2010模拟试题七１、数列(Sequence.pas/c/cpp)问题描述一个数列定义如下：f(1) = 1，f(2) = 1，f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。
给定A,B和n的值，要求计算f(n)的值。
输入格式输入文件(sequence.in)仅一行包含3个整数A，B和n，其中(1≤ A, B ≤1000, 1 ≤n≤100,000,000)。
输出格式输出文件(sequence.out)仅一行，一个整数，即f(n)的值。
输入样列1 1 3输出样列2说明：若输入样例为1 2 10，则输出为5。
数据规模20%的数据，n≤1,00040%的数据，n≤100,000100%的数据，n≤100,000,000２、最长路(path.pas/c/cpp)问题描述设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当<i，j>为G中的一条边时有i < j。
设w（i，j）为边<i，j>的长度，请设计算法，计算图G中<1，n>间的最长路径。
输入格式输入文件path.in的第一行有两个整数n和m,表示有n个顶点和m条边，其中(2≤n≤1500，m≤50000)，接下来m行中每行输入3个整数a ，b，v表示从a点到b点有条边，边的长度为v。
输出格式输出文件path.out，一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。
输入样例2 11 2 1输出样例1说明：若输入样例为2 0，则输出为-1。
数据规模20%的数据，n≤100，m≤100040%的数据，n≤1,000，m≤10000100%的数据，n≤1,500，m≤500003、木棍(wooden.cpp/pas/c)问题描述有n根木棍，每根的长度l和重量w已知。
这些木棍将被一台机器一根一根的加工。
机器需要一些启动时间来做准备工作，启动时间与木棍被加工的具体情况有关。
描述Description【问题描述】在一个夜黑风高，伸手不见五指的深夜，睡梦中的林月如突然听到房外一阵躁动。
她出去一看，发现一个女飞贼抢了一个古董商的包袱。
"站住！""那你为什么不来追我？""因为程序设计，在李大哥来之前，我不能追你。
""那李逍遥为什么不来呢？""大概程序出bug了吧"………………………………………………终于，在等了一个又一个时辰后，林月如终于忍不住了，开始向女飞贼发起进攻。
"喂！你为什么可以动？？？""这大概也是一个bug吧！""不公平啊！""废话少说。
"已知林月如和女飞贼站在一个矩阵中，矩阵中有某些障碍物不可穿越。
月如使出的铜钱镖可攻击8个方向，但不可穿越障碍物（可视为不能穿墙的重狙）。
每个单位时间，月如可向上下左右4个方向移动一格，攻击不浪费时间。
当然，月如想尽快结束这场无聊的战斗，所以她想在最短的时间内消灭女飞贼。
【输入格式】第一行为2个数N,M表示矩阵的规模(N为高,M为宽)。
接下来是N*M的矩阵,O表示空地,X表示障碍物。
下面是若干行数据，每行为一对数据，分别是女飞贼的位置和林月如的位置，显然她们都不可能在障碍物上。
以"0 0 0 0"为输入结束标志。
【输出格式】每一组数据输出一行，仅一个整数，表示能消灭掉女飞贼的最短时间。
显然若能直接打到女飞贼，则时间为0。
若无法消灭，则输出"Impossible!"。
（不含引号）【输入样例】3 4OXXOXXOOXOOO3 2 2 43 3 1 10 0 0 0【输出样例】1Impossible!【数据规模】对于30%的数据,有N*M<=100对于50%的数据,有N*M<=400对于100%的数据,有N*M<=20000对于100%的数据,测试数据组数不超过20组【时间限制】1s【来源】经典问题描述Description【问题描述】今年是虎年，小老虎一年来过得可充实了，一有时间就往电脑室跑，因为他要在“在线测试”系统上拿第一名，成为做题最多的牛人。
2010年NOIP模拟试题(一)题目名称开灯速算24点生日派对餐馆服务员【附加】电子表提交程序Light fun party service watch输入文件light.in fun.in party.in service.in watch.in输出文件light.out fun.out party.out service.out watch.out时间限制1s 1s 1s 3s 1内存限制64MB 64MB 64MB 64MB 64MB1、开灯（light.pas/c/cpp; 时限:1s; 64MB）【问题描述】在一条无限长的路上，有一排无限长的路灯，编号为1,2,3,4,…每一盏灯只有两种可能的状态，开或者关。
如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。
如果原来是开，将变成关。
如果原来是关，将变成开。
在刚开始的时候，所有的灯都是关的。
胖胖每次可以进行如下的操作：指定两个数a,t（a为实数，t为正整数）。
将编号为[a],[a*2],[a*3],…,[a*t]的灯的开关各按一次。
其中[k]表示实数k的整数部分。
在胖胖进行了n次操作后，胖胖突然发现，这个时候只有一盏灯是开的，胖胖很想知道这盏灯的编号，可是这盏灯离胖胖太远了，胖胖看不清编号是多少。
幸好，胖胖还记得之前的n次操作。
于是胖胖找到了你，你能帮他计算出这盏开着的灯的编号吗？【输入格式】第一行一个正整数n，表示n次操作。
接下来有n行，每行两个数a i,t i。
其中a i是实数，小数点后一定有6位，t i是正整数。
【输出格式】仅一个正整数，那盏开着的灯的编号。
- 1 -31.618034 132.618034 71.0000000 21【输出样例】20【数据规模】记T=t1+t2+t3+…+tn对于30%的数据，满足T≤1000对于80%的数据，满足T≤200000对于100%的数据，满足T≤2000000对于100%的数据，满足n≤5000，1≤ai≤1000，1≤ti≤T数据保证，在经过n次操作后，有且只有一盏灯是开的，不必判错。
第十六届全国青少年信息学奥林匹克联赛(NOIP2010)提高组 Pascal语言两小时完成一、单向选择（每道题1.5分）1.与16进制数 A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是( )。
A. exeB. comC. dllD. 以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。
A. 克劳德•香农B. 戈登•摩尔C. 查尔斯•巴比奇 D. 冯•诺依曼7.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。
A. 23B. 25C. 37D. 658.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A. 寄存器B. 高速缓存C. 闪存D. 外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A. 2kB. 2k+1C. k/2下取整D. (k+1)/210. 以下竞赛活动中历史最悠久的是（）。
A. NOIPB. NOIC. IOID. APIO二、不定向选择（每道题1.5分）1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。
江苏省金湖中学08、09、10级信息学奥赛组NOIP2010初赛模拟练习(三)1、下面一段程序是用（）语言书写的。
int func1(int n){int i,sum=0;for(i=1;i<=n;i++)sum+=i*i;return sum;}A)FORTRAN B)PASCAL C)C D) PROLOG E)BASIC2、多媒体计算机是指()计算机。
A)专供家庭使用的B)装有CD-ROM的B)连接在网络上的高级D)具有处理文字、图形、声音、影像等信息的3、在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是()。
A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置B)文本框中的图形不可以衬于文档中输入的文字的下方。
C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可实现文字环绕。
D)将图形放入文本框后,文档中输入的文字不能环绕图形。
4、计算机软件保护法是用来保护软件()的。
A)编写权B)复制权C)使用权D)著作权5、64KB的存储器用十六进制表示，它的最大的地址码是()A)10000B)FFFF C)1FFFF D)EFFFF6、在外部设备中，绘图仪属于（）A.输入设备B.输出设备C.辅（外）存储器D.主（内）存储器7、某种计算机的内存容量是640K，这里的640K容量是指（）个字节A.640B.640*1000C.640*1024D.640*1024*10248、已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。
试问：A（5，8）的起始地址为（）A.SA+141B.SA+180C.SA+222D.SA+2259、电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。
这些线段可分为两类；一类是两端的小鸟相同；另一类则是两端的小鸟不相同。
冲刺NOIP2010模拟试题与解析（普及组复赛）湖南省长沙市第一中学周祖松一、数数(count.pas/c/cpp)【问题描述】小可可正在学习怎么用手指数数。
当爸爸问她“n(1 ≤ n ≤ 10)是多少”，小可可的回答就是竖起n个手指头。
为了让问题简单一些，爸爸告诉她正确的手指表示方式：(1)这个数可以用一只手或两只手表示；(2)如果这个数用两只手表示，大的数会先给出。
比如爸爸问她“4是多少”，小可可有3种表示方法：(1)一只手竖起出4个手指头；（可以是左手也可是右手，只算一种）(2)一只手竖起出3个手指头，另一只手竖起出1个手指头；(3)一只手竖起出2个手指头，另一只手竖起出2个手指头；你的任务是，对于爸爸的提问，确认小可可有几种正确的回答方法。
【输入】输入文件count.in共一行为一个1到10之间的整数。
【输出】输出文件count.out共一行为一个整数，表示方法总数。
【样例输入】4【样例输出】3二、分数树(fraction.pas/c/cpp)【问题描述】十九世纪的时候，Moriz Stern (1858)与Achille Brocot (1860)发明了“一棵树”。
据说，经由一些简单的规则而产生的这一棵树上，可以包含零以上所有的有理数。
这棵树看起来大致这样：你观察出规则了吗？首先,他们在第一列放两个“分数”，第一个是0 / 1，代表0；第二个是1 / 0，代表无穷大。
接着他们一列一列地产生这棵树,当他们要产生第k+1列的时候,就先把前k列所有的分数按照大小排成一列（假设有n个），在这些数之间会有n - 1个间隔，那么第k + 1列就准备产生n - 1个数，其值的分子恰好是左右两个数的分子的和、分母是左右两个数的分母的和。
例如，2 / 3，而它的2就是左边1 / 2的1和右边1 / 1的分子1相加的结果；而2 / 3的3，则是1 / 2的2加上1 / 1的分母1而得。
从这棵树中，我们可以看出，每个正的最简分数在这棵树中恰好出现一次，我们用字母“L”和“R”分别表示从树根(1 / 1)开始的一步“往左走”和“往右走”，则每一个数都可以由L和R 组成的序列表示。
冲刺NOIP2010模拟试题五（提高组复赛）无穷的序列（seq）【问题描述】有一个无穷序列如下：110100100010000100000…请你找出这个无穷序列中指定位置上的数字【输入】第一行一个正整数N，表示询问次数；接下来的N行每行一个正整数Ai，Ai表示在序列中的位置。
【输出】N行，每行为0或1，表示序列第Ai位上的数字。
【输入样例】431476【输出样例】1【数据范围】对于100%的数据有N≤1500000，Ai≤10^9汤姆斯的天堂梦（par）【问题描述】汤姆斯生活在一个等级为0的星球上。
那里的环境极其恶劣。
每天12小时的工作和成堆的垃圾让人忍无可忍。
他向往着等级为N的星球上天堂般的生活。
有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。
汤姆斯预先知道了从0等级星球去N等级星球的所有的航线和所需支付（或者可以得到）的金钱，他想找一条价格最低（甚至获得金钱最多）的航线。
【输入】第一行第一个正整数N（N≤100），接下来的数据可分为N个段落。
每段的第一行一个整数Ki（Ki≤100），表示等级为i的星球有Ki个。
接下来的Ki中第Tij行依次表示与等级为i，编号为j的星球相连的等级为i-1的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。
每行以0结束，每行的航线数≤100。
【输出】输出所需（或所得）费用。
正数表示支出，负数表示收益。
【输入样例】321 15 01 5 031-52 10 01 3 02 40 021 12 53 -5 02-19 3-20 0【输出样例】-1【数据范围】对于100%的数据N≤100 Ki≤100。
【样例解释】如图克鲁斯的加减法（plus）【问题描述】奶牛克鲁斯认为人类的加法算式太落后了。
比如说有时候想要用加法计算+15*3.，只能写成+15+15+15。
真是浪费精力啊！于是，克鲁斯决定开发出一种新的加法算式。
NOIP 提高组复赛模拟题（一）1.中位数（median .pas/c/cpp ）【问题描述】给出1~n 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b 。
中位数是指把所有元素从小到大排列后，位于中间的数。
【文件输入】第一行为两个正整数n 和b ，第二行为1~n 的排列。
【文件输出】输出一个整数，即中位数为b 的连续子序列个数。
【样例输入1】 5 4 1 2 3 4 5 【样例输出1】 2 【样例输入2】6 31 2 4 5 6 3【样例输出2】1【样例输入3】7 45 7 2 4 3 1 6【样例输出3】4第三个样例解释：{4}，{7，2，4}，{5，7，2，4，3}和{5，7，2，4,3，1，6}2. 打砖头（brike .pas/c/cpp ）【问题描述】在一个凹槽中放置了n 层砖块、最上面的一层有n 块砖，从上到下每层依次减少一块敲掉第i-1层的第j 和第j+1块砖。
你现在可以敲掉最多m 块砖，求得分最多能有多少。
【文件输入】输入文件的第一行为两个正整数n 和m ；接下来n 行，描述这n 层砖块上的分值a[I][j],满足0≤a[i][j] ≤100。
【文件输出】输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。
【样例输入】4 52 23 48 2 72 349【样例输出】19【数据规模】对于20%的数据，满足1≤n≤10，1≤m≤30；对于100%的数据，满足1≤n≤50，1≤m≤500；3.合并序列(sequence.pas/c/cpp)【问题描述】有两个长度为N的序列A和B，在A和B中各任取一个数相加可以得到N2个和，求这N2个和中最小的N个。
【文件输入】第一行输入一个正整数N；第二行N个整数A i且A i≤109；第三行N个整数B i且B i≤109。
【文件输出】输出仅一行，包含n个整数，从小到大输出这n个最小的和，相邻数字之间用空格隔开。
【输入1】51 32 4 56 3 4 1 7【输出1】2 3 4 4 5【数据规模】对于50%的数据，满足1≤N≤1000；对于100%的数据，满足1≤N≤100000;4. 最小密度路径（path.pas/c/cpp）【问题描述】给出了一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。
冲刺NOIP 2010 模拟试题（十）（普及组）一、手机（mobile.pas）【问题描述】一般的手机的键盘是这样的：X就得按9两下，第一下会出w，而第二下会把w变成x。
0键按一下会出一个空格。
你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。
【问题输入】一行一个句子，只包含英文小写字母和空格，且不超过200个字符。
【问题输出】一行一个整数，表示按键盘的总次数。
【样例输入】I have a dream【样例输出】23【数据范围】如题目所示二、数字积木（brick.pas）【问题描述】小明有一款新式积木，每个积木上都有一个数，一天小明突发奇想，要是把所有积木排成一排，所形成的数目最大是多少呢？你的任务就是读入n个数字积木，求出所能形成的最大数。
【问题输入】第一行是一个整数n（n<=1000），接下来n行每行是一个正整数。
【问题输出】所能形成的最大整数。
【样例输入】313131343【样例输出】34313131【数据范围】30%的数据，n<=10，每个数<10^3。
50%的数据，n<=100。
100%的数据，n<=1000，每个数<10^200。
三、家族（family.pas）【问题描述】在一个与世隔绝的岛屿上，有一个有趣的现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同的姓氏。
现在给你的岛上的地图有n行，每行有若干列，每个格子中要么是“”，表示大海，要么是“*”，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。
【问题输入】第一行是个数字N，表示下面信息的行数。
接下来是N行字符，每行由小写字母和*号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过200个字符。
【问题输出】一个数字，表示家族数。
福建省长乐一中NOIP2010模拟赛2题1 神奇的风【问题描述】T博士最近在研究一种神奇的风。
这种风有一个源头，称之为“风口”。
风口的风要么是顺时针的，要么是逆时针的。
这种风是有能量的。
这种风是能传播的，如果风口周围都能传播风，风会像这样产生下一级的风：（箭头表示风的转向，最中间的是风口，图中风口的风是顺时针的，对于风口的风是逆时针的情形可通过物理模型想象一下或由这个图推理。
）产生的下一级风的能量依据新产生的风所在的地形决定，有两种可以传递这种风的地形：一、平地，下一级风的能量与风口的风能量相等．．，这种地形用“.”表示。
二、少量障碍物，下一级风的能量是风口的风能量的一半．．，这种地形用“*”表示。
每个新产生的风都能作为新的风口继续产生下一级风。
此外，还有一种地形是不能传递风的：大量障碍物，用“#”表示。
如果在风口的某一方向是“#”地形，则该方向不会产生下一级风，其他方向视该位置．．．．．．．．的地形而定，就是说，如果是“．．．．．．．．．．．。
．．．．．．．．．．．．．．.．”或“．．．*．”地形则该方向照样传播T博士还发现了这种神奇的风的叠加规则：两股风叠加时，无论它们的转向是否相同，都只保留能量较大的那股风．．．．．．．．．．．，即风叠加后的能量和转向都与叠加前能量较大的那股风相同。
而如果叠加的两股风的能量相同且转向相同，则保留其中任意一股。
两股风能量相同且转向不同时叠加的情况未知，因为T博士至今还没碰到这样的情况。
T博士画了几张地图，他想知道地图上的某点风的转向和能量。
【输入格式】输入文件wind.in的第一行是两个整数m和n，表示地图大小为m行n列。
接下来的m行，每行是n个字符，只会是以下的几种：“S”表示风口，保证图中有且仅有一个“S”。
“E”表示目的地，即T博士想知道的那个点。
“.”“*”“#”见描述。
第m+2行是一个整数“0”或“1”，分别表示风口的风是顺时针方向或逆时针方向。
约定“S”处的风能量为16384，“S”和“E”处的地形均为平地。
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.。
