🚀互动话题#7 ：期中心情 😎嗨，小伙伴们！期中考试结束啦，或者你正在期中阶段，有啥心情都来聊聊吧！ 🎤心情分享 * 考后心情：考得好就像打了胜仗，考差了也别气馁。 * 当下体验：当下的心情，压力大或有新体验，都可以说说。 🎁 奖励 * 奖励设置：抽3人送社区盲盒 * 参与方式：在评论区写心情 快来分享，一起加油！😎

前言： 作者在上初中，本次考试只记语数英物四门。从考试到查分全程反转不断，也写的比较搞笑和抽象，大家多多点赞！ 正片开始↓ Day -1(2024/11/10) 好紧张，明天就要上机了。 最后一夜过了一遍模板，就早早睡觉了，毕竟不能像csp那样失眠了。 半夜有小孩尖叫。根据小孩尖叫的频率，我们可以容易的算出小孩的声音波长。 Day 1上午(2024/11/11) 没错，D1先考语文！！！ 拿到试卷看到题目，果然还是那三道题：基础知识，阅读理解，作文。预计难度蓝紫蓝。赶紧看到最后一题“作文”，题目名“这，是我的选择”。数据范围大于600字即可。啊？简单的题目，极小的数据，这是D1T3该有的难度？我非常的惊喜。 这时，开始考试，我看到了第一题：一开始我就傻眼了，这是道非传统题——他竟然让我写出关于“信”的成语！真的是太难了！用最短路分层图也只能拿到80%。还有类似改病句，将“提高诚信建设”提出修改建议。这也没有特殊性质啊？我推了一会，没有推出性质，只能先做后面的题。 名著题直接切。问我周恩来干过那些事情？我知道！周恩来建立清朝，反对独裁！（好像哪里不对）直接来到第二题。第二题直接分为了3部分，而且也是一道非传统题目。但不是通讯题之类，因为第一部分的题目描述直接变成了文言文! 真的是太奇怪了。好在我懂文言文，主要介绍了谢灵运个神金孤高傲世，不想做官还写诗词恶心我们的故事。非连也是非常简单，只要推出来旅游商家怎么坑钱就行。但是这道题这所以是蓝题主要不是算法的毒瘤，而是他让你写出像商家一样怎么更好的坑钱——出文创产品。真奇怪哉！最后来到现代文。还是一样，我先把预备快读模板打好，常数大大下降。结果这道题常数没有用——每个测试点的分值给的都很少，而且有些一眼大模拟就能过。我也是飞快的打了出来。D1T2就这样被我切出来了。作文已经想好了。就写我csp失利吧！我用tarjan把我的考试用dfn时间戳表现了出来，再加一点常数优化，这样一定会给我高分！原来最难的是基础知识。还剩5分钟，我最后死磕了一下，瞎写了一个，交了上去。 但是交上去过后我才想到那个特殊性质“请用序号表示”，我写成字母了啊啊啊啊啊啊 Day 1下午(2024/11/11) 不用慌，不是还有物理吗。 跟qzr对了一下语文选择题答案，不一样，但他硬说自己估分Ag稳了。 最后复习了一下就开考了。 先来看选择题。有些题目比较抽象啊，题干我就读不懂，更别说数据范围了。有一道题目，他让你求角反射器转45度后反射光线旋转多少度。这道题我只能想出一个O(n3)O(n^{3})O(n3)的暴力，花了我很多timing。 填空题没有什么好讲的。直接一路往下码！！！ 这时候离谱的来了。看到最后一小题，欸这是不是在哪里做过——这不就是考试前10分钟讲的那道“压轴题”吗？我非常震惊。有生之年我也能成为透题的一员。《座杆竞得澳塞》，实锤。 Day 2上午(2024/11/12) 数学！！！！！！！！！！！！！！！！！！！！！！！！我*，不说了直接图概括： 没有关系，要微笑面对！！！ 8：50下发pdf。

1.PE（Pattern Error）输出格式错误 2.RE（Runtime Error）运行错误 tips：数组太大也会RE哦！ 3.TLE（Time Limit Exceed）超出时间限制/超时 tips：TLE一般是循环嵌套得太多层了，或者循环没出口！ 4.OLE（Output Limit Exceed）输出超出限制/输出超限 这种情况没见过，有图私聊我！ 5.AC（Accepted）答案正确/通过 6.WA（Wrong Answer）答案错误 tips：我遇到WA一般重写!! -_- 以上就是ACGO中常见的错误，有问题直接评论就AC了！ 制作不易，点个爱心+关注吧 -_-"

第一次写题解，如有不好的地方，望多多包含多多指教 许愿成为优秀题解 T1 数组 先看范围 数据：都在1e5之内，所以可以用数组（甚至题目名称就叫数组） 时间复杂程度：O（n） 思路：用一个数组记录每次给出的数，如果没被记录则a++ 代码 T2 走路 一道简单的模拟 数据：指令数是1e5，字母4个 时间复杂度： O（n） 思路：模拟就行 代码： T3 休息日 哔哔：一道题占了1/3的分数，然后默认cout<<1骗分，结果一看，哇，ioi赛制，被自己整笑了 言归正传，先分析一下，数据量是1e9，所以要么是O（n），要么是数学方法某人以为是递推，推了半天，被推死到沙滩上了 但是我研究了半天，发现解出来太费时间了，故放弃，选择打表大法 先用暴力算法解（大概是O（n方））出10到20 然后我惊奇的发现 抛开重复的不谈， 取12，2 和15，3可得y=x/3-2 将18代入验证，成立，所以答案就出来了 代码： 没错就是这么简单 然后附上我的数学思路 设选的两天为a，b，可得 d1=2a-b-1 d2=b-a-1 d3=n-b-1 然后设min里的三项为X,Y,Z； 可得 X=abs(2a-b) Y=abs(n-2b+a) Z=abs(n-a-b) 在分别假设X，Y，Z最小，然后根据所得的n与a，b的关系求出最大值在进行比较，就可以证明了 如：当n>2b,n>3a时 X最小，Xmax=1/3n+2/1n 理论上可行，所以仅供参考，如有误求轻骂 T4 质数个数 数据 1e6，所以可以暴力 时间复杂程度：O（根号n*n）暴力是因为数据支持，用筛法会更快 思路：函数zs：先特判，然后根据质数的特性分别对每个数使用试除法 main 依次遍历直到n，记录质数个数 代码： T5 好串 数据：T在100以内，n在1e4以内，所以可以使用数组来记录 时间复杂度 O（T*n） 思路：多询问题目 单次询问：把两个字符串按位把字符存进Book数组，然后遍历查看是Book是否一样 代码 T6 期中考试 继续祝大家期中考试高分but我已经寄了 本人没有什么实力，如有错误望大佬多多指教 许愿成为优秀题解

前言: 本文耗时π天写成，本人初中数学基础水平《just so so》，不喜勿喷 本文适合对几何开发达到0.0001%的人食用 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 中考几何 几何在中考中占50~60分，但各个地区中考分值不同 * 北京2025新中考政策（史）满分100分 几何就（约）占60分！！！ * 上海中考 满分150分 几何就（约）占60分！！！ * 浙江中考 满分150分 几何（约）就占60分！！！ 几何在中考至关重要！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 角与线段/图形 这个东西非常基础（不学这个几何学不下去） 看这个三角形 表示三角形 表示这个三角形我们可以用△ABC△ABC△ABC来表示，表示一个三角形可以用△+△+△+三个顶点字母来表示 表示线段 如果想表示一条线段，我们可以用两个字母来表示，这两个字母中间的一条线段就是所表示的线段 比如这个三角形的三角形可以用AB,AC,BCAB,AC,BCAB,AC,BC来表示 表示角 我们先看角的符号：∠∠∠ 这个三角形的三个角分别表示为：∠ABC/∠B,∠ACB/∠C,∠BAC/∠A∠ABC/∠B,∠ACB/∠C,∠BAC/∠A∠ABC/∠B,∠ACB/∠C,∠BAC/∠A 以∠ABC∠ABC∠ABC来举例，我们把它拆分，可以拆分为：线段AB与线段BC线段AB与线段BC线段AB与线段BC 所以∠ABC∠ABC∠ABC表示的是线段AB与线段BC线段AB与线段BC线段AB与线段BC所形成的夹角 特殊的表示方法 单个字母表示法 如果这个角只有一个角的顶点，如这个三角形，我们就可以用∠∠∠+一个大写字母 这个三角形的各个角就可以用∠A,∠B,∠C∠A,∠B,∠C∠A,∠B,∠C来表示 数字表示方法 这种方法常用于数学题中，用于在图形上标注简称。例如，∠1、∠2、∠3∠1、∠2、∠3∠1、∠2、∠3等‌ 看这张图片在角上标志数字，来简约的表达各个角，比如： ∠1∠1∠1就和∠ABE∠ABE∠ABE相同 ∠2∠2∠2就和∠FDC∠FDC∠FDC相同 ∠3∠3∠3就和∠BMD∠BMD∠BMD相同 (PS:如果你不建议，你完全可以列到∠∞∠∞∠∞) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 三线八角 （平行符号用∥∥∥来表示） 我们现在已知AB∥CDAB∥CDAB∥CD... 内错角 定义：在几何中，当两条直线被第三条直线所截（如图），而两个角分别在截线的两侧（错），且夹在两条被截直线之内时（内），这样位置关系的两个角被称为内错角（用直线把两个角描出来，可见一个不太明显的ZZZ）

今天闲的没事花了一个多小时搓了一个短链生成器,链接是这个: https://xiaosu.icu/short 也顺便教一下大家如何搓一个短链生成器~ 短链生成器原理很简单，最重要的是你得有一个比较短的域名 （不然就不叫短链了） 本质原理就是建立一个映射表，记录短链和目标url的地址，比如现在我们想要创建一个短链，短链的路径为https://xiaosu.icu/s/a 我们以flask为例，这样写来捕获和处理 但是很明显，人工一个一个写，一个一个匹配也太麻烦了，这时候 聪明的小朋友 就发现了，这个结构和python的字典很相似，于是我们可以创建一个字典 匹配的代码就可以写成 基本的原理就是这么简单，之后再加上持久化存储、api接口、前端网页之类的就是一个比较完整的短链生成器了。

T1.简单 T2.小小模拟 T3.二分……额不管了反正想不起来（ T4.埃氏筛... T5.P党大喜 T6.升华(感人) 开做 T1: 预计得分： 200pts200pts200pts 实际得分： 200pts200pts200pts 用时5min 集合的特性(去重)来计算列表中不同元素的数量(这个都知道): T2: 预计得分： 200pts200pts200pts 实际得分： 200pts200pts200pts 用时15min 小模拟(注意输出格式要不然会全WA)： T3: 预计得分： 500pts500pts500pts 实际得分： 450pts450pts450pts(极限) 😭😭😭已老实😭😭😭 二分我恨你 T4: 预计得分： 200pts200pts200pts 实际得分： 200pts200pts200pts 不难发现，如果n<=2n<=2n<=2，直接返回0就行，因为小于等于2的质数个数为0 先弄一个长度为n+1n+1n+1的布尔数组sss，初始值全为True，表示所有数都假设为质数 然后将s[0]s[0]s[0]和s[1]s[1]s[1]设为False，因为0和1不是质数 然后埃氏筛 从2开始遍历到sqrt(n)sqrt(n)sqrt(n)就行，要不然会TLE 如果s[i]s[i]s[i]为True，则iii是质数，就将iii的倍数(从i2i^2i2开始)标记为False 代码如下: T5: 预计得分： 300pts300pts300pts 实际得分： 300pts300pts300pts (P党最可以装的一集)不难想到，可以用collections.Counter库来统计字符串中每个字符的出现次数，然后比较两个Counter对象是否相等 如果两个字符串的字符计数相同，返回True；否则返回False (对于每个测试用例，读取两个字符串str1和str2，并判断它们是否字符数量平衡) 最后遍历list并输出 tips:这里故意降低code可读性所以头加了as C(懒的打Counter了)(bushi T6: 期中成绩都出来了吗(?想必各位都考了高分罢(没考好的别灰心!

以下是一些常见的 C++ 错误汇总： 语法错误 * 缺少分号：在语句末尾忘记添加分号是常见的错误。例如：int a = 5 // 缺少分号 * 括号不匹配：函数调用、表达式或控制结构中的括号没有正确匹配。比如：if (a > 5 { // 括号不匹配 * 变量未声明：使用了未声明的变量。cout << b; // b未声明 * 拼写错误：关键字、变量名、函数名等拼写错误。如：int mian() { // main拼写错误 语义错误 * 逻辑错误：代码的逻辑流程存在问题，导致结果不符合预期。例如在循环条件或条件判断中出现错误的逻辑表达式。 * 变量初始化错误：变量初始值设置不正确，影响后续的计算结果。 * 数据类型不匹配：在进行运算或赋值时，数据类型不一致。 运行时错误 * 数组越界：访问数组元素时超出了数组的有效范围。 * 除数为零：在进行除法运算时，除数为零。 * 内存泄漏：动态分配内存后没有及时释放，导致内存占用不断增加。 * 空指针引用：对空指针进行解引用操作。 链接错误 * 符号未定义：在链接阶段找不到函数或变量的定义。例如，只声明了函数但没有实现。 * 重复定义：在多个源文件中定义了相同的全局变量或函数。 模板错误 * 模板参数不匹配：在使用模板时，传递的模板参数类型不符合模板的要求。 * 模板实例化错误：模板实例化过程中出现问题，如模板函数的调用参数无法推导出正确的模板参数类型。 命名空间错误 * 未使用命名空间：忘记使用所需的命名空间，导致无法找到相应的标识符。 * 命名空间冲突：不同的命名空间中定义了相同名称的标识符，导致混淆。 以上只是一些常见的 C++ 错误类型，实际编程中还会遇到许多其他特定场景下的错误。通过仔细检查代码、理解错误信息以及进行适当的调试，可以帮助我们更快地发现和解决这些错误。 除此之外，可以见着

概述 新版 Acgo\tt{Acgo}Acgo 竞赛分系统参考了 AtCoder\tt{AtCoder}AtCoder 平台的 AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00[1]。 该积分系统基于 Logistic Distribution\tt{Logistic\ Distribution}Logistic Distribution（或 Sigmoid Function\tt{Sigmoid\ Function}Sigmoid Function），类似于 Elo\tt{Elo}Elo 评分系统，但进行了许多修改。 新版竞赛分系统上线后，用户参加 Acgo\tt{Acgo}Acgo 的所有比赛将会有 Rated\tt{Rated}Rated 和 Unrated\tt{Unrated}Unrated（即「评分」与「不评分」）两种状态。 正常情况下参加比赛的选手状态为 Rated\tt{Rated}Rated，状态被评为 Unrated\tt{Unrated}Unrated 包含但不仅限于以下情况： 1. 参加本场比赛前竞赛分超过本场比赛的 Rated\tt{Rated}Rated 分数线限制（RATEDBOUNDRATEDBOUNDRATEDBOUND）； 2. 比赛中作弊，被取消比赛成绩； 3. 本场比赛因不可抗力因素导致无法正常进行的将参与本场比赛的所有用户设置为 Unrated\tt{Unrated}Unrated。 对于 Rated\tt{Rated}Rated 的选手，在每场比赛中，会获得一个「表现分」。这个值代表了你在比赛中的表现如何。 粗略地说，你的每场比赛后的竞赛分为「表现分」的加权平均值（最近的比赛权重更高）减去 f(x)f(x)f(x)（xxx 为 Rated\tt{Rated}Rated 比赛的参与次数），其中 f(1)=1200f(1) = 1200f(1)=1200，且 fff 随参加的 Rated\tt{Rated}Rated 比赛的次数增加而逐渐减小并趋于零。 这意味着如果你持续获得 XXX 的表现分，你的竞赛分将从 X−1200X−1200X−1200 开始，并逐渐趋近于 XXX。 请不要担心在第一场比赛中获得很低的竞赛分，如果你参加更多比赛，分数很可能会迅速上升。当参加 101010 场比赛后，你的竞赛分将会非常接近于你的真实实力。 计算表现分 在系统内部有两种类型的「表现分」：PerfPerfPerf 和 RPerfRPerfRPerf（修正后的 PerfPerfPerf） 。 首先，对于每个参赛选手，我们计算出他们的 APerfAPerfAPerf（平均表现分）。 令 Perf1,Perf2,⋯ ,PerfkPerf_1, Perf_2, \cdots, Perf_kPerf1 ,Perf2 ,⋯,Perfk 为一位参赛选手的历史 PerfPerfPerf。其中 Perf1Perf_1Perf1 是最近参加的一场比赛，PerfkPerf_kPerfk 是最早参加的一场比赛，这位选手的 APerfAPerfAPerf 被定义为： APerf=∑i=1kPerfi×0.9i∑i=1k0.9i\begin{equation} APerf = \frac{\sum_{i=1}^{k}Perf_i \times 0.9^i}{\sum_{i=1}^{k}0.9^i} \end{equation} APerf=∑i=1k 0.9i∑i=1k Perfi ×0.9i 所有第一次参与 Acgo\tt{Acgo}Acgo 的 Rated\tt{Rated}Rated 比赛的选手的 APerfAPerfAPerf 将会被设置为 CenterCenterCenter。 CenterCenterCenter 和每一场 Rated\tt{Rated}Rated 比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND（即 Rated\tt{Rated}Rated 上限）有关。 Center=RATEDBOUND×0.4Center = RATEDBOUND \times 0.4Center=RATEDBOUND×0.4。 令 nnn 为一场比赛中所有的 Rated\tt{Rated}Rated 的参赛选手的数量，令 APerfiAPerf_iAPerfi 为第 iii 个选手的 APerfAPerfAPerf。那么比赛的 Rated\tt{Rated}Rated 榜单中，排行第 rrr 名选手的 PerfPerfPerf 被定义为满足以下公式的唯一的 XXX： ∑11+6.0(X−APerfi)/400.0=r−0.5\begin{equation} \sum\frac{1}{1 + 6.0^{(X - APerf_i) / 400.0}} = r - 0.5 \end{equation} ∑1+6.0(X−APerfi )/400.01 =r−0.5 这个 XXX 可以使用二分来计算得出。 请注意，以上的排名是所有并列名次的平均值。例如，如果有四个人并列第 333 名至第 666 名，那么这些人的排名为 4.54.54.5。 除此之外，为了避免在第一场比赛中的「表现分」方差过小，Acgo\tt{Acgo}Acgo 使用新竞赛分系统的第一场比赛（这里指 排位赛#4）的表现值会被放大处理，具体如下： Perf=(Perf−Center)×1.5+Center\begin{equation} Perf = (Perf - Center) \times 1.5 + Center \end{equation} Perf=(Perf−Center)×1.5+Center 最终，对于每个用户其 RPerfRPerfRPerf 使用以下方式计算： RPerf=min⁡{Perf,RATEDBOUND+100}\begin{equation} RPerf = \min{\{Perf, RATEDBOUND + 100\}} \end{equation} RPerf=min{Perf,RATEDBOUND+100} 其中 RATEDBOUNDRATEDBOUNDRATEDBOUND 对于不同的比赛是不一样的，每场比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND 会在竞赛说明中给出。 计算竞赛分 定义 FFF 为： F(n)=∑i=1n0.81i∑i=1n0.9i\begin{equation} F(n) = \frac{\sqrt{\sum_{i=1}^{n} 0.81^i}}{\sum_{i=1}^n 0.9^i} \end{equation} F(n)=∑i=1n 0.9i∑i=1n 0.81i 定义 fff 为： f(n)=F(n)−F(∞)F(1)−F(∞)×1200\begin{equation} f(n) = \frac{F(n) - F(\infin)}{F(1) - F(\infin)} \times 1200 \end{equation} f(n)=F(1)−F(∞)F(n)−F(∞) ×1200 定义 ggg 为： g(X)=2.0X800\begin{equation} g(X) = 2.0^{\frac{X}{800}} \end{equation} g(X)=2.0800X 该函数可以给更好的表现赋予更多的权重。因此，极好表现与较好表现之间的差异会非常大，而重大失误与一般失误之间的差异则不会那么大。 这样可以使得当参赛者在比赛中打出了超出水平的发挥时，会增加更多的竞赛分；当参赛者在比赛中打出了远低于自己水平的表现分时，不会减少太多的竞赛分； 令 RPerf1,RPerf2,⋯ ,RPerfkRPerf_1, RPerf_2, \cdots, RPerf_kRPerf1 ,RPerf2 ,⋯,RPerfk 为一位参赛选手的历史 RPerfRPerfRPerf，其中 RPerf1RPerf_1RPerf1 为当场比赛的 RPerfRPerfRPerf。那么本场比赛结束后，其竞赛分为： Rating=g−1(∑1kg(RPerfi)×0.9i∑1k0.9i)\begin{equation} Rating = g^{-1}(\frac{\sum_1^k g(RPerf_i) \times 0.9^i}{\sum_1^k 0.9^i}) \end{equation} Rating=g−1(∑1k 0.9i∑1k g(RPerfi )×0.9i ) 然后考虑公式 (6)(6)(6) 的 fff 函数对竞赛分的影响，定义以下函数[2]： mapRating(r)={400exp⁡(400−r400)r≤400rr>400\begin{equation} mapRating(r) = \begin{cases} \frac{400}{\exp{(\frac{400 - r}{400})}} &{r \le 400}\\ r & {r \gt 400}\\ \end{cases} \end{equation} mapRating(r)={exp(400400−r )400 r r≤400r>400 最终 RatingRatingRating 计算出来为： TrueRating=mapRaing(Rating−f(n))\begin{equation} TrueRating = mapRaing(Rating - f(n)) \end{equation} TrueRating=mapRaing(Rating−f(n)) 其中 nnn 为已经参加的 Rated\tt{Rated}Rated 的比赛场次（包括本场）。 本文档的版本记录 * 10/29/2024 Ver. 1.00: 第一版。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00 ↩︎ 2. AtCoderのレート計算式\tt{AtCoderのレート計算式}AtCoderのレート計算式 ↩︎

📋 ACGO社区帮助手册 🌟 站务汇总 * 站务汇总 🏆 赛事信息 * 巅峰排行榜规则介绍 * 排位分机制揭秘 🗨️ 讨论区指南 * 发帖规范 * 删帖原因 团队招募帖子通常不应发布在“学习讨论”板块； 发布无意义内容； 发布违反社区规范的内容； 发布格式混乱，难以阅读的题解，不符合题解规范的题解。 📘 格式手册 * LaTeX数学公式语法 * Markdown语法教程 🤔 提问与解答 * 提问的智慧 * 题解编写技巧 🤖 AC助手使用指南 * AC助手的正确食用方法 🧠 知识点精华贴 * 知识点精华贴

上一期啊，讲了BFS,（虽然更多人看到的是暑假小逝）那么在上一期结尾，我说过有个叫双源BFS的东西，十分的牛b吽吽，那今天就来浅讲一手§(￣▽￣)§ 1.0 基本思想 要知道，双源这名字一听就高大上，那怎么区分这玩意和普通BFS的区别呢？，那本狗就不得不讲一个例子了..... 一只舔狗，舔他的女神，年年舔，月月舔，日日舔，可能舔三年才能感动女神...不排除女神拒绝了，爆了个MLE，嘻嘻φ(゜▽゜*)♪ 所以这就是典型的单相思（BFS）没结果的！你看隔壁，小帅和小美本来就那啥，表个白恐怕三分钟就够了....单身狗小声哭泣ing(ノへ￣、) 这就是双源BFS。 咳咳（战术清嗓），扯远了。从刚刚那个生动形象的例子就可以知道，双源BFS的基本思想就是双向奔赴，而且也可以看到他很明显的优势就是快！（效率高），而且他还有一个优势就是省内存（毕竟可以更快相遇） 1.5 适用范围 双源BFS的应用范围还算广，毕竟能够应对的数据范围更大，主要还是分3类： 1. 一般搜索问题（略） 2. 搜索问题butBFS或DFS不顶事er 3. 题有明确的特征（强制把一坨双源BFS塞你嘴里） 2.0 具体实现 双源BFS有两种实现方法，主要差别在需要维护的队列数量上..... 即顺序和逆序共用队列和不共用队列 2-A 共用队列 这种情况每次出入队都得两个两个来，如下： 还有一个注意点！怎么停止循环？ 只要两个点相同就好了啦！^o^/ 如下： 除了以上代码外，其他基本代码大体相同，不予给出其实是我懒得敲━━(￣ー￣*|||━━。 2-B 不共用队列 其实出入队也差不多，长这样： 这里再把停止给出~ 其实两个一样，所以空一行给个空气U•ェ•*U 然后是扩展邻居，两个差不多所以一起给 懒 _〆(´Д｀ ） 最后，一道美味的双源BFS就被你食用完了！加上灵魂之zi，浇给 蟹蟹你的阅读，留个点赞加关注吧太难写了求求了(;´༎ຶД༎ຶ`) ·

C++ 是一种通用的编程语言，它的设计目标是提供一种高效、可靠的系统级编程方法。 > 一、基本概念 > C++的基本框架包括预处理指令、函数、类和对象等。下面分别介绍这些基本概念。 1. 预处理指令：在C++程序中，以#开头的行称为预处理指令，如#include、#define等。它们在编译前对代码进行处理，例如包含头文件、定义宏等。 2. 函数：函数是C++ 程序的基本组成单元，它由返回类型、函数名和参数列表组成。一个C++程序通常由多个函数组成，其中主函数main()是程序的入口点。 3. 类和对象：C++是一种面向对象的编程语言，类是对象的模板，对象是类的实例。类定义了一组属性和方法，用于描述对象的状态和行为。通过类可以创建多个具有相同属性和方法的对象。 > 二、基础语法和数据类型 > 接下来，我们来看一下C++的基本输入输出、数据类型、运算符、分支结构、循环结构、数组和函数。 1. 输入输出：C++使用iostream库进行输入输出操作。常用的输入输出对象有cin（标准输入）和cout（标准输出）。例如： 2. 数据类型：C++有多种数据类型，包括整型（int）、浮点型（float、double）、字符型（char）等。此外，还有引用类型（&）、指针类型（*）等复杂数据类型。 3. 运算符：C++提供了丰富的运算符，包括算术运算符（+、-、*、/等）、关系运算符（>、<、==等）、逻辑运算符（&&、||等）等。例如： 4. 分支结构：C++使用if-else语句进行条件判断。例如： 5. 循环结构：C++有两种循环结构，分别是for循环和while循环。例如： 6. 数组：数组是一种数据结构，用于存储相同类型的多个元素。在C++中，可以使用数组来存储一组数据，例如整数、浮点数或字符等。例如： 7. 函数：函数是C++ 程序的基本组成单元，它由返回类型、函数名和参数列表组成。一个C++程序通常由多个函数组成，其中主函数main()是程序的入口点。例如：

00 INTRO > 前面咱们主要讲的都是算法类的(例如:高精度算法,深度优先搜索(DFS)&广度优先搜索(BFS),排序算法) > 那么今天咱们讲的简单一点,把知识点往回倒,来介绍一下C++标准模板库(STL) > > > 本文均同步CSDN-Ysjt | 深 > > 点击链接关注!!! > > > > > 话不多说进入正题: 01 STL模板库历史 对于软件界来说,做出一个可重复利用的东西是一直以来的梦想,为了实现这个梦想,就有许多我们熟悉的东西被发明创造了出来(后面我也会讲),例如函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries) > 为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹 > 性、交互操作性(相互合作性,interoperability),诞生了STL。 > STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要 > 出现在 c+ +中，但是在引入 c++之前该技术已经存在很长时间了。 > -- 选自C++ - STL标准库 STL容器主要包括(敲黑板): 容器(CONTAINER) 算法(ALGORITHM) 迭代器(ITERATOR) 02 STL容器的使用(参考:①,②) 我们先用表格讲一下STL容器的名称和区别 容器 实现 查询 插入 删除 其它 vector(本篇讲解) 一段内存连续区域 查询下标O(1) 值查询O(N) 尾部O(1) 中间O(N) 尾部O(1) 中间O(N) 空间只增不减,空间够,1.5-2倍扩容 list 双向链表 O(N) O(1) O(1) deque 中控器map+多个连续缓冲区 查询下标O(1) 值查询O(N) 尾部O(1) 头部O(N) 尾部O(1) 头部O(N) list&vector(见上)折中 map(set)(本篇讲解) 红黑树(无重复,有序) 下标访问log2(N) log2(N) log2(N) stack(本篇讲解) deque 插入栈顶O(1) 删除栈顶O(1) queue(本篇讲解) deque 插入队尾O(1) 插入队头O(1) 03 STL库-VECTOR动态数组[1] VECTOR数组简介:VECTOR数组是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组，在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（LIST是一个双向链表，在同一个位置插入大量的数据时速度很快，但是查找的速度就会慢很多） VECTOR数组在初始化的时候,需要加上头文件 但如果定义的是万能头,则可以直接忽略 定义数组时,切记不可像INT ,FLOAT ,DOUBLE ,CHAR一样直接定义 对于vector数组来说,要用: 时间复杂度:O(N) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 04 STL库-MAP(SET)[2] MAP的作用:访问地址符(篇幅有限,后面还有栈和队列,我们简单讲一下使用方法) map跟vector一样,有专属于自己的头文件,见下: 使用万能头的可以忽略 在MAP后加一个括号SET是因为SET拥有去重的功能,配合代码如下: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 05 STL库-STACK(栈) 栈的东西太多,我个人认为可以单独开一篇文章讲解了(后续完善,可查看目录) 那么就将最重要的东西!!!!! 顺序进出(入栈,出栈) 接下来给出代码:ACGO官方例题 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 06 STL库-QUEUE(队列)[3] 讲了这么多,到队列这我们直接引用了,(手指报废,眼睛报废),如果后面有时间会修改的 (AC君见谅) > 队列是一种线性的数据结构【线性数据结构：数组、栈、队列】 > 相比数组，队列对应的数据操作是数组的子集。 > 只能从一端(队尾)添加元素，只能从另一端(队首)取出元素。 例题-传送门 AC题解: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 07 STL库-LIST(链表)[4] list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素). 代码及例题不给了(作者懒) 修改发布时间:2024年7月3日18:43:12 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 03节参考内容:①,②,③,④,⑤ ↩︎ 2. 04节参考(引用):①,② ↩︎ 3. 06节参考(引用):① ↩︎ 4. 07节参考内容(引用):①,② ↩︎

第一题题解 A33695.换行 > 解题思路 > 第一题比较简单，单纯的考察C++的基础知识转义字符的使用，注意一下换行符的使用即可。 第二题题解 A33696.求和 > 解题思路 > 第二题主要考察了一下时间复杂度的计算，如果简单的使用forforfor循环，nnn的范围是1≤n≤21474836471≤n≤21474836471≤n≤2147483647，时间复杂度是O(n)O(n)O(n)，会超时，所以需要使用数学方法，高斯求和(等差求和公式)，时间复杂度是O(1)O(1)O(1)。 第三题题解 A33697.权重 > 解题思路： > 本题的重点还是考察了数据范围，把数据开成long long，基本上就没啥问题了。 > 首先读取字符串，统计一下每个字符出现的次数，然后给的公式计算权重进行累加即可。 第四题题解 A33698.最大公约数 1. 计算因子个数： * 定义函数 countFactors，用于计算一个整数的因子个数。通过从 1 到该整数的平方根进行遍历，因为如果 i 是 num 的因子，那么 num / i 也是 num 的因子（除了 i 和 num / i 相等的情况，此时只算一个）。 * 对于每个能整除 num 的 i，先将因子个数加 2（表示 i 和 num / i 两个因子），如果 i 和 num / i 相等，就需要把多算的一次减掉，从而准确得到 num 的因子个数。 2. 处理输入并计算因子个数序列： * 在 main 函数中，先读取输入的 n（整数个数）和 m（目标累加和）。 * 然后通过循环依次读取 n 个整数，对于每个读取到的整数 tmp，调用 countFactors 函数计算其因子个数，并将结果添加到向量 v 中，这样就得到了所有整数的因子个数构成的向量。 3. 排序与累加查找： * 使用 sort 函数对向量 v 中的因子个数进行排序，排序方式是从大到小（通过 greater<int> 指定）。 * 接着通过循环依次累加排序后的因子个数，用变量 sum 记录累加和。在每次累加后，判断 sum 是否大于等于 m，如果满足这个条件，就输出当前的累加次数 i + 1（因为索引是从 0 开始的，所以要加 1 才是从 1 开始计数的正确索引），然后程序结束。 复杂度分析 1. 时间复杂度： * 计算因子个数部分：对于每个整数计算因子个数时，需要从 1 到该整数的平方根进行遍历，假设输入的整数最大值为 N，那么计算一个整数因子个数的时间复杂度大约为 O(N)O(\sqrt{N})O(N )。总共要计算 n 个整数的因子个数，所以这部分的时间复杂度大约为 O(nN)O(n\sqrt{N})O(nN )。 * 排序部分：使用 sort 函数对向量 v 进行排序，一般 sort 函数的时间复杂度为 O(nlogn)O(nlogn)O(nlogn)，这里 n 是向量 v 的长度，也就是输入的整数个数。 * 累加查找部分：通过循环依次累加向量 v 中的元素，时间复杂度为 O(n)O(n)O(n)。 * 综合起来，整个程序的时间复杂度大约为 O(nN+nlogn+n)O(n\sqrt{N} + nlogn + n)O(nN +nlogn+n)，简化后约为 O(nN+nlogn)O(n\sqrt{N} + nlogn)O(nN +nlogn)。 2. 空间复杂度： * 主要的空间消耗在于存储每个整数的因子个数的向量 v，向量 v 的长度最大为 n，所以空间复杂度为 O(n)O(n)O(n)。 第五题题解 A33699.美丽数组 1. 判断回文 2. 判断奇数项之和与偶数项之和是否相等 时间复杂度分析 * 对于每个测试用例： * 判断回文数组的操作：在 isPalindrome 函数中，需要遍历数组的前半部分元素，时间复杂度为 O(n)O(n)O(n)，其中 n 为数组的长度。 * 判断奇数项之和与偶数项之和是否相等的操作：在 isSumEqual 个函数中，需要遍历数组的每一个元素，时间复杂度也为 O(n)O(n)O(n)。 * 总共存在 T 个测试用例，所以整个程序的时间复杂度为 O(Tn)O(Tn)O(Tn)。 空间复杂度分析 * 主要的空间消耗在于存储数组元素的数组 a，其大小为 100005，但实际上对于每个测试用例，只使用了其中的 n 个位置来存储数组元素。所以空间复杂度为 O(n)O(n)O(n)，这里的 n 是指每个测试用例中数组的长度。 第六题题解 A33700.字典序问题 1. 整体思路 * 我们要想办法构造出一个可能的字典序最大的字符串。考虑到数字越大在字典序中越靠后，所以要尽量让高位数字尽可能大。 * 因为 n 的取值范围可能很大（从代码中看，是用字符串来接收 n 的，这也暗示了 n 可能是非常大的数），所以我们通过对 n 的字符串表示进行分析和操作来找到答案。 2. 具体步骤 * 首先，判断 n 是否全部由数字 9 组成。如果是，那字典序最大的字符串就是 n 本身啦，不过代码里没有显式地处理这种全 9 的情况，我们先接着往下看一般情况的处理。 * 然后，我们先构造一个临时字符串 tmp，它的长度是 n 的长度减1，并且每个字符都是 9。为什么要这样做呢？因为我们要让高位尽可能大，所以先假设高位都是 9，然后再根据实际情况进行调整。假设现在有一个5位数，那么9999算是最大的数字，除非这个5位数是9999?,所以需要对最后一位数字进行判断。 * 最后，我们再看 n 的最后一位数字。如果 n 的最后一位不是 0，并且 n 的前 len - 1 位（也就是去掉最后一位的部分）组成的字符串大于等于我们刚才构造的 tmp，那就把 n 的最后一位数字加到 tmp 后面。这样得到的 tmp 就是我们要找的字典序最大的字符串啦。

ACGO欢乐赛34 T1 方法一：使用数组统计 观察到 1≤Ai≤1051 \leq A_i \leq 10^51≤Ai ≤105，所以可以开一个长度为 10510^5105的数组进行统计。 方法二：使用set统计 方法三：使用map统计 T2 直接按照题目要求模拟即可 T3 根据分析，最小值的最大值，可以联想到二分算法。需要考虑的有序性，在题目中寻找。 我们发现， d1+d2+d3d_1+d_2+d_3d1 +d2 +d3 的结果是一定的，为 n−3n-3n−3 。 考虑枚举三者之中最小的间隔，但是不确定元素不止有间隔本身大小，还有间隔之间的差值，这个思路舍弃。 现在考虑二分枚举三个间隔之间的最小的那个差值。 证明： 设 d1,d2,d3d_1,d_2,d_3d1 ,d2 ,d3 三个间隔从小到大。 枚举三者之间最小差值为 xxx ，那么第二个差值也是不小于 xxx ，否则当前假设 xxx 不成立。 设 d1=ld_1 = ld1 =l ,则如果要满足假设必须满足 d2d_2d2 最小也是 l+xl+xl+x ,同理 d3d_3d3 最小也是 l+2∗xl+2*xl+2∗x 。此外，对于 d3d3d3 还可以通过 n−3−l−(l+x)n-3-l-(l+x)n−3−l−(l+x) ，即为 n−3−2∗l−xn-3-2*l-xn−3−2∗l−x 。 如果根据总长度算出来的理论高度，不小于满足最小间隔差值是 xxx 要求的最小高度，即为 n−3−2∗l−x≥l+2∗xn-3-2*l-x \ge l+2*xn−3−2∗l−x≥l+2∗x 化简得到 n−3≥3∗l+3∗xn-3\ge 3*l+3*xn−3≥3∗l+3∗x 看似存在两个不确定元素，间隔本身大小，还有间隔之间的差值，但是要求取最小值的最大值，也就是说 xxx 要最大，满足题目的前提下是 l=0l = 0l=0 。即 n−3≥3∗xn-3\ge 3*xn−3≥3∗x 。 当然这题你也可以用结论写，结论自己摸索哈。 T4 埃氏筛法，时间复杂度O(nloglogn)O(nloglogn)O(nloglogn) T5 利用两个map维护即可。 你也可以不用map，开两个数组，映射到对应的ASCII即可。 T6 直接输出即可

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ （这是我发的第二个赛事题解了，希望大家支持）。 由于本次欢乐赛顺序比较佛系（最后一题竟然送分），所以讲解顺序是先易后难。 T6： 不用讲了吧，是个人都会。 代码： T1: 这题我的做法是桶，先统记再判断，代码如下： T2: 这题我是把dx、dy数组用map存起来，再模拟。 代码如下： T4: 和欢乐赛33#的T4一样，许多人不能AC的原因是在判断质数这方面判断到sqrt（n）就可以了，不然会TLE。 代码如下： T5: 这题我还是用桶来存，挨个判断（真可恶，本来能上前五的，结果一开始没有memset断送的我的霸业）。 代码如下： 最终BOSS——T3： 这题一眼——分值500就知道不简单，我认为难度硬是要排的话甚至可以排到巅峰赛的第三题。 首先，我们需要深刻地剖析题意，看起来是放假，但是深加思考后会发现实际上就是要我们分面包，尽量切得不均匀，才能使这个最小值最大。那怎样切得尽量不均匀呢？就会有人想到等差数列了。而这一题的难点在于怎样得出等差数列的公差。——诶呀，两层for不就行了吗？（兄弟，你看看数据范围）。那我们要怎样得到公差呢——套公式！！众所周知，等差数列之和=末项 * n / 2。我们这里的n已经固定是3了，所以 就可以得出最大的末项，而通过末项我们就可以用 来得出公差，有了公差，再推下去，最后用min求答案即可。 代码如下： 别看它代码这么少，你做出来了吗？！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如果这篇题解对你有用，还请点赞支持一下~

写原创好文，推荐加“精” 为了鼓励优质内容创作，我们决定自12月起，长期征集优质内容，推荐加精，欢迎大家分享在社区刷题过程中的宝贵经验。 活动时间 长期有效，首次开启时间：12月1日 内容要求 不限算法解题思路、编程技巧、调试经验，或者是心得体会和学习方法，要求如下： 技术型 * 分享你在刷题过程中遇到的挑战和困惑； * 详细描述你是如何解决这些问题的，包括算法解题思路、具体代码实现等； * 可以分享具体题目的解题思路和代码； 干货型 对某一知识内容进行总结，有较高的收藏价值。 如何参与 * 在讨论区发布文章时，在标题添加#创作计划# ，即可被统计到。 活动奖励 优秀内容将被推荐至首页精华分区； 被加精的作者可以获得ACGO社区周边一套； 注意事项 * 参与活动的帖子需真实有效，没有抄袭或侵权行为； * chatgpt代写文章，聊天记录等不计入活动； * 我们将严格审查，不合规的帖子一经发现将取消参资格。

这题太简单了，入门题还差不多，你告诉我这题是 提高+/省选-？

从第一个提交的都骗分