欢迎辞欢迎来到“笃志以砺，决起而飞”！ 如果您是第一次来到本站，建议访问 本站导读以便更快地了解本站。 如果您喜欢本站， 欢迎订阅。 | 生日蛋糕 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 [...] 首先声明这个文章不是我原创，功劳归 Matrix67（First Published By Matrix67）但合并，整理 + 改编后效果更好，也删除和添加了一些东西，献给所有需要的人。首先还是从最基础的东西说起。 什么是位运算？ 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算 符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）： 110 AND 1011 ———- 0010 –> 2 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。 Pascal和C中的位运算符号 下面的a和b都是整数类型，则： C语言 | Pascal语言 ——-+————- a & b | a and b a | b | a or b a ^ b | a xor b ~a | not a a << b | a shl b a >> b | a shr b [...] 【本文由 Ceeji 原创，转载请注明出处并保留本注释。】 Bellman-Ford算法（根据发明者 Richard Bellman 和 Lester Ford 命名）是求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。 单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 与迪杰斯特拉算法，（另一种著名的求最短路径的算法）不同的是，在 Bellman-Ford 算法中，路径的权值可以为负数。 设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有路径的权值之和为负。那么通过这个环路，环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。 算法描述 设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目 weight(u,v)表示从结点u到结点v的路径的权值。 Distanz(v)表示从源点s出发到结点v的最短路径的距离，（或者说是从s到v所有的路径中权值的最小值）。【Predecessor(v)表示节 点v的父结点。】在Bellman-Ford算法结束之后，可以输出，G是不是包含一个负环路。如果G不包含负环路，那么Distanz就存储了从s出发 到所有结点的距离。 Bellman-Ford 算法是 SPFA 算法的基础算法。SPFA 算法是 Bellman-Ford 算法的加强版，时间复杂度和适用面都优于 Dijkstra 算法。设G = (V,E,W) 为某一有向带权图（W 即 weight，权值），s，t 分别代表源点和终点，Distance(v) 代表 v 在算法当前阶段中暂定的从源点出发的最短权和，则算法的核心思想是进行至多 |V|-1 次的迭代处理，每次从 s 出发扩展一层路径，逐渐逼近最短路径。 [...] 高斯-塞得尔算法解方程组 {输入方程个数n,再输入n个方程} {例如方程3x+2y=1,2x+7y=0,则输入: 2 3 2 1 2 7 0 } {使用了高斯消元法} program p1052;{解线性方程组} [...] | |
近期评论