Ephemeral-fever

概述1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。 在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间)。 AOE网AOE网（Activity On Edge）即边表示活动的网，是与AOV网（顶点表示活动）相对应的一个概念。而拓扑排序恰恰就是在AOV网上进行的，这是拓扑排序与关键路径最直观的联系。AOE网是一个带权的有向无环图，其中顶点表示事件（Event），弧表示活动，权表示活动持续的时间。下面的就是一个AOV网： 其中$V_{1},…,V_{9} $表示事件，a_{1},a_{2}…,a_{11} 表示活动，活动的取值表示完成该活动所需要的时间，如$a_{1}=6$表示完成活动$a_{1}$所需要的时间为6天。此外，每一事件$V_{i}$表示在它之前的活动已经完成，在它之后的活动可以 ...

问题描述有n种物品，它们有各自的体积，价值和一定的数量。现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 算法思想在解决问题之前，为描述方便，首先定义一些变量：vi表示第 i 种物品的价值，wi表示第 i 种物品的体积或重量，si表示第i种物品的数量。定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值。 多重背包问题其实可以转换为01背包来解决，那么如何转换呢？有一种朴素思想：对于同一种物品，如果我们把不同数量的该物品看作一个新品种，那么这种物品不就化成了很多个新品种但每种只有1个，这不就变成了01背包了吗。 不妨设第i件物品有s个，我们可以把相同种类的物品进行合并。比如我拿出两件合并出一个新的物品，我拿出三件合并出另一个新的物品。依此类推，我拿出s个合并出一个新的物品。基于这种思想，我们可以把第i件的s个物品转换为s种体积价值各不相同的物品，然后再用01背包的思想，求出最优解! 于是可以列出状态转移方程： j<w(i) V(i,j)=V(i-1,j) j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j ...

A第几天2000年的1月1日，是那一年的第1天。那么，2000年的5月4日，是那一年的第几天？注意：需要提交的是一个整数，不要填写任何多余内容。 答案：125 31+29+31+30+4=125 B明码汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。 16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。 一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。 把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节， 一共16行，布局是： 第1字节，第2字节第3字节，第4字节…第31字节, 第32字节 这道题目是给你一段多个汉字组成的信息，每个汉字用32个字节表示，这里给出了字节作为有符号整数的值。 题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形，从中看出题目的要求，并根据要求填写答案。 这段信息是（一共10个汉字）： 4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 016 64 16 64 34 68 ...

A组队 编号 号位1 2 3 4 51 97 90 0 0 02 92 85 96 0 03 0 0 0 0 934 0 0 0 80 865 89 83 97 0 06 82 86 0 0 07 0 0 0 87 908 0 97 96 0 09 0 0 89 0 010 95 99 0 0 011 0 0 96 97 012 0 0 0 93 9813 94 91 0 0 014 0 83 87 0 015 0 0 98 97 9816 0 0 0 93 8617 98 83 99 98 8118 93 87 92 96 9819 0 0 0 89 9220 0 99 96 95 81 暴力就完事，答案490： teams=[(97,90,0,0,0),(92,85,96,0,0),(0,0,0,0,93),(0,0,0,80,86),(89,83,97,0,0),(82,86,0,0,0),(0,0,0,87,90),(0,97,96,0,0),(0,0,89,0,0),(95,99,0,0,0),(0,0,96,97,0),(0,0,0, ...

概述最小生成树（Minimum Spanning Tree,MST）在一给定的无向图G = ( V , E ) 中，代表连接顶点u 与顶点v 的边，而 w(u, v)代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树，因为T是由图G产生的。 其中， w(T)=\sum_{(u,v)\in T}^{} w(u,v)最小生成树其实是最小权重生成树的简称。我们称求取该生成树的问题成为最小生成树问题。一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 那么，我们如何来求最小生成树呢，由最小生成树的定义我们可以知道构建最小生成树是可以利用贪心算法去实现的，我们接下来介绍的算法也都是利用贪心算法去求得MST的。因为贪心算法的策略就是在每一步尽可能多的选择中选择最优的，在当前看是最好的选择，这种策略虽然一般不能在全局中寻找到最优解，但是对于最小生成树问题来说，它的确可以找到一颗权 ...

问题描述有N种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i种物品的费用是wi，价值是vi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。 算法思想朴素思想完全背包与01背包不同的是同一种物品可多次选取。有了01背包的基础，再来理解完全背包就很容易了。 先回顾一下01背包的状态转移方程： j<w(i) V(i,j)=V(i-1,j) j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝ 完全背包的子问题定义和01背包相同，V(i,j)表示当前背包容量 j，前 i 个物品最佳组合对应的价值。面对当前商品也同样有两种可能性： 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)； 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，装多少也同样是个未知数。所以我们需要另设一个变量k表示装的物品的个数（0<=k*wi<=j）。我们需要在装k个物品之间选择最优的一个，即V(i,j)=max｛V( ...

背景已知e，n，c（其中n太大，分解不了），和p的高位或m的高位或d的高位 基础知识（1）生成一个以x为符号的一元多项式环 PR.<x> = PolynomialRing(Zmod(n)) （2）定义求解的函数 f = x + p4 （3）多项式小值根求解及因子分解，其中X表示求解根的上界 roots = f.small_roots(X=2^kbits, beta=0.4) coppersmith的定理： 对任意的a > 0 ， 给定N = PQR及PQ的高位(1/5)(logN,2)比特，我们可以在多项式时间logN内得到N的分解式。这是三个因式的分解。也就是说我们现在是由理论依据的，已知高位是可以在一定时间内分解N。 Coppersmith证明了在已知p和q部分比特的情况下，若q和p的未知部分的上界X和Y满足XY <= N 0.5则Ｎ的多项式可以被分解。这里的0.5可以替换成其他的数，具体原因不详。 已知p高位知道p的高位为p的位数的约1/2时即可已知e,n爆破 1024的P，至少需要知道前576位二进制，即 ...

引入总体思路此类问题一般是寻找最优解，但由于最终的最优解取决于前面一系列的决策，局部最优不一定能导出整体最优，所以贪心的思想对此种问题束手无策。所以需要从最简单的小问题开始，逐步扩展，最终扩展到我们需要的地方为止。这里的扩展就是决策，就是状态转移。根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出问题的最优解以及解组成，然后编写代码实现。 动态规划的原理动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的 ...

A门牌制作【问题描述】小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个字符 0，2 个字符 1，1 个字符 7。 请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？ 答案：624 res = 0for i in range(1, 2021): for j in str(i): if j == '2': res += 1print(res)# 624 B寻找2020【问题描述】小蓝有一个数字矩阵，里面只包含数字 0 和 2。小蓝很喜欢 2020，他想找到这个数字矩阵中有多少个 2020 。 小蓝只关注三种构成 2020 的方式： 同一行里面连续四个字符从左到右构成 2020。 同一列里面连续四个字符从上到下构成 2020。 在一条从左上到右下的斜线上连续四个字符，从左上到右下构成 2020。 例如，对于 ...

A卡片 cards = [2021]*10i = 1while True: s = str(i) for j in s: cards[int(j)] -= 1 flag = False for j in cards: if j < 0: flag = True break if flag: break i += 1print(i-1)# 3181 B直线 cnt = 0dots = [(i, j) for i in range(20) for j in range(21)] # 生成所有点lines = set()for i in range(len(dots)): for j in range(i+1, len(dots)): if dots[j][0]-dots[i][0] != 0: x1, x2 = dots[i][0], dots[j][0] y1, y2 = dots[i][1], ...