枚举法、模拟法

1、专题一、枚举法：所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的，能使命题成立的就是正确的解。例0、最长公共子串（noi93第一题）文件名string.pas, string.in. string.out求N个字符串的最长公共子串，N20，字符串长度不超255。例如N3，由文件依次输入3个字符串为What is locla bus ?Name some local buses .local bus is a high speed I/Obus close to the processor .则最长公共子串为“local bus”长度为9输入

2、：3What is local bus ?Name some local buses .local bus is a high speed I/Obus close to the processor .输出：9例1、 断开的项链（ioi93t1 usacogate/broken necklace）文件名necklace.pas,necklace.in,necklace.out有一条n（3<n<350）个珠子穿成的项链，珠子有红（red）、蓝（blue）、白（white）三种颜色，分别使用字母r,b,w来代表。如图所示： 1 2 1 2 r b b r b r r b r b b b

3、 r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w Figure A Figure B项链可以从某一个位置断开，然后从断开的位置沿着两个方向收集珠子。相同颜色的珠子能被收集到一块，白色的珠子能和蓝色的收集成一堆也能和红色的收集成一堆。问题：给定一个项链，问从哪里断开收集的珠子总个数最多。输入样例：（第一行是一个数字，表示项链中的珠子数；第二行是每个珠子颜色）29wwwbbrwrbrbrrbrbrwrwwrbwrwrrb输出样例：（输出结果是最多收集的珠子个数）1

4、1例2、Prime Palindromes 回文质数pprime.pas因为151即是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 号是回文质数。写一个程序来找出范围a,b(5 <= a < b <= 100,000,000)间的所有回文质数;输入格式：第 1 行: 二个整数 a 和 b .样例输入pprime.in5 500输出格式：输出一个回文质数的列表，一行一个。样例输出：file pprime.out5711101131151181191313353373383例3：一元三次方程求解equation.pas/equation.in/equati

5、on.out问题描述有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个 根。样例输入：1 -5 -4 20输出：-2.00 2.00 5.00例4：最大公约数与最小公倍数问题 gcdlcm.pas/gcdlcm.in/

6、gcdlcm.out问题描述 输入二个正整数x0,y0(2x0100000，2y01000000)，求出满足下列条件的P、Q的个数。 条件:1.P、Q是正整数 2要求P、Q以x0为最大公约数，以y0为最小公倍数。 试求，满足条件的所有可能的两个正整数的个数。样例 输入：x0=3 y0=60 输出：4 说明：(不用输出)此时的 P Q 分别为， 3 60 15 12 12 15 60 3所以，满足条件的所有可能的两个正整数的个数共4种。专题二、模拟法：在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立地推、递归、枚举、回溯等算法。在这种情况下，一般

7、采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数引起的过程状态的变化，由此展开算法。编程的人可以按照题意设计的方法进行模拟，观察模拟过程中参数变化和过程状态的变化，模拟效果取决于过程模拟的真实性和算法的正确性。这一类题目在编程时要注意考虑问题的全面性，不能疏忽特殊条件、边界条件等。例1：津津的储蓄计划(save.pas)【问题描述】津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。

8、因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2004年1月到12月每个月

9、津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20%还给津津之后，津津手中会有多少钱。【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。【输出文件】输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】290230280200300170330

10、50908020060【样例输出2】1580例2：贪婪的送礼者(Greedy Gift Giver)对于一群要互送礼物的朋友，你要确定每个人送出的礼物比收到的多多少(and vice versa for those who view gift giving with cynicism)。在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。给出一群朋友， 没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的

11、比送出的钱多的数目。 PROGRAM NAME: gift1 INPUT FORMAT 第 1 行: 人数NP,2<= NP<=10 第 2到 NP+1 行: 这NP个在组里人的名字一个名字一行第NP2到最后： 这里的NP段内容是这样组织的：第一行是将会送出礼物人的名字。第二行包含二个数字:第一个是原有的钱的数目（在0到2000的范围里），第二个NGi是将收到这个送礼者礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。 SAMPLE INPUT (file gift1.in) 5davelauraowenvickamrdave200

12、3lauraowenvickowen500 1daveamr150 2vickowenlaura0 2amrvickvick0 0 OUTPUT FORMAT 输出 NP 行每行是一个的名字加上空格再加上收到的比送出的钱多的数目。对于每一个人，他名字的打印顺序应和他在输入的2到NP1行中输入的顺序相同。所有的送礼的钱都是整数。每个人把相同数目的钱给每位要送礼的朋友，而且尽可能多给，不能给出的钱被送礼者自己保留。 SAMPLE OUTPUT (file gift1.out) dave 302laura 66owen -359vick 141amr -150例3：题一、乒乓球（Table.pas）

13、【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：WWWWWWWWWWWWW

14、WWWWWWWWWLW在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分

15、是21分制下的结果，两部分之间由一个空行分隔。【输入样例】WWWWWWWWWWWWWWWWWWWWWWLWE【输出样例】11:011:01:121:02:1例4：题一 均分纸牌playcard.pas/playcard.in/playcard.out问题描述有 N 堆纸牌，编号分别为 1，2，, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动

16、次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为：98176移动3次可达到目的：从 取 4 张牌放到 （9 8 13 10） -> 从 取 3 张牌放到 （9 11 10 10）-> 从 取 1 张牌放到（10 10 10 10）。输 入：键盘输入文件名。文件格式：N（N 堆纸牌，1 <= N <= 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）输 出：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。输入输出样例a.in：49 8 17 6屏慕显示：3例5：神经网络【问题背景】 人工神经网络（Arti

17、ficial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。【问题描述】 在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子： 神经元编号为1） 图中，X1X3是信息输入渠道，Y1Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。 神经元按一定的顺序排列，构成

18、整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目） 公式中的Wji（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。 如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。【输入格式】输入文件第一行是两个整数n（1n20）和p。接下来n行，每行两个整数，第i1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wi