最近有些人私聊我说标准库的sqrt函数精度不够，想让我出一期教程，让精度提升至long double、__float128，…… 首先，牛顿送代法都听说过吧，他的公式只需要算一阶导数，这里公式推导过程就不细讲了，直接上公式：x_new=(x^2 +n)/2x（标准公式推导出来是：x_new=x-(x^2 -n)/2x，前面的是简化过后的），如果对效率没有太大需求的话（如只是算个几十位，用来炫技等）可以直接用了。 代码示范： 如果你追求极致速度的话，我这里也是有一个四阶收敛的超级公式，具体公式如下： 代码示范： 最后顺便提一嘴：__float128等扩展类型不能用普通cout/cin、printf/scanf 输出/输入，你得自己定义输出输入方式 如有更快的收敛公式，也欢迎大家留言讨论！ 课后作业：用我讲到的任意方法心算/笔算出 根号10的 前10位小数。 下课！

只输出数字

提示：这题变量要用char类型

感谢@Xylophone给这篇帖子提出的建议！ 帖主是小白。欢迎提出建议！ —————————————————————————————————————————— 本质上似乎都是贪心。毕竟叫最小生成树了。 1.Prim 用一个dis数组来记录到目前为止当前树中的点到其他点的最短边长。 先将一个随机的点（这里选择一号点）放入生成树，遍历它的边。 用它的边来更新dis。标记它。 这里用一个结论：任何时刻未标记的点中dis最小者，其dis值所对应的边一定在一颗最小生成树中。 把所有未标记点中dis最小的那个点标记，遍历它的边。 重复上述操作。 时间复杂度O(n2+m)O(n^2+m)O(n2+m)。 注意到这个过程其实很像dijkstra。所以不难想到它可以用优先队列优化。 时间复杂度O(mlogn)O(mlogn)O(mlogn). 不过。堆优化prim似乎是有很大的常数的。 理论上我们认为在稠密图的情况下堆优化prim会比kruskal快。但是实际上可能并不。 题目：最小生成树-模板 代码：(堆优化版本） 另：其实我并不清楚这个版本的优势在哪里。可能唯一的优点就是对我来说比较好些。因为和dijkstra很像嘛。 注意：更新dis[i]需要确保vis[i]没有被标记。 代码：（普通版本） 堆优化版本和普通版本的代码没什么过大的差异。 建议写普通版本。 2.kruskal 其实逻辑本身和prim是一样的。只是实现方式不同罢了。 kruskal：将所有边排序，根据边权从小到大遍历每条边。如果当前边连接的两个节点来自不同的连通块，那么就将这条边加入最小生成树。 插播小广告：并查集 想要写出kruskal，我们需要先学会并查集。 由于我早就修为散尽，所以我的并查集可能写的很烂，如果弄不懂的话可以直接看oi-wiki 并查集需要支持两个操作：1.合并（将两个元素所属集合合并） 2.查询（查询两个元素所属集合是否为同一个） 开始时，每个元素属于一个单独的集合。每个节点的父亲节点设为自己（使用一个f数组来存储当前节点的父亲节点）。 如何查询：当前节点为i，使得i=f[i]，直到i==f[i]。 考虑到集合内顺序并不重要，我们可以直接使得当前节点（i)的f[i]设置为根节点。（路径压缩） 合并：合并两棵树，只需要将一颗树的根节点改成另一棵树的根节点。 然后就可以开始挫代码了。 并查集的每次操时间是一个极小的常数。 所以，kruskal的时间复杂度瓶颈在排序上。时间复杂度为O(mlogm)O(mlogm)O(mlogm)。 prim从点开始，kruskal从边开始。不过它们本质相同。 应@Xylophone的建议，多加了一种方法：Boruvka 先把代码放一下，明天来写做法： 我来了。接下来我的说明会参考洛谷的这篇题解。有兴趣的话可以直接去看原版而不是山寨版。不过山寨版会加入一些自己的见解。 我个人认为，boruvka其实算是prim和kruskal的结合体。 prim是从一个点开始，不断贪心地往外找最短边，最后构成一个大连通块。 而boruvka的每次增广，都会在每个连通块上找最短边。 而最短边有两个评判依据： 1.边权最短 2.（如果有边权相同）那么根据编号排序（也就是每条边的下标） 而连通块的形成又依靠并查集。这个部分又神似kruskal。 需要注意的点： 1.两个排序要求 2.每添加一条边，那就要将这条边进行标记。否则有可能出现加一条边两次的情况： 比如在遍历一号点的时候，我将这条边加入了一次最小生成树。 那么在遍历二号点的时候，（恰巧此时二号点的最短边也是这条边）如果我不标记，就会再次添加。 它的时间复杂度还挺特殊的。 每一次合并，需要遍历m条边。时间复杂度O(m)O(m)O(m)。 不过每一次合并后，连通块的个数都会减小一半。也就是说需要lognlognlogn次，它们就可以合并成一颗最小生成树了。 所以时间复杂度是O(mlogn)O(mlogn)O(mlogn)。（哦不过这个不像是堆优化prim那样参水）。 lognlognlogn次的合并使boruvka十分特殊。 所以如果有题目想要考察这个算法，就一定会和这个性质密切相关。 明天会弄一些例题。 例题：买礼物 先说做法，再说想法。 做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。 由于在熟悉，所以prim和kruskal都会拿出来弄一遍。 prim: 在写prim的时候，我发现了一点比较有意思的事情。 我将vis[k]=1改动成了： 如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。 当时居然没注意，随意改了一下酿成大错qwq。 接下来是kruskal的版本。 分析： 1.如何分析这道题目需要用到最小生成树 分析这个问题，先需要想到，这是一道和图论相关的问题。 如何将一个实际问题转化成为图。或者说如何识别有“图”。 它有点之间的关系。点i和点j之间的联系就是k[i][j]。 那么这个联系就可以变成边。 想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。 然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。 最后分析复杂度：一共有n∗nn*nn∗n条边。大约2e5。可以支撑的起O(mlogn)O(mlogn)O(mlogn)的时间复杂度。 2.使用prim更好还是使用kruskal更好。 稠密图。推荐使用prim（非堆优化）。 好的，来看下一道例题：构造树 题目大意：一颗有n个结点的树，其中每条边有一个正整数边权。但并不知道这颗树的样子，只知道每两点之间最短路长度，但是这些最短路长度可能是错误的。请判断是否存在一颗树满足条件。 样例 输入： 3 0 2 7 2 0 9 7 9 0 输出： YES 先说做法，再分析。 我们先将图根据题目所给出的信息建出来。 如果这n个点能构成一颗符合条件的树（指符合题目要求的树），那么一定是该图的生成树。 回顾kruskal算法的过程。一条点u到v，边权为w的边属于最小生成树，那么就代表其他所有边权小于w的边没能使得点u和点v连通。（这边的最小生成树指的是我们用图中的边建立的最小生成树） 这也就意味着在最后的生成树中（也就是我们在图中建立的生成树）这两点的路径一定会经过至少一条边权大于等于w的树。 这样下来，这两点之间的距离一定会大于等于w。只有在点u和点v直接相连的时候才能取到相等。 而点u和点v之间只会有一条边。边权是两点之间的最短距离。 因此只有在这颗树是最小生成树的时候，它才可能是满足条件的树。 这是大致的思路： 构造树的代码已经写好了。就是不知道为什么cf一直不能交。只能看后面怎么办。 现在这里放一下我的代码： (不一定是对的）

萌新的第一个帖子，别说我写的差了 别人随随便便一个帖子直接几十个赞，我这就2赞啊，很搞人心态的，求点赞 本帖禁止刷罐 如果我们想要求两数的最大公因数，平时我们可能是直接暴力，依次枚举进行判断，如下代码： 对于一些比较大的数据暴力就 TLE 了，这时候我们就要用辗转相处法 数学思维：对于要求 a和b（ a≥b）的最大公因数辗转相除法步骤：k = b, b = a % b, a = k ……不断重复，直到b = 0时，k就是答案。 因此我们可以写出两种代码（迭代 和 递归）： 1.迭代法 2.递归法 c++11有__gcd(a, b)可以直接求解! 拓展：我们可以通过求最大公因数来求最小公倍数：A * B / 最大公因数(不懂看最下面) 可以写出代码： 在c++17有直接求解最大公因数的函数lcm(a, b) 附件：为什么最小公倍数 = 乘积 / 最大公因数？ 令a === 最大公因数 * (a / 最大公因数) b === 最大公因数 * (b / 最大公因数) 则其最小公倍数 = 最大公因数（公共的，只用乘一次） * (a /// 最大公因数) * (b /// 最大公因数) = a ∗*∗ b /// 最大公因数 辗转相除法证明过程： 设 a = q × b + r，其中 q 是 a 除以 b 的商，r 是余数（0 ≤ r < b）。 第一步：证明 gcd(a, b) 是 b 和 r 的公因数 令 d = gcd(a, b)，则 d 能整除 a，也能整除 b。 由 r = a - q × b，因为 d 能整除 a 和 b，所以 d 也能整除 r。 因此 d 是 b 和 r 的公因数，所以 d ≤ gcd(b, r)。 第二步：证明 gcd(b, r) 是 a 和 b 的公因数 令 e = gcd(b, r)，则 e 能整除 b，也能整除 r。 由 a = q × b + r，因为 e 能整除 b 和 r，所以 e 也能整除 a。 因此 e 是 a 和 b 的公因数，所以 e ≤ gcd(a, b)。 由第一步和第二步可得：d = e 即：gcd(a, b) = gcd(b, a mod b) 结论： 反复使用这个等式，每次把较大的数换成它除以较小数的余数，不断重复，直到余数为 0。此时，那个非零的除数就是原来两个数的最大公因数。这就是辗转相除法（欧几里得算法）的原理。 求赞！！！

康拓表？

前言：有个文章 声明！本文和ID：4259470联动出品，搭配米饭食用更佳！ 众所不周知，常见的搜索方法有广度优先搜索、深度优先搜索（俗称：深搜广搜）、二分搜索、线性搜索。 正片开始前，请准备好米饭，然后再看目录： 1. 常见搜索方法的概念： （ （1）、搜索的概念 （2）、线性搜索概念 （3）、二分搜索概念 （4）、深度搜索概念 （5）、广度搜索概念 ） 2. 深度搜索模板 3. 广度搜索模板 4. 二分搜索模板 5. 线性搜索模板 正片已开始 1. 常见搜索方法的概念 （1）、搜索的概念 * 在 C++ 编程中，搜索指的是从数据集合（如数组、链表、树、图等）中查找满足特定条件的元素或路径的过程。搜索是程序设计中最基础且常用的操作之一，其效率直接影响程序性能，因此选择合适的搜索算法至关重要! * 找到目标元素在数据集合中的位置。 * 判断目标元素是否存在于数据集合中。 * 在复杂结构（如树、图）中寻找满足条件的路径或解（如最短路径、可行解）。 （2）、线性搜索概念 * 线性搜索，是一种最简单直观的搜索算法，其核心思想是逐个检查数据集合中的元素，直到找到目标元素或遍历完所有元素。 基本原理： 线性搜索不要求数据集合具备特定的排列顺序，适用于任何类型的线性数据结构（如数组、链表等）。其过程如下： 1. 从数据集合的第一个元素开始 2. 依次将每个元素与目标值进行比较 3. 如果找到匹配的元素，返回其位置（索引） 4. 如果遍历完所有元素仍未找到匹配项，返回表示 "未找到" 的标识（通常为 - 1） （3）、二分搜索概念 * 二分搜索，是一种高效的查找算法，其核心思想是利用数据的有序性，通过反复将搜索范围减半来快速定位目标元素。 基本原理： 二分搜索仅适用于已排序的数据集合（升序或降序），其过程如下： 1. 确定搜索范围的起始和结束位置 2. 计算中间位置，并比较中间元素与目标值 3. 如果中间元素等于目标值，找到目标，返回其位置 4. 如果中间元素小于目标值，说明目标在右半部分，调整左边界 5. 如果中间元素大于目标值，说明目标在左半部分，调整右边界 6. 重复步骤 2-5，直到找到目标或搜索范围为空（未找到） （4）、深度搜索概念 * 深度搜索（DFS），又称深度优先搜索，是一种用于遍历或搜索树、图等数据结构的算法。其核心思想是尽可能深地探索一条路径，当无法继续前进时，回溯到上一个节点，选择另一条未探索的路径继续深入，直至遍历所有可达节点。 基本原理： 深度搜索的执行过程类似于 “走迷宫”：优先沿着一条路径走到尽头，遇到死胡同再退回上一个岔路口，选择新的路径继续探索。其过程如下： 1. 从起始节点开始，标记该节点为 “已访问”。 2. 选择一个未访问的相邻节点，递归或通过栈深入探索该节点。 3. 重复步骤 2，直到当前路径无法继续（所有相邻节点均已访问）。 4. 回溯到上一个节点，继续探索其他未访问的相邻节点。 5. 直至所有可达节点均被访问。 （5）、广度搜索概念 * 广度搜索（BFS），又称广度优先搜索，是一种用于遍历或搜索树、图等数据结构的经典算法。其核心思想是从起始节点出发，优先访问距离起始节点最近的所有节点，然后逐层访问更远的节点，类似于水波从中心向四周扩散的过程。 基本原理： 广度搜索的执行过程如同 “逐层扩散”：先访问起始节点的所有直接邻居（距离为 1 的节点），再依次访问这些邻居的所有未访问邻居（距离为 2 的节点），以此类推，直到遍历所有可达节点。其过程如下： 1. 从起始节点开始，将其加入队列并标记为 “已访问”。 2. 当队列不为空时，取出队首节点并访问它。 3. 将该节点所有未访问的相邻节点加入队列，并标记为 “已访问”。 4. 重复步骤 2-3，直到队列为空（所有可达节点均被访问）。 2. 深度搜索模板 时间复杂度： * 对于包含 n 个节点和 e 条边的图： 邻接表存储时，时间复杂度为 O(n+e)O(n + e)O(n+e) 邻接矩阵存储时，时间复杂度为 O(n2)O(n^2)O(n2) * 对于树（特殊的图，边数为 n-1）：时间复杂度为 O(n)O(n)O(n) 优缺点： * 优点： 内存占用通常小于广度优先搜索，尤其对于深度较大但分支较少的结构。 适合解决路径查找、连通性检测、迷宫求解等问题。 * 缺点： 不保证找到最短路径（在无权图中）。 对于深度极大的结构（如深度为 10610⁶106 的树），递归实现可能导致栈溢出。 可能陷入 “深层无效路径”，在某些场景下效率较低。 3. 广度搜索概念 时间复杂度： * 对于包含 n 个节点和 e 条边的图： 邻接表存储时，时间复杂度为 O(n+e)O(n + e)O(n+e) 邻接矩阵存储时，时间复杂度为 O(n2)O(n²)O(n2) * 对于树（特殊的图，边数为 n-1）：复杂度为 O(n)O(n)O(n) 优缺点： * 优点： 在无权图中，能找到从起始节点到其他节点的最短路径（边数最少）。 适合解决 “层次化” 问题（如按层级遍历树）。 * 缺点： 空间复杂度较高，尤其对于分支较多的结构（队列可能存储大量节点）。 不适合用于检测环路（相比深度搜索更复杂）。 4. 二分搜索模板 时间复杂度 * 最佳情况：目标元素是中间元素，时间复杂度为 O(1)O(1)O(1) * 最坏情况和平均情况：时间复杂度均为 O(logn)O(log n)O(logn)（n为元素总数） * 每次搜索范围减半，经过 log⁡2n\log₂nlog2 n 次比较后即可完成 优缺点 * 优点：效率高，尤其对于大规模数据，性能远优于线性搜索 * 缺点：要求数据必须有序，且仅适用于可随机访问的结构（如数组），不适用于链表 求赞！！！！ 真的制作不易！ 彩蛋

明明这题比a1048简单

我的代码为何会错

#include<bits/stdc++.h> main(){printf("%s","Hello World");} //我哭死，你再给1/4m呢？

按常理来说，float定义n是可以判断的，不必要用double 但为什么这道题用float第8和第10测试点过不了？

666，啥题呀，这么难

你告诉我这叫入门： #include<bits/stdc++.h> using namespace std; bool isPalindrome(long long num) { if (num<0){ return false; } string s=to_string(num); long long left=0; long long right=s.length()-1; while (left<right) { if (s[left]!=s[right]) { return false; } left++; right--; } return true; } vector<long long>getFactors(long long n) { vector<long long>factors; for (long long i=1;i*i<=n;i++) { if (n%i==0) { factors.push_back(i); if (i!=n/i) { factors.push_back(n/i); } } } sort(factors.begin(),factors.end()); return factors; } bool isJHNNumber(long long n) { if (n%2==0) { return false; } if (!isPalindrome(n)){ return false; } vector<long long>factors=getFactors(n); long long count = 0; for (long long factor:factors) { if (factor >= 10 && isPalindrome(factor)) { count++; } if (count>=2) { return true; } } return false; } int main() { long long N; if (cin>>N) { if (isJHNNumber(N)){ cout<<"yes"; }else if(N<=11){ cout<<"no"; } else{ cout<<"no"; } } return 0; } 都解决不了，有大佬能说一下这错那了吗？

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注意这是一个暴力算法 1 背景与来源 * 起源题目：CF 896C Willem, Chtholly and Seniorious * 正式名称：Old Driver Tree * 本质：基于 set 的区间暴力合并 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2 适用条件（非常重要） 2.1 必须满足 存在大量区间赋值\text{存在大量区间赋值} 存在大量区间赋值 2.2 推荐环境 * 随机数据 * 对复杂度要求不严格 * 比赛 / 快速实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3 核心思想 3.1 区间表示 数组被划分为若干连续段： [l1,r1,v1],[l2,r2,v2],…[l_1,r_1,v_1],[l_2,r_2,v_2],\dots [l1 ,r1 ,v1 ],[l2 ,r2 ,v2 ],… 相同值合并为一个节点。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3.2 关键直觉 > 区间赋值会急剧减少段数 期望段数： E[k]=O(log⁡n)\mathbb{E}[k]=O(\log n) E[k]=O(logn) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4 数据结构定义 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5 核心操作 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5.1 SPLIT（拆分） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5.2 ASSIGN（区间赋值） ✅ ODT 的灵魂 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6 区间查询 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6.1 区间和 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6.2 区间加 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6.3 区间 K 小 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6.4 区间幂次和 ∑i=lraik mod m\sum_{i=l}^{r} a_i^k \bmod m i=l∑r aik modm ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 7 完整可用模板（CF 896C） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 8 复杂度分析 8.1 均摊复杂度 操作 均摊 assign O(log⁡n)O(\log n)O(logn) query O(log⁡n)O(\log n)O(logn) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 8.2 理论警告 Worst Case=O(n)\text{Worst Case}=O(n) Worst Case=O(n) 不可用于正经数据结构题证明 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9 与其他结构对比 结构 稳定性 实现难度 ODT 低 ⭐ 线段树 高 ⭐⭐⭐ 平衡树 高 ⭐⭐⭐⭐ 分块 中 ⭐⭐ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10 常见错误 * 忘记 mutable * 忘记 split(r+1) * 没有区间赋值 * 在严肃比赛中依赖 ODT ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 11 进阶方向 * ODT 随机性证明 * ODT + 哈希 * ODT 离线技巧 * ODT 与线段树混合 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; cout<<a+b; return 0; }

我缩在沙发角，像只被逼到绝境的猫。客厅里，酒瓶碎裂的声音和母亲扭曲的咒骂混成一片。“都是你这个扫把星害的！”她抄起半截啤酒瓶，眼底是骇人的红。我僵着没躲，以为这次还能像往常一样熬过去。谁知她猛地扑过来，指甲几乎抠进我胳膊肉里，力道大得像是要把我撕碎。下一秒，火辣辣的剧痛炸开——我妈一巴掌拍在我脸上，竟然直接爆出了manacher的肥美食用方式🤣🤣🤣 首先说一下我对manacher的理解，我们普通的做法是直接将每一个位置都从起点向外面扩算，这就导致了一个问题，很多位置已经被算过了，结果又被算了一遍，这样会损失很多时间，非常难受，那咋办呢？那当然是摆好姿势请出你的manacher爸爸让他爽爽抄一抄，举个栗子 字符串abba非常欲求不满， manacher插进去了 字符：# (OMG)**哦齁齁齁齁齁齁齁齁齁齁齁齁❤️❤️❤️❤️**(?) 于是，字符串的第一次变成了#a#b#b#a# 这样所有的回文就都变成奇数长度，不用再去分烦人的奇偶回文，随便贴个代码 然后就是最肥美的一步 再然后，你就可以挑战黑题了 （想抄题解的有福了，kp也不会写这道题，总感觉这题怪怪的）

抄袭hopeworse的题目!