挑战赛#8题解 T1： 题目要求求出数轴上被同时涂成红色和蓝色的部分的长度。 其中[L1,R1]为蓝色 [L2,R2]为红色 纯模拟或者直接算即可 模拟代码 不用思考非常适合我： 时间复杂度O(n)O(n)O(n) 但是可以简化为什么要写模拟 计算代码： 时间复杂度O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 题目要求判断给定的比赛结果是否存在矛盾。 因为数据很小 n≥1000n\ge1000n≥1000 所以直接枚举每一个结果即可 有句话说得好：暴力出奇迹 代码如下： 时间复杂度O(n2)O(n^2)O(n2) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 题目要求统计字符串出现的次数。 注意第二次出现的时候要输出的是1 用STL模版中的 map 会很简单 不会STL模版可以参考Macw07大佬的帖子 代码如下: 时间复杂度O(nlog⁡2n)O(n\log_2n)O(nlog2 n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 后三题和前三题完全不是一个难度的，天才出题组 T4 先说算法：动态规划+前缀和 我们设dp[i]表示i次抛硬币时能获取的最大价值 用sumA与sumB存储钱和额外奖金的前缀和 注意奖金的前缀和，sumB[i]指计数器到i时获得的额外奖金总数 我们假设在j次抛硬币选择反面，于是我们就能得到dp[i]的转移方程如下 dp[i]=max(dp[i],dp[j]+sumA[i]-sumA[j+1]+sumB[i-j-1]); 代码如下: 时间复杂度大约Θ(n22)\Theta(\frac{n^2}{2})Θ(2n2 ) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 这道题可以通过前缀位运算和动态规划来做 定义一个dp[i][0/1(j)][k]表示第i位的数字一开始的值(j)经过k轮后的值。 则根据定义我们可以得到转移方程为dp[i][j][k]=dp[i][j][k-1]|x(&x,^x) 取a的第i位可以通过a>>i&1实现 例如二进制10110要取第三位的1 右移三(i)位得到00101发现第三位到了第一位上 我们在&1 即00101&00001 因为&运算是都为1时取1,其余取0 发现如果第一位是1是刚好取1,是0时刚好取0 其余位因为&的1都是0,所以得数也是0 答案就是a的第i位 初始化为 dp[i][j][0]=j 因为不经过变换时当前位的数字不变 最后将dp[][][k]数组经过位运算还原 AC代码： 时间复杂度Θ(60n)\Theta(60n)Θ(60n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 一道和逆序对很像的题 首先先讲述逆序对怎么做，题目 逆序对 对于一个数组 3 4 2 4 5 1 我们对它进行归并排序 当有序数组合并时，如果后半段大，则逆序对的数量加上前半段当前的长度 举个例子 比如：[2 3 4][1 4 5]时 后半段第一个 1 比前半段的第一个 2 大 因为归并排序的性质，数组的前半段和后半段都是有序的 则如果后半段第一个数比前半段第一个数小，则前半段所有的数都比他大 不难发现此时[2,1],[3,1][4,1]则前半段的所有数与后半段第一个都是逆序对 则此时让ans+=前半段的长度就是逆序对的答案 逆序对代码如下： 时间复杂度O(nlog⁡2n)O(n\log_2n)O(nlog2 n) 回到这题来看，不难看出也是要求求出逆序对的数量，但是不同的是对于相同颜色的两个球不需要增加ans，那么我们考虑用一个cnt[]数组记录颜色的数量，在增加ans的时候减去cnt[后半段的颜色]。 AC代码如下： 时间复杂度O(nlog⁡2n)O(n\log_2n)O(nlog2 n)

AC君，A4758.奥特曼身高问题，我按样例输入，而输出则是，雷欧 52 1974，与样例输出的，迪迦 53 1996，有误，但是还是对了，我想问一下，为什么会这样？

呼叫大佬 呼叫大佬 呼叫大佬

ACGO挑战赛#8 T1~T4题解 前言 是的这篇挑战赛题解只有T1到T4的，因为本蒟蒻只做了这4题... 该篇题解方便个人总结和整理思路，如果能帮到你那么我将肥肠荣幸！ 欢迎指正或者提供hack数据！违规紫衫QwQ AK大神 Orz T1 交集 数轴上两个部分，起点和终点分别为L1,R1,L2,R2L_1,R_1,L_2,R_2L1 ,R1 ,L2 ,R2 ，输出两部分重合的长度，注意如果两部分相邻不算长度 LikeLikeLike样例3 很容易写出模拟代码毕竟数据不大 T2 比赛结果 N名玩家参加比赛，比赛结果存储在N×NN\times NN×N的二维表当中 题目描述 > 如果玩家iii战胜了玩家jjj，则Ai,jA_{i,j}Ai,j 为W； > > 如果玩家iii输给了玩家jjj，则Ai,jA_{i,j}Ai,j 为L； > > 如果玩家iii和玩家jjj打成平局，则Ai,jA_{i,j}Ai,j 为D 要去判断该二维表是否存在矛盾 简单思考一下 如果Ai,jA_{i,j}Ai,j 为W，那么相应的Aj,iA_{j,i}Aj,i 应该为L，因为玩家iii赢了玩家jjj，玩家jjj输给了玩家iii； 同理如果Ai,jA_{i,j}Ai,j 为L，相应的Aj,iA_{j,i}Aj,i 应该为W； 如果Ai,jA_{i,j}Ai,j 为D，相应的Aj,iA_{j,i}Aj,i 应该为D 这样就很简单写出判断了 T3 新建文件夹（1） 简化题目，就是输出字符串的出现次数，建立map从string映射到int型的关系即可，也是hash思想的简单应用 数据不大，模拟解决 T4 投硬币 一开始见这题想用DFS解决，但是见了数据范围知道肯定不行，毕竟DFS的话时间已经到O(2n)O(2^n)O(2n)的复杂度，这简直惊为天人！！！ 但当时没思路，觉得计数器这个东西带有后效性不符合DP，所以还是先写了个记忆化DFS泪拿42pts。。。 在随后分析了一下，每次对计数器的更改只增加了当时的金额，不对后面的金额发生影响，因此没有后效性 同时又可以分阶段求解前iii次投掷可获得的最大金额，符合动态规划的特性 对于任一次硬币的操作只有正面朝上和反面朝上两种情况，要求在NNN次操作中可获得的最大金额，这不就是01背包吗！ 定义DPDPDP状态表，DP[i][count]DP[i][count]DP[i][count]为第iii次投掷且计数器为countcountcount时可获得的最大金额 可得状态转移方程DP[i][count]=max(DP[i−1][count−1]+Y[count]+X[i],DP[i−1][count])DP[i][count]=max(DP[i-1][count-1]+Y[count]+X[i],DP[i-1][count])DP[i][count]=max(DP[i−1][count−1]+Y[count]+X[i],DP[i−1][count]) 注：Y[count]Y[count]Y[count]为计数器为countcountcount时可获的奖金，X[i]X[i]X[i]为第iii次硬币正面朝上所获的金额 其中DP[i−1][count−1]+Y[count]+X[i]DP[i-1][count-1]+Y[count]+X[i]DP[i−1][count−1]+Y[count]+X[i]为正面时的情况，DP[i−1][count]DP[i-1][count]DP[i−1][count]为反面朝上的情况 但是特别注意：countcountcount为000时，等于i−1i-1i−1次投掷时所能获得的最大值(为了保证DPDPDP的定义) 这样就能优化到O(n3)O(n^3)O(n3)了 代码如下：

防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视防透视 能AC的奖励10地铁币，Q区

完全背包问题 目录 1——问题概览 2——从"01背包"到"完全背包" 3——完全背包的优化 4——总结 问题概览 难度：普及 题目： YBT 1268 完全背包模板 洛谷 P1616 疯狂的采药 ACGO A174 飞马踏燕Gold King2 本文以YBT 1268 完全背包模板来作完全背包的讲解，另外两题同样为完全背包模版的应用，难度低，适合练习 描述： 设有nnn种物品，每种物品有一个重量及一个价值。 但每种物品的数量是无限的，同时有一个背包，最大载重量为MMM 今从nnn种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于MMM，而价值的和为最大。 从"01背包"到"完全背包" 同为背包问题，完全背包与01背包极其的相似 但不同的是01背包对问题描述是每个物品只能拿一次，对于物品也就有拿和不拿两种状态 完全背包是每个物品能拿任意次 在对01背包的讲解当中我们知道 (01背包-洛谷 01背包-ACGO) 01背包的状态转移方程DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)当中 DP[i−1][v−i.weight]+i.valueDP[i-1][v-i.weight]+i.valueDP[i−1][v−i.weight]+i.value是对于第i个物品如果存放，那么它的价值为 操作前i−1i-1i−1个物品且重量为v−i.weightv-i.weightv−i.weight时的最大值 加当前物品价值 这是01背包的，在完全背包中物品可以重复放 所以完全背包中对于第i个物品如果存放，它的价值为 操作前iii个物品且重量为v−i.weightv-i.weightv−i.weight时的最大值 加当前物品价值 即DP[i][v]=max(DP[i−1][v],DP[i][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i][v−i.weight]+i.value)除此之外其它都与01背包一致！ 完全背包Code: 完全背包的优化 既然对01背包可以进行优化，那么同样的完全背包也可以进行优化 把它的空间复杂度压缩成一维O(M)O(M)O(M) 在01背包的讲解文章中，我们对它优化后是进行逆推，如果进行顺推是错误的，这个我们也进行过讲解 但其实，完全背包的优化后推法就是顺推，对于01背包进行逆推就是为了保证每一件物品只可以选一次，顺推的结果会保存到同一轮的，而这正好符合完全背包的要求 因此完全背包优化后的代码也肥肠容易写出来 总结 完全背包建立与01背包的基础之上，也由此可见01背包的重要性 两个问题的思维相似，建议配合食用

这个写法占66B 但运行后的exe占1.3MB

首先在做题之前，我们先了解宇宙的起源： 天文学认为，宇宙是所有的空间、时间、物质及其等所产生的一切事物的统称，是我们这个物质世界的整体，是物理学和天文学的最大研究对象。这一名词在现代学术界首先是以经典场、量子力学、相对论与引力场、量项维物基等一系列学术概念为基础的现代物理学定义。其次是以人类历史为背景的人文内涵，哲学上又叫世界。 宇宙大爆炸学说 大爆炸宇宙论是现代宇宙学中最有影响的一种学说。它的主要观点认为宇宙曾有一段从热到冷的演化史。在这个时期里，宇宙体系在不断地膨胀，使物质密度从密到稀地演化，如同一次规模巨大的爆炸。大爆炸理论认为:宇宙是由一个致密炽热的奇点于约138亿年前一次大爆炸后膨胀形成的。大爆炸理论的建立基于了物理定律的普适性和宇宙学原理这两个基本假设以及科研工作者的实际观测。 许多人不知道的是，与大爆炸理论已经成为常识相比，在该理论刚刚提出之后的很长一段时间，世界科学界对其的态度是"嗤之以鼻"的。这种奇怪的现象，是因为这个理论与《圣经》所言，宇宙是有一个起点的这一说法具有一致性，当时的科学界受进化论推翻"上帝创造论"的哲学思潮影响，盲目地反对传统理论，不承认与《圣经》相似的这种说法，这一时期的西方科学界普遍坚持宇宙和物质是恒定不变、无始无终的。因此对于所有涉及说宇宙万物都"有一个起点"的理论一概不予承认。包括像爱因斯坦这样的大科学家也受其影响。爱因斯坦在总结引力场方程时发现这个Rμv-(1/2)Rgμv=kTμv的公式将推导出宇宙其实是一个有着从未停止的物质变化的动态宇宙，于是在该公式中又*加了一个"宇宙常数"，以维持静态宇宙的计算结果。也就是说，最初的场方程其实是这样的:∧gμv+Rμv-(1/2)Rgμv=kTμv，其中常数"∧"为宇宙常数。自从1922年美国天文学家埃德温·哈勃开始观测到"红移现象"开始，有关"宇宙膨胀"的观点开始形成。1929年，埃德温·哈勃总结出了一个具有里程碑意义的发现，即:不管你往哪个方向看，远处的星系正急速地远离我们而去，而近处的星系正在向我们靠近。换言之，宇宙正在不断膨胀。这意味着，在早先星体相互之间更加靠近，似乎某一时刻，它们刚好在同一地方，所以哈勃的发现暗示存在一个叫做大爆炸的时刻，当时宇宙处于一个密度无限的奇点。听闻此事的爱因斯坦很快来到哈勃工作的威尔逊天文台，在哈勃的带领下亲自进行了红移现象的观测。访问结束后，爱因斯坦公开承认了自己主观意识影响科学结论的错误，并去掉了场方程中的宇宙常数，于是就有了我们所熟知的爱因斯坦场方程(Einstein Field Equation)。就此，哈勃的这一重大发现直接奠定了以大爆炸为中的现代宇宙学根基。 在二十世纪四十年代末，大爆炸宇宙论的鼻祖伽莫夫认为，我们的宇宙正沐浴在早期高温宇宙的残余辐射中，其温度约为6K。正如一个火炉虽然不再有火了，还可以冒一点热气。1964年，美国贝尔电话公司年轻的工程师-彭齐亚斯和威尔逊在工作中发现的宇宙微波背景辐射使许多从事大爆炸宇宙论研究的科学家们获得了极大的鼓舞。因为彭齐亚斯和威尔逊等人的观测竟与伽莫夫的理论预言的温度如此接近，正是对宇宙大爆炸论的一个非常有力的支持!这是继1929年哈勃发现星系谱线红移后的又一个重大的天文发现。宇宙微波背景辐射的发现，为观测宇宙开辟了一个新领域，这一发现，使我们能够获得很多大爆炸早期的直接信息。 2014年3月17日美国物理学家宣布，首次发现了宇宙原初引力波存在的直接证据。原初引力波是爱因斯坦于1916年发表的广义相对论中提出的，它是宇宙诞生之初产生的一种时空波动，随着宇宙的演化而被削弱。科学家说，原初引力波如同创世纪大爆炸的"余晖"，将可以帮助人们追溯到宇宙创生之初的一段极其短暂的急剧膨胀时期，即所谓"暴涨"。然而，广义相对论提出近百年来，源于它的其他重要预言如光线的弯曲、水星的近日点运动以及引力红移效应等都被一一证实，而引力波却始终未被直接探测到，问题就在于其信号极其微弱，技术上很难测量。美国哈佛-史密森天体物理学中心等机构物理学家利用架设在南极的BICEP2望远镜，观测宇宙大爆炸的"余烬"-微波背景辐时，计算到原初引力波作用到微波背景光子，会产生一种叫做B模式的特殊偏振模式，其他形式的扰动，都产生不了这种B模式偏振，因此B模式偏振成为原初引力波的"独特印记"。观测到B模式偏振即意味着引力波的存在。南极是地球上观测微波背景辐射的最佳地点之一。研究人员在这里发现了比"预想中*烈得多"的B模式偏振信号，随后经过3年多分析，排除了其他可能的来源，确认它就是原初引力波导致的。2016年年初，美国激光干涉引力波天文台(LIGO)和欧洲引力波天文台(VIRGO)的科学家联合宣布，他们探测到了两个约为30倍太阳质量的黑洞在13亿年前的并合产生的引力波，这一发现给大爆炸理论予以了新的有力证据。 2019年4月事件视界望远镜组织(Event Horizon Telescope Collaboration)在美国、比利时、智利、中国、日本同步发布首张基于观测事实的黑洞照片，这一照片给大爆炸理论又进一步增加了一个有利依据。 遗憾的是对于大爆炸的起点以及起点之前和大爆炸之后的最初阶段，相关的观测严重缺乏，最早期的宇宙物质以及能量的实际形式很大程度上仍只是猜测。 接下来我们来了解地球的起源： 现代地球起源假说是由我国学者江发世提出来的。认为地球是在太阳系外形成的，在距今5.4亿年前被太阳捕获，产生自转和公转，成为绕太阳旋转的行星。地质时期进入显生宙，地球有了阳光，冰川融化，生物爆发式出现，形成大量的灰岩沉积建造。 在距今46亿年前，在太阳系外的宇宙空间，由铁镍物质组成的地核俘获宇宙高温熔融物质和少量塑性物质、固态物质、气体和液体，在地核外形成高温熔融物质巨厚层。 地核与高温熔融物质间形成内过渡层。 地球外表温度降低，熔融物质凝固，形成地球最原始的外壳。 外壳与高温熔融物质间形成外过渡层。高温熔融物质形成液态层。 在这一地质时期，地球形成分层结构，由内向外：地核、内过渡层、液态层、外过渡层、外壳。固体地球结构见下表和图。 在地球表面，由于熔融物质凝固和收缩，形成张裂、沟谷、高山。由于宇宙天体撞击，在地表形成大坑洼地。 然后了解人类的起源： 人们通过对古人类、古猿类化石(包括遗体、遗迹和遗物)以及对现在世界各地的人与猿猴类的各个方面所进行的比较研究，人类起源于古猿的学说已被人们普遍接受。该学说认为，在距今七八百万年以前，人类和类人猿的共同祖先一古猿， 在新生代的第三代和第四代，由于造山运动，向着不同方向进化。生活在林中空地上的古猿、逐渐由树栖生活转到地面上生活，最终进化成人类;而留在森林中的那部分古猿则进化成了类人猿。 接下来了解电脑的起源和发展过程： 计算器是最早的计算工具，例如：古代印加人的一种结绳记事的方法，用来计数或者记录历史；还有古希腊人的安提凯希拉装置；中国的算盘等。 1642年，年仅19岁的法国伟大科学家帕斯卡发明了第一部机械式计算器，但是只能做加减计算。 1694年，莱布尼兹在德国将其改进成可以进行乘除的计算。此后，一直到20世纪50年代末才有电子计算器的出现。 20世纪70年代开始，微处理器技术被吸纳进计算器制程，最初的微处理器是Intel于1971年为日本名为Busicom的计算器公司生产的，1972年惠普推出第一款掌上科学计算器HP-35计算器是最早的计算工具，例如：古代印加人的一种结绳记事的方法，用来计数或者记录历史；还有古希腊人的安提凯希拉装置；中国的算盘等。 1642年，年仅19岁的法国伟大科学家帕斯卡发明了第一部机械式计算器，但是只能做加减计算。 1694年，莱布尼兹在德国将其改进成可以进行乘除的计算。此后，一直到20世纪50年代末才有电子计算器的出现。 20世纪70年代开始，微处理器技术被吸纳进计算器制程，最初的微处理器是Intel于1971年为日本名为Busicom的计算器公司生产的，1972年惠普推出第一款掌上科学计算器HP-35计算器是最早的计算工具，例如：古代印加人的一种结绳记事的方法，用来计数或者记录历史；还有古希腊人的安提凯希拉装置；中国的算盘等。 1642年，年仅19岁的法国伟大科学家帕斯卡发明了第一部机械式计算器，但是只能做加减计算。 1694年，莱布尼兹在德国将其改进成可以进行乘除的计算。此后，一直到20世纪50年代末才有电子计算器的出现。 20世纪70年代开始，微处理器技术被吸纳进计算器制程，最初的微处理器是Intel于1971年为日本名为Busicom的计算器公司生产的，1972年惠普推出第一款掌上科学计算器HP-35 然后了解C+ +起源： 与C语言一样，C+ +也是在贝尔实验室诞生的，Bjarne Stroustrup于20世纪80年代在这里开发出了这种语言。Stroustrup比较关系的是让C+ +更有用，而不是实施特定的编程原理和风格。名称C+ +来自C语言的递增运算符+ +，名称C+ +表示它是C的扩充版本。 C+ + 作者 C＋＋是80年代由贝尔实验室的Bjarne Stroustrup博士及其同事在C语言的基础上开发成功的面向对象（oop）的语言。 C+ +发展： C+ +是一门以C为基础发展而来的一门面向对象的高级程序设计语言，从1983年在贝尔实验室创立开始至今，已有30多个年头。C+ +从最初的C with class，经历了从C+ +98、C+ + 03、C ++ 11、C+ + 14再到C+ +17多次标准化改造，功能得到了极大的丰富，已经演变为一门集面向过程、面向对象、函数式、泛型和元编程等多种编程范式的复杂编程语言。由于C+ +过于复杂，并且经历了长时间的发展演变，目前对于C+ +标准支持的较好主要有GNU C+ +和Visual C+ +，严格来说，目前还没有一个完全支持ISO C+ +的版本。 接下来了解C+ +: C+ +是一种面向对象的计算机程序设计语言，作为C语言的继承，C+ +不仅能进行C语言的过程化程序设计，而且可进行以抽象数据类型为特点的基于对象的程序设计，还能进行基于过程的程序设计。C+ +是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它的设计风格支持数据抽象、面向对象程序设计、过程化程序设计、泛型程序设计等。 工作原理： C+ +语言的程序因为要体现高性能，所以都是编译型的。但其开发环境，为了方便测试，将调试环境做成解释型的。即开发过程中，以解释型的逐条语句执行方式来进行调试，以编译型的脱离开发环境而启动运行的方式来生成程序最终的执行代码。 生成程序是指将源码(C++语句)转换成一个可以运行的应用程序的过程。如果程序的编写是正确的，那么通常只需按一个功能键，即可搞定这个过程。该过程实际上分成两个步骤。 第一步是对程序进行编译，这需要用到编译器。编译器将C+ +语句转换成机器码;如果这个步骤成功，下一步就是对程序进行链接，这需要用到链接器。链接器将编译获得机器码与C++库中的代码进行合并。C+ +库包含了执行某些常见任务的函数(“函数”是子程序的另一种称呼)。例如，一个C+ +库中包含标准的*方根函数sqrt，所以不必亲自计算*方根。C+ +库中还包含一些子程序，它们把数据发送到显示器，并知道如何读写硬盘上的数据文件。 接下来我们看这道题（你还在看吗）： 根据题意，我们知道要把两个数加起来，所以我们先写出C+ +的头文件： #include<bits/stdc++.h>//调用数据包 using namespace std;//使用 int main(){//定义main函数，众所周知main函数是C+ +代码中必要的一部分 } 然后我们知道，C+ +定义变量的函数有： int,short,long,long long,double,float,long double,long float,char,string 所以我们根据题意知道是整数，范围是小于等于1000000000，int最符合，所以选择int。 写出定义代码： int a,b; 然后输入a和b，我们知道C+ +输入函数有： cin>>,scanf，gets,fgets 这里我们使用cin最恰当。 写出输入代码： cin>>a>>b; 然后就是输出了，我们知道C+ +中输出的函数有cout<<,printf 这里用cout<<更恰当。 写出输出代码： cout<<a+b; 最后写出整合代码： #include<bits/stdc++.h> //调用数据包 using namespace std;//使用 int main(){//定义main函数，众所周知main函数是C+ +代码中必要的一部分 int a,b;//使用这里最恰当的int定义函数定义变量a,b; cin>>a>>b;.//使用最恰当的cin输入函数输入变量a,b； cout<<a+b;//使用最恰当的cout输出函数输出a+b； return 0;//结束代码 }

真有实力就来参加dzoi！点击加入

居然发现了老版！

https://www.acgo.cn/application/1821812545799495680

None

小黑子蒸鹅心~还我家哥哥~

WA队

01背包问题 目录 1——问题概览 2——DP实现(状态转移方程推论) 3——对于01背包问题的优化 二维到一维 问题概览 难度：普及 题目：YBT1267 01背包问题(模版) 描述： 一个旅行者有一个最多能装MMM公斤的背包，现在有nnn件物品 它们的重量分别是W1，W2，...,WnW_1，W_2，...,W_nW1 ，W2 ，...,Wn ,它们的价值分别为C1,C2,...,CnC_1,C_2,...,C_nC1 ,C2 ,...,Cn 求旅行者能获得最大总价值。 DP实现(状态转移方程推论) 首先为什么要叫这为01背包问题？？？ 由题可得，对于任一物品只有拿取或者不拿这两种选择(对于一次选择，执行或不执行) 因此也就由"01"代表这个意思了，这是背包问题的root也是最简单的背包问题 如果用普通的搜索来解决，时间复杂度是O(2n)O(2^n)O(2n)，这简直惊为天人！！！ 思考下，我们可以把问题分阶段为取第iii件物品且容量为vvv时可获得的最大价值，从第111件商品与背包容量为111时开始往后递推，找到每一阶段的最大值，最终肯定能找到全局最优解，满足动态规划的最优子结构特点 因为前面i−1i-1i−1物品已经为最优了，所以只需要看放第iii个物品和不放第i个物品所获的价值哪个大 但放下也有前提条件，就是第iii个物品重量要小于当前背包容量vvv，不然你就算把背包掏空也塞不下...... 简易分析得以下结论 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ A.放不了：直接不放这个物品，最优解——放这个物品前的最优解 B.放得下： a.先清空背包，只放这个物品，再看看剩余容量能否装下之前的物品，最优解——这个物品的价值+背包剩余容量的最优解 b.不放这个物品，最优解——放这个物品前的最优解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 然后，a、b 情况进行比较，选出真正的最优解 设DP[i][v]DP[i][v]DP[i][v]为当操作物品为iii个,背包容量为vvv时所获最大价值 状态转移方程就是DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value) 注：i.weighti.weighti.weight指第iii件物品的重量 valuevaluevalue指第iii件物品的价值 代码实现如下 对于01背包问题的优化 二维到一维 其实对于01背包的时间已经到O(M∗N)O(M*N)O(M∗N)了，没法再优化了 但对于空间却可以进一步压缩 我们重新定义DP[v]DP[v]DP[v]为背包容量为vvv下所获的最大价值 根据我们上文的分析DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value) 其中DP[i−1][v]DP[i-1][v]DP[i−1][v]和DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]都是上一次操作时，容量为vvv和v−i.weightv-i.weightv−i.weight下所得最大价值 可知每一次的DP[i][v]DP[i][v]DP[i][v]都依赖上一轮的最大值 但是我们可以使用逆推来省去[i−1][i-1][i−1]的步骤，因为在一轮iii之后的i+1i+1i+1轮中DP[v]DP[v]DP[v]存储的都是上一次所能获得的最大值 这就使得DP[v−i.weight]DP[v-i.weight]DP[v−i.weight]代替了DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]的功能，并且压缩了空间 状态转移方程为：DP[v]=max(DP[v],DP[v−i.weight]+i.value)DP[v]=max(DP[v],DP[v-i.weight]+i.value)DP[v]=max(DP[v],DP[v−i.weight]+i.value) 注：DP[v]DP[v]DP[v]为不放时所获的值 DP[v−i.weight]+i.valueDP[v-i.weight]+i.valueDP[v−i.weight]+i.value为放时所获的值 If you have QuestionIf\ you\ have\ QuestionIf you have Question为什么使用逆推不用顺推？？？ 初学的本蒟蒻在一开始整理个人笔记时也有该问题... 但是如果你通过YBT原题给出样例去填表发现 很明显顺推情况下DP表是错误的 因为在顺推情况下DP[v]DP[v]DP[v]会存到同一轮前面的值也就是相当于存了DP[i][v−i.weight]DP[i][v-i.weight]DP[i][v−i.weight]但我们要的是DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight] 这样在优化后01背包的空间复杂度为O(M)O(M)O(M)了 优化代码：