输出样例 3
题11.生物基元问题
一个生物体的结构可以用“基元”的序列表示,一个“基元\用一些英文字符串表示。对于一个基元集合P,可以将字符串S看作由n个基元P1,P2,?,Pn依次连接而成的。问题是给定一个字符串S和一个基元集合P,使S的前缀可由P中的基元组成。求这个前缀的最大长度。基元的长度最大为20,字符中的长度最大为500000.例如基元集合为{A,AB,BBC,CA },字符串为ABACABBCAACCB,则最大长度为10,其具体组成为
ABACABBCAA
22 144333 11
题12. 双塔
2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“911”事件，Mr. F决定自己用水晶来搭建一座双塔。Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。
给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。
输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。 输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。 样例输入： 5
1 3 4 5 2 样例输出： 7
题41。过河river.pas/ river.exe/ river.c/ river.cpp
【问题描述】河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
【输入文件】输入文件river.in的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数，其中1≤S ≤T≤10,1 ≤M ≤100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【输出文件】输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 【样例输出】 【数据规模】 10 2 对于30%的数据，L <= 10000； 2 3 5 对于全部的数据，L <= 109。 2 3 5 6 7
5 4 B(9,5) 北
线性动规
题22。1997年普及组第3题---街道路径条数 【问题描述】
设有一个N*M(l≤N≤50, l≤M≤50)的街道(如右图)： 规定行人从A(1,1)出发,在街道上只能向东或向北方向行 走。如图,从(1,1)点出发,至(3,3)点,共有6条不同的路径：
(1,1)-(2,1)-(3,1)-(3,2)-(3,3)； (1,1)-(2,1)-(2,2)-(3,2)-(3,3)； (1,1)-(2,1)-(2,2)-(2,3)-(3,3)；(1,1)-(1,2)-(2,2)-(3,2)-(3,3)；
(1,1)-(1,2)-(2,2)-(2,3)-(3,3)； (1,1)-(1,2)-(1,3)-(2,3)-(3,3)；若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用阴影线表示的部分。此矩形障碍区域可以用2对顶点坐标给出,如上图中的障碍区域以2对顶点坐标(2,2),(8,4)表示。此时,从A(1,1)出发至B(9,5),只有两条路径：
路径一：(1,1)-(2,1)-(3,1)-(4,1)-(5,1)-(6,1)-(7,1)-(8,1)-(9,1)-(9,2)-(9,3)-(9,4)-(9,5) 路径二：(1,1)-(1,2)-(1,3)-(1,4)-(1,5)-(2,5)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(8,5)-(9,5)
程序要求：任务一：给出N,M后,求出所有从(1,1)出发到达(N,M)的路径的条数。 任务二：给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,Y1), (X2,Y2), 然后求出此种情况下所有从(1,1)出发到达(N,M)的路径的条数。
【输入格式】输入文件street.in的第一行只有一个数字,1代表任务一,2代表任务二。 1)任务一：第二行有两个数字,表示N和M 2)任务二：第二行有两个数字,表示N和M； 第三行有两个数字,表示矩形障碍的左下角坐标； 第四行有两个数字,表示矩形障碍的右上角坐标；
【输出格式】输出文件street.out的只有一个数字,表示求得的路径条数。
3 2 1 A(1,1) 1 2 3 4 5 6 7 8 9 东
【输入样例1】 1 3 3
【输出样例1】 6
【输入样例2】 2 9 5 2 2 8 4
【输出样例2】 2
A(0,0) 0 1 2 3 4 5 6 7 8 题23。2002年普及组第4题--过河卒
P4 0 P5 【问题描述】
1 P6 P3 如右图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以 2 C 向下、或者向右。同时在棋盘上的某一点有一个对方的马(如上图的C 3 P2 点),该马所在的点和所有跳跃一步可达的点称为马的控制点。例如右 P7 P8 P B(4,8) 14 Y 图C点上的马可以控制9个点(图中的P1,P2,?,P8和C)。卒不能通过 对方马的控制点。棋盘用坐标表示,A 点坐标为(0,0)、B 点坐标为(n,m)
(n,m为不超过 20 的整数),同样马的位置坐标是需要给出的(约定点:C≠点A,同时点C≠点B)。现在要求你计算出卒从A 点到达 B 点的路径的条数。 【输入格式】输入文件p4.in只有一行数据,该行中有4个以空格分隔的数,表示B点的坐标和马的坐标 【输出格式】输出文件p4.out只有一行数据,该行只有一个数,表示求得的路径条数。 【输入样例】 6 6 3 2 【输出样例】 17
题24。1997年普及组第1题---统计正方形和长方形个数 【问题描述】
设有一个n*m方格的棋盘(1≤m,n≤1000),求出该棋盘中包含多少个正方形、多少个长方形(不包括正方形)。例如：当n=2,m=3时, 正方形的个数有8个；长方形的个数有10个；
【输入格式】输入文件square.in只有一行数据,包含2个以逗号分隔的数,分别代表n和m 【输出格式】输出文件square.out只有一行数据,包含2个以逗号分隔的数,分别代表正方形的个数和长方形的个数。 【输入样例】 2,3
【输出样例】
8,10
马 题25。1997年提高组第3题-骑士游历
【问题描述】
设有一个n*m的棋盘(2≤n≤50,2≤m≤50) ,在棋盘上左下角(1,1)处有一个中国
图1 马的4种走法 象棋马。马走的规则为：(1)马走日字；(2)马只能向右走。如图1所示。
任务1：当n,m输入之后,找出一条从左下角到右上角的路径。若不存在路径,则输出'NO' y 例如,如图2所示,输入：n=4,m=4,则输出路径：(1,1)-(2,3)-(4,4)(不唯一)
10 任务2：当n,m给出之后,同时给出马起点的位置和终点的位置,试找出从
9 起点到终点的所有路径的数目。如图3所示,给出马的起点坐标为(1,8),终
8 点坐标为(3,8),则有2条路径。 图3: 马从(1,8)至 7 【输入格式】 (3,8)有2条路径 6 从文件horse.in输入,第一行只有一个数字,1代表任务1,2代表任务2。
5 1)任务1：第2行有两个数,表示右上角坐标(n,m)
4 2)任务2：第2行有两个数,表示右上角坐标(n,m)
3 图2: 马从(1,1)至 第3行有两个数,表示起点坐标(x1,y1)
2 (4,4)的一条路径 第4行有两个数,表示终点坐标(x2,y2) 1 【输出格式】 X 1 2 3 4 输出至文件horse.out中。1)任务1：输出一条路径。2)任务2：输出一个数,表示路径数。 【输入样例1】 【输出样例1】 1 (1,1)-(2,3)-(4,4) 4 4
【输入样例2】 【输出样例2】 2 2 10 10 1 8 3 8
题26。2000年提高组第4题--方格取数
A点 0 0 0 0 0 0 0 0 【问题描述】
设有N*N的方格图(N<=30,我们将其中的某些方格中填入正整数, 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 而其他的方格中则放入数字0。如右图所示,表示样例数据的情况.
0 0 0 14 0 0 0 0 某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到
0 21 0 0 0 4 0 0 到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的
0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B点
方格中将变为数字0)。此人从A点到B 点共走两次,试找出2条这样 的路径,使得取得的数之和为最大。
【输入格式】输入文件4.in的第一行为一个整数N(表示N*N的方格图),
接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束
【输出格式】输出文件4.out中中只有一行数据,该行只有一个数字,表示2条路径上取得的最大的和。 【输入样例】 【输出样例】 8 67 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0
题27。NOIP2003年普及组第3题--栈(p2003_3.pas) 【问题背景】
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。 【问题描述】
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）使用这两种操作,由一个操作数序列就可以得到一系列的输出序列。你的程序将对给定的n，计算并输出由操作数序列1，2，?，n经过操作可能得到的输出序列的总数。
【输入格式】输入文件STACK.in只含一个整数n（1≤n≤18）
【输出格式】输出文件STACK.out只有一行，即可能输出序列的总数目 【输入样例】 【输出样例】 3 5 【思考】
如果1≤n≤3000，如何做？