欢迎辞欢迎来到“笃志以砺，决起而飞”！ 如果您是第一次来到本站，建议访问 本站导读以便更快地了解本站。 如果您喜欢本站， 欢迎订阅。 | 本解题报告由 Ceeji 编著，转载请注明出处。 [题目描述] Genotype 是一个有限的基因序列。它是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集 合所控制。每个分化的规则可以用三个大写字母A1A2A3表示，含义为基因A1可以分化成A2A3。我们用S代表特种基因，繁殖genotype是从特种 基因序列开始。根据给定的规则，它由被选择控制规则对基因不断进行繁殖而成。 任务 从文本文件GEN.IN 读入一个定义的规则集和一个想生成的genotypes 单词序列。对每一个给定的 genotype，根据给定的分化规则，检查是否它能从某一个确定特种基因序列生成，如果能，找到最小的序列长度，将结果写入文本文件GEN.OUT。 输入 在文件GEN.IN 的第一行有一个整数n, 1 <= n <= 10000. 下面n 每一行为一个分化规则. 这些规则都由包含A – Z的三个大写字母组成. 接下来有一个整数k, 1 <= k <= 10000. 接下来的k 行有一个 genotype. Genotype由没有空格的单词组成，最多100 个英文大写字母. 输出 在文件GEN.OUT中有k行,在第I行应写入: 一个正整数――需要生成第I个genotypes的最小长度；或者单词 NIE, 如果不能生成对应的genotype。 GEN.IN: 6 SAB SBC SAA ACA BCC CBC 3 ABBCAAABCA CCC BA GEN.OUT: [...] 本解题报告版权归 Ceeji 所有，如需转载请注明出处和本注释。 题目描述 单词方程 二元词是一个由0和1组成的非空串。一个单词方程是一个形如X1X2..Xl=Y1Y2..Yr的等式，其中 Xi 和Yj 是二进制数字 (0 和 1) 或者变量（小写英文字母）。每个变量都代表某个固定长度的二元词，这个长度被称作该变量的长度。要解一个单词方程，我们必须赋给每个变量一个适当长度的二元词（这个二元词的长度必须和变量的长度相等），使得当所有变量都用所对应的二元词替换完毕后，等式两边（替换的来的二元词）相同。 请计算一个给定的单词方程的所有解的总数。 例如： 假设a、b、c、d、e 是长度分别为4、2、4、4、2的变量（a的长度是4，b的长度是2……）。则方程1bad1 = acbe有16组不同的解。 求解任务： 请设计一个程序 从文件ROW.IN中读入方程的总数以及每个方程的信息； 求出每个方程解的个数； 将结果写到文件ROW.OUT中。 输入： [...] 本解题报告版权归 Ceeji，转载请保留出处和本注释。 【问题描述】 在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。 现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。 在这个地区住着的猴子有M个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。 【问题】 现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。 【输入要求】 输入文件monkey.in包括： 第1行为一个整数，表示猴子的个数M(2< [...] 生日蛋糕 Birthday Cake Cake.{pas|bas|c} Cake.exe 7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。 由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q= Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 （除Q外，以上所有数据皆为正整数） 输入 有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。 输出 仅一行，是一个正整数S（若无解则S=0）。 样例输入 100 2 样例输出 68 附：圆柱公式 体积V=πR2H 侧面积A’=2πRH 底面积A=πR2 搜索题。 但是,朴素的搜索面临大数据超时的危机-_-|| 所以,剪枝是必要的: 最优化剪枝 k层蛋糕的最小表面积可知(h,r都为整数) 当前s可知 那么,s+剩下层数最小表面积>=min最无需再往下搜了 可行性剪枝 k层蛋糕的最小体积minv可知 k层蛋糕的最大体积maxv可知 那么,剩下的体积v不在minv至maxv的范围内,即可停止搜索 最优化剪枝数据越大功力越强..^-^ 于是便可以写出程序了. 下面是我的程序，并没有加所有的剪枝……不过AC足够了 ?View Code PASCAL1 2 3 4 5 6 7 8 9 10 11 12 13 14 [...] | |
近期评论