期末考成绩终于出了，这次试卷很简单（2026.6.29) 展示一波---- 这是我的成绩，拿下数学状元，英语状元，道法状元（我人品不好） 这是我好兄弟的成绩 成功拿下科学状元 这是曾经7080过我的人的成绩 通过作弊+临时抱佛脚拿下语文状元

是这样的·························································································································································································································· 这天，我正在弄那个今日运势 前几天： 注意看还有几天获得AC之神的祝福 今天： 怎么回事！！！！！！！！！！！！！！！！！！！！！ 555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555

一不小心把山炸塌了一块

狗的星吗

好难

前言 蒟蒻的markdown用的不好，轻喷。 正题 双端队列就像是普通队列的加强版，使用时要引入头文件 <deque> ，大家都知道，普通的队列只支持从队头入队与从队尾出队。 而双端队列支持队头/尾的出/入队（长难句），也就是四个操作。 打个比方，队列就像是一个马路，普通的是单行道，只能从一边进一边出，而双端队列就是一个双向的路，可以从南到北也可以从北到南。当然，队列中的一些操作在双端队列里也可以使用。 注意： 在调用 front() 与 back() 时要记得判读队列是否为空，不然会RE。 双端队列的遍历 其中的 auto 可以自动切换数据的类型，不用写 deque<int>::iterator 这么长一段。 这里提一嘴，其实 dq[1] 这样的写法也是可以的，但是不推荐大家用。凑字数 例题 B3656 【模板】双端队列 1，这道题数据有点恶心，大家看看循环里的过程就行，这里的list其实就是一个可以储存大数据的deque，讲完了这些我们来看代码。 这道题就是考察同学们对双端队列的函数使用，对于每个操作按照题目上写就可以了。 后记 感谢@古希腊掌管AC和WA的神帮忙修正内容/bx

创作者：YYF LINK（此为转载，版权为YYF LINK所有，原文出处） 本文研究蚂蚁在圆柱体表面从一点到其正对点（主视图最左下到最右上）的最短路径问题，通过将路径分解为底面弦与侧面展开图直线，建立总长度关于底面圆心角 Θ的目标函数 L(Θ)利用微分法求得驻点，通过二阶导数严格证明内部驻点均为局部极大值，从而确定全局最小值仅在区间端点取得。比较两端点路径长度，得到最短路径的判别准则。本文推导严谨，结论简洁明确。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、问题溯源 有一个底面半径为 rrr，高为 hhh 的圆柱，AAA 是底面圆周上的一点，在主视图最左下角；BBB 为顶面圆周上一点，在主视图最右上角。一只蚂蚁从 AAA 出发，可在圆柱表面自由爬行，求其爬至 BBB 点的最短路径。 二、表示总长度 设蚂蚁从 AAA 沿底面某一条弦走到底面圆周上一点 PPP，再由 PPP 沿侧面最短路径至 BBB。设底面圆心为 OOO，弧 APAPAP 的圆心角为 θ\thetaθ，即 ∠AOP=θ\angle AOP=\theta∠AOP=θ（0≤θ≤π0\leq \theta \leq \pi0≤θ≤π）。 如图为蚂蚁路线及圆柱体沿高 PP′PP'PP′ 切割的侧面展开图。图中 P′B′=P′B^P'B'=\widehat{P'B}P′B′=P′B，则总长度 L(θ)=AP+PB′L(\theta)=AP+PB'L(θ)=AP+PB′. 计算底面弦长 APAPAP： OA=OP=rOA=OP=rOA=OP=r，在等腰 △AOP\triangle AOP△AOP 中，顶角为 θ\thetaθ。取 APAPAP 的中点 MMM，连结 OMOMOM。 因为等腰三角形三线合一，则 ∠AOM=θ/2\angle AOM=\theta/2∠AOM=θ/2。 由正弦定义，sin⁡θ2=AMr\sin \frac{\theta}{2}=\frac{AM}{r}sin2θ =rAM ∴AM=rsin⁡θ2\therefore AM=r\sin \frac{\theta}{2}∴AM=rsin2θ ∴AP=2AM=2rsin⁡θ2\therefore AP=2AM=2r\sin \frac{\theta}{2}∴AP=2AM=2rsin2θ 计算侧面长 B′P′B'P'B′P′： ∵AC\because AC∵AC 为直径，PP′PP'PP′ 是圆柱的一条高 ∴\therefore∴ 显然弧 P′BP'BP′B 与弧 PCPCPC 长度相等。 又 ∵AC\because AC∵AC 是直径 ∴\therefore∴ 弧 APAPAP 与弧 P′BP'BP′B 的度数之和为 180∘180^\circ180∘ ∵∠AOP=θ\because \angle AOP=\theta∵∠AOP=θ ∴AP^=rθ\therefore \widehat{AP}=r\theta∴AP=rθ，P′B^=r(π−θ)\widehat{P'B}=r(\pi-\theta)P′B=r(π−θ) ∴P′B′=r(π−θ)\therefore P'B'=r(\pi-\theta)∴P′B′=r(π−θ) ∴PB′=[r(π−θ)]2+h2\therefore PB'=\sqrt{[r(\pi-\theta)]^2+h^2}∴PB′=[r(π−θ)]2+h2 ∴\therefore∴ 总长度 L(θ)=2rsin⁡θ2+[r(π−θ)]2+h2L(\theta)=2r\sin \frac{\theta}{2}+\sqrt{[r(\pi-\theta)]^2+h^2}L(θ)=2rsin2θ +[r(π−θ)]2+h2 ，θ∈[0,π]\theta\in[0,\pi]θ∈[0,π] (1) 三、求驻点 对 θ\thetaθ 求导（链式求导）： L′(θ)=rcos⁡θ2−12[r2(π−θ)2]−1/2⋅ddθ[r2(π−θ)2+h2]L'(\theta)=r\cos \frac{\theta}{2}-\frac{1}{2}[r^2(\pi-\theta)^2]^{-1/2}\cdot \frac{d}{d\theta}[r^2(\pi-\theta)^2+h^2]L′(θ)=rcos2θ −21 [r2(π−θ)2]−1/2⋅dθd [r2(π−θ)2+h2] =rcos⁡θ2−12r2(π−θ)2+h2⋅[−r2⋅2(π−θ)]=r\cos \frac{\theta}{2}-\frac{1}{2\sqrt{r^2(\pi-\theta)^2+h^2}}\cdot[-r^2\cdot 2(\pi-\theta)]=rcos2θ −2r2(π−θ)2+h2 1 ⋅[−r2⋅2(π−θ)] =rcos⁡θ2−−r2(π−θ)r2(π−θ)2+h2=r\cos \frac{\theta}{2}-\frac{-r^2(\pi-\theta)}{\sqrt{r^2(\pi-\theta)^2+h^2}}=rcos2θ −r2(π−θ)2+h2 −r2(π−θ) (2) 令 L′(θ)=0L'(\theta)=0L′(θ)=0，得方程： rcos⁡θ2−−r2(π−θ)r2(π−θ)2+h2=0r\cos \frac{\theta}{2}-\frac{-r^2(\pi-\theta)}{\sqrt{r^2(\pi-\theta)^2+h^2}}=0rcos2θ −r2(π−θ)2+h2 −r2(π−θ) =0 rcos⁡θ2=−r2(π−θ)r2(π−θ)2+h2r\cos \frac{\theta}{2}=\frac{-r^2(\pi-\theta)}{\sqrt{r^2(\pi-\theta)^2+h^2}}rcos2θ =r2(π−θ)2+h2 −r2(π−θ) −r(π−θ)r2(π−θ)2+h2=cos⁡θ2\frac{-r(\pi-\theta)}{\sqrt{r^2(\pi-\theta)^2+h^2}}=\cos \frac{\theta}{2}r2(π−θ)2+h2 −r(π−θ) =cos2θ （3） 四、判定驻点非全局最小值 1.求二阶导数 第一项：原式 =−r2sin⁡θ2=-\frac{r}{2}\sin \frac{\theta}{2}=−2r sin2θ 第二项：原式 =r2h2[r2(π−θ)2+h2]3/2=\frac{r^2 h^2}{[r^2(\pi-\theta)^2+h^2]^{3/2}}=[r2(π−θ)2+h2]3/2r2h2 ∴L′′(θ)=−r2sin⁡θ2+r2h2[r2(π−θ)2+h2]3/2\therefore L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^2 h^2}{[r^2(\pi-\theta)^2+h^2]^{3/2}}∴L′′(θ)=−2r sin2θ +[r2(π−θ)2+h2]3/2r2h2 2.求解 hhh 并代入 由(3): −r(π−θ)r2(π−θ)2+h2=cos⁡θ2\frac{-r(\pi-\theta)}{\sqrt{r^2(\pi-\theta)^2+h^2}}=\cos \frac{\theta}{2}r2(π−θ)2+h2 −r(π−θ) =cos2θ r2(π−θ)2=cos⁡2θ2⋅[r2(π−θ)2+h2]r^2(\pi-\theta)^2=\cos^2 \frac{\theta}{2}\cdot [r^2(\pi-\theta)^2+h^2]r2(π−θ)2=cos22θ ⋅[r2(π−θ)2+h2] r2(π−θ)2=cos⁡2θ2⋅[r2(π−θ)2]+cos⁡2θ2⋅h2r^2(\pi-\theta)^2=\cos^2 \frac{\theta}{2}\cdot [r^2(\pi-\theta)^2]+\cos^2 \frac{\theta}{2}\cdot h^2r2(π−θ)2=cos22θ ⋅[r2(π−θ)2]+cos22θ ⋅h2 cos⁡2θ2⋅h2=r2(π−θ)2−cos⁡2θ2⋅[r2(π−θ)2]\cos^2 \frac{\theta}{2}\cdot h^2=r^2(\pi-\theta)^2-\cos^2 \frac{\theta}{2}\cdot [r^2(\pi-\theta)^2]cos22θ ⋅h2=r2(π−θ)2−cos22θ ⋅[r2(π−θ)2] cos⁡2θ2⋅h2=r2(π−θ)2(1−cos⁡2θ2)\cos^2 \frac{\theta}{2}\cdot h^2=r^2(\pi-\theta)^2(1-\cos^2 \frac{\theta}{2})cos22θ ⋅h2=r2(π−θ)2(1−cos22θ ) （4） ∵sin⁡2x+cos⁡2x=1\because \sin^2 x+\cos^2 x=1∵sin2x+cos2x=1 所以 cos⁡2θ2⋅h2=r2(π−θ)2sin⁡2θ2\cos^2 \frac{\theta}{2}\cdot h^2=r^2(\pi-\theta)^2\sin^2 \frac{\theta}{2}cos22θ ⋅h2=r2(π−θ)2sin22θ ∵sin⁡2(θ/2)cos⁡2(θ/2)=tan⁡2θ2\because \frac{\sin^2(\theta/2)}{\cos^2(\theta/2)}=\tan^2 \frac{\theta}{2}∵cos2(θ/2)sin2(θ/2) =tan22θ ∴h2=r2(π−θ)2tan⁡2θ2\therefore h^2=r^2(\pi-\theta)^2\tan^2 \frac{\theta}{2}∴h2=r2(π−θ)2tan22θ ∵h>0,θ∈(0,π)\because h>0,\theta\in(0,\pi)∵h>0,θ∈(0,π) 所以 h=r(π−θ)tan⁡θ2h=r(\pi-\theta)\tan \frac{\theta}{2}h=r(π−θ)tan2θ （5） 将（5）代入（4）：L′′(θ)=−r2sin⁡θ2+r2⋅r2(π−θ)2tan⁡2(θ/2)[r2(π−θ)2+r2(π−θ)2tan⁡2(θ/2)]3/2L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^2\cdot r^2(\pi-\theta)^2\tan^2(\theta/2)}{[r^2(\pi-\theta)^2+r^2(\pi-\theta)^2\tan^2(\theta/2)]^{3/2}}L′′(θ)=−2r sin2θ +[r2(π−θ)2+r2(π−θ)2tan2(θ/2)]3/2r2⋅r2(π−θ)2tan2(θ/2) L′′(θ)=−r2sin⁡θ2+r4(π−θ)2tan⁡2(θ/2)[r2(π−θ)2(1+tan⁡2(θ/2))]3/2L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^4(\pi-\theta)^2\tan^2(\theta/2)}{[r^2(\pi-\theta)^2(1+\tan^2(\theta/2))]^{3/2}}L′′(θ)=−2r sin2θ +[r2(π−θ)2(1+tan2(θ/2))]3/2r4(π−θ)2tan2(θ/2) L′′(θ)=−r2sin⁡θ2+r4(π−θ)2tan⁡2(θ/2)[r2(π−θ)2(1+tan⁡2(θ/2))]3/2L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^4(\pi-\theta)^2\tan^2(\theta/2)}{[r^2(\pi-\theta)^2(1+\tan^2(\theta/2))]^{3/2}}L′′(θ)=−2r sin2θ +[r2(π−θ)2(1+tan2(θ/2))]3/2r4(π−θ)2tan2(θ/2) ∵tan⁡2x****ec⁡2x\because \tan^2 x+1=\sec^2 x∵tan2x****ec2x ∴L′′(θ)=−r2sin⁡θ2+r4(π−θ)2tan⁡2(θ/2)[r2(π−θ)2sec⁡2(θ/2)]3/2\therefore L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^4(\pi-\theta)^2\tan^2(\theta/2)}{[r^2(\pi-\theta)^2\sec^2(\theta/2)]^{3/2}}∴L′′(θ)=−2r sin2θ +[r2(π−θ)2sec2(θ/2)]3/2r4(π−θ)2tan2(θ/2) ∴L′′(θ)=−r2sin⁡θ2+r4(π−θ)2tan⁡2(θ/2)r3(π−θ)3sec⁡3(θ/2)\therefore L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r^4(\pi-\theta)^2\tan^2(\theta/2)}{r^3(\pi-\theta)^3\sec^3(\theta/2)}∴L′′(θ)=−2r sin2θ +r3(π−θ)3sec3(θ/2)r4(π−θ)2tan2(θ/2) ∴L′′(θ)=−r2sin⁡θ2+rtan⁡2(θ/2)(π−θ)sec⁡3(θ/2)\therefore L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r\tan^2(\theta/2)}{(\pi-\theta)\sec^3(\theta/2)}∴L′′(θ)=−2r sin2θ +(π−θ)sec3(θ/2)rtan2(θ/2) ∵sec⁡x=1cos⁡x\because \sec x=\frac{1}{\cos x}∵secx=cosx1 ，tan⁡x=sin⁡xcos⁡x\tan x=\frac{\sin x}{\cos x}tanx=cosxsinx ∴L′′(θ)=−r2sin⁡θ2+rsin⁡2(θ/2)cos⁡(θ/2)(π−θ)=rsin⁡θ2(−12+sin⁡2(θ/2)cos⁡(θ/2)π−θ)\therefore L''(\theta)=-\frac{r}{2}\sin \frac{\theta}{2}+\frac{r\sin^2(\theta/2)\cos(\theta/2)}{(\pi-\theta)}=r\sin \frac{\theta}{2}\left(-\frac{1}{2}+\frac{\sin^2(\theta/2)\cos(\theta/2)}{\pi-\theta}\right)∴L′′(θ)=−2r sin2θ +(π−θ)rsin2(θ/2)cos(θ/2) =rsin2θ (−21 +π−θsin2(θ/2)cos(θ/2) ) ∵sin⁡θ2cos⁡θ2=12sin⁡θ\because \sin \frac{\theta}{2}\cos \frac{\theta}{2}=\frac{1}{2}\sin\theta∵sin2θ cos2θ =21 sinθ ∴L′′(θ)=rsin⁡(θ/2)2(sin⁡θπ−θ−1)\therefore L''(\theta)=\frac{r\sin(\theta/2)}{2}\left(\frac{\sin\theta}{\pi-\theta}-1\right)∴L′′(θ)=2rsin(θ/2) (π−θsinθ −1) （6） 3.证明全局最小 我们需要证明 θ∈(0,π)\theta\in(0,\pi)θ∈(0,π) 时，sin⁡θπ−θ<1\frac{\sin\theta}{\pi-\theta}<1π−θsinθ <1，即 sin⁡θ<π−θ\sin\theta<\pi-\thetasinθ<π−θ 令 g(θ)=π−θ−sin⁡θg(\theta)=\pi-\theta-\sin\thetag(θ)=π−θ−sinθ， 则 g′(θ)=−1−cos⁡θ≤0g'(\theta)=-1-\cos\theta\leq 0g′(θ)=−1−cosθ≤0 ∴g(θ)\therefore g(\theta)∴g(θ) 在 (0,π)(0,\pi)(0,π) 上严格递减 且 g(0)=πg(0)=\pig(0)=π，g(π)=0g(\pi)=0g(π)=0 ∴\therefore∴ 在 (0,π)(0,\pi)(0,π) 上，g(θ)>0g(\theta)>0g(θ)>0 所以 π−θ−sin⁡θ>0\pi-\theta-\sin\theta>0π−θ−sinθ>0，即 π−θ>sin⁡θ\pi-\theta>\sin\thetaπ−θ>sinθ （7） 将（7）代入（6），则 L′′(θ)<0L''(\theta)<0L′′(θ)<0. 在任意驻点 θ∈(0,π)\theta\in(0,\pi)θ∈(0,π) 处，L′′(θ)<0L''(\theta)<0L′′(θ)<0，所以该驻点是局部极大值，不可能是局部最小值。因此，L(θ)L(\theta)L(θ) 的全局最小值只能在区间端点取得。即路程最小时，θ\thetaθ 的值只能为 000 或 π\piπ。 五、精确结果 端点 θ=0\theta=0θ=0：L(0)=π2r2+h2L(0)=\sqrt{\pi^2 r^2+h^2}L(0)=π2r2+h2 端点 θ=π\theta=\piθ=π：L(π)=2r+hL(\pi)=2r+hL(π)=2r+h 令两者相等，得 h=π2−44rh=\frac{\pi^2-4}{4}rh=4π2−4 r 因此最终判别规则为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【预告】我们即将开始研究蚂蚁圆台问题，具体内容详见此贴。

02 DFS 与连通块 一、本阶段目标 学完本阶段，学生要能做到： 二、DFS 的核心思想 DFS，全称 Depth First Search，深度优先搜索。 通俗理解： 它很像走迷宫： 三、DFS 模板：图的遍历 其中： vis 数组非常重要。没有 vis，图中有环时会无限递归。 例如： 如果没有 vis： 四、完整模板 五、连通块 在无向图中，如果一组点互相可以到达，就属于同一个连通块。 统计连通块数量的方法： 代码： 六、连通块大小 有时不仅要知道有几个连通块，还要知道每个连通块有多大。 七、网格图 DFS 迷宫、地图、岛屿都可以看成图。 方向数组： 边界判断： 网格 DFS： 八、岛屿数量模型 题目常见描述： 建模： 代码框架： 九、填涂颜色模型 类似 P1162 填涂颜色。 关键思想： 这是一个很重要的反向思维。 步骤： 这种思想在自招题里很常见： > 正面不好判断，就从反面出发。 十、染色思想 有些题要判断能不能把点分成两组，使得每条边两端颜色不同。 这就是二分图染色的基础。 其中颜色用 1 和 2 表示，3 - c 可以在 1 和 2 之间切换。 十一、DFS 常见错误 错误 后果 修正 忘记 vis 死循环或爆栈 进入点后立刻标记 递归层数太深 栈溢出 大图可改 BFS 或手写栈 网格越界 RE 先判断 inside 把 x/y 写反 答案错 统一行列含义 有向图当无向图建 可达性错误 看清题目方向 多组数据不清空 上一组数据污染 清空 g、vis 十二、课堂例题 例题 1：判断两点是否连通 给无向图，问从 s 能不能到 t。 做法： 例题 2：统计连通块 给无向图，问有几个互不相连的区域。 做法： 例题 3：迷宫方案数 给迷宫，问从起点到终点有多少条路径。 注意：这是“方案数”，不是“最短路”。 通常使用 DFS 回溯。 这里要特别强调： 十三、练习题 题号 题名 训练点 建议 P1605 迷宫 DFS 回溯、路径数量 必做 P1162 填涂颜色 从边界反向搜索 必做 P1451 求细胞数量 连通块数量 必做 P1596 Lake Counting S 八方向连通块 选做 P1330 封锁阳光大学 染色、二分图雏形 提高 P6566 观星 连通块大小 提高 链接： 十四、本阶段作业 1. 手写图 DFS 模板。 2. 手写网格 DFS 模板。 3. 解释“连通块为什么可以用一次 DFS 全部找出来”。 4. 完成 P1605、P1162。 5. 选做 P1330，并写出染色失败的条件。 十五、本阶段小结 DFS 适合解决： 但 DFS 不适合直接求无权图最短路。只要题目出现“最少步数”，优先考虑 BFS。

本人是圆桌粉 1.༺ཌༀ༃༒池瑶女帝༒༃ༀད༻这个别用和我的是一对的 2平平凡凡 3桃花仙 4.萧凡（直接从动漫里取的） 5.4.瑶曦（直接从动漫里取的） （想不出来了下期继续） 觉得不好勿喷

问有没有哈迷，我现在有个团队需要哈迷（https://www.acgo.cn/team/2010274285956993024?teamName=%25E9%259C%258D%25E6%25A0%25BC%25E6%25B2%2583%25E8%258C%25A8%25E9%25AD%2594%25E6%25B3%2595%25E5%25AD%25A6%25E6%25A0%25A1）是哈迷的话可以申请加入团队，谢谢，我一定会及时答复的。

为了不被封号，大家给我提几个建议行不？

官方题解 | 欢乐赛#76题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的动物园门票 入门 T2 皓仔的动物园参观 入门 T3 皓仔统一大小写 入门 T4 皓仔的森林施法 入门 T5 皓仔的进制求和 普及- T6 皓仔的三段数组 普及- T1 皓仔的动物园门票 题意简述 给定总票价 w 和参加活动的人数 n。 要求计算平均每张动物园门票的价格，并保留 222 位小数输出。 也就是计算： w÷nw \div n w÷n 解题思路 这是一道简单的实数除法题。 因为总票价 w 可能是实数，所以需要使用 double 类型存储。 读入 w 和 n 后，直接计算 w / n，再使用 printf("%.2f", ...) 输出保留 222 位小数即可。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T2 皓仔的动物园参观 题意简述 给定皓仔到达动物园的时间 t。 根据不同时间段输出能看到的动物： * 8≤t<108 \le t < 108≤t<10，输出 熊猫 * 10≤t<1210 \le t < 1210≤t<12，输出 猴子 * 12≤t<1512 \le t < 1512≤t<15，输出 大象 * 15≤t<1815 \le t < 1815≤t<18，输出 老虎 如果不在这些时间段内，输出 动物园已关闭。 解题思路 这是一道简单的条件判断题。 因为每个时间段都是左闭右开，所以判断时需要注意右端点不能取到。 按照题目给出的时间段依次使用 if else 判断即可。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T3 皓仔的统一大小写 题意简述 给定一个只包含英文字母的字符串 s。 每次可以修改一个字符，目标是让字符串变成以下两种情况之一： 所有字母都是大写字母； 所有字母都是小写字母。 输出最少需要修改的字符数量。 解题思路 统计字符串中大写字母的数量 cnt1，以及小写字母的数量 cnt2。 如果要全部变成大写字母，就需要修改所有小写字母，次数为 cnt2。 如果要全部变成小写字母，就需要修改所有大写字母，次数为 cnt1。 答案就是两者的较小值。 时间复杂度为 O(∣s∣)O(|s|)O(∣s∣)。 参考代码 T4 皓仔的森林施法 题意简述 有一个 n×nn \times nn×n 的森林，最开始每棵树高度都是 000。 接下来有 mmm 次施法，每次给出 a、b、x，表示第 a 行第 b 列的树长高 xxx 米。 同一棵树可能被多次施法，高度会累加。 最后输出最高的树所在的位置，题目保证最终最高的树唯一。 解题思路 用二维数组 h 记录每棵树当前的高度。 每次读入一次施法操作后，执行： 然后判断这棵树的高度是否超过当前记录的最大高度。 如果超过，就更新最高树的位置。 由于 xxx 最大可以到 10910^9109，并且同一棵树可能多次累加，所以高度要使用 long long 存储。 时间复杂度为 O(m)O(m)O(m)。 参考代码 T5 皓仔的进制求和 题意简述 给定 nnn 个数字，每个数字由字符串 s 和进制 b 表示。 需要把每个数字从 b 进制转换成十进制，然后求出所有数字的总和。 数字中可能出现： 0 到 9 表示 000 到 999； A 到 F 表示 101010 到 151515。 解题思路 对于每个字符串 s，从左到右依次处理每一位。 假设当前已经转换出的十进制值为 num，当前字符对应的数值为 x，那么更新方式为： num=num×b+xnum=num\times b+x num=num×b+x 这样就可以将整个 b 进制数字转换为十进制。 由于答案最大不超过 101810^{18}1018，所以总和以及每个转换后的数字都要使用 long long 存储。 时间复杂度为 O(n×∣s∣)O(n\times |s|)O(n×∣s∣)。 参考代码 T6 皓仔的三段数组 题意简述 给定一个长度为 nnn 的正整数数组。 现在需要选择两个分割位置，把数组分成连续的三段，并且每一段都不能为空。 对于每一种分法，分别计算三段元素和 s1、s2、s3。 要求最小化： max⁡(s1,s2,s3)−min⁡(s1,s2,s3)\max(s1,s2,s3)-\min(s1,s2,s3) max(s1,s2,s3)−min(s1,s2,s3) 输出这个最小值。 解题思路 因为 n≤500n \le 500n≤500，可以直接枚举两个分割位置。 设第一个分割位置为 i，第二个分割位置为 j，那么三段分别是： 第 111 段：111 到 i 第 222 段：i + 1 到 j 第 333 段：j + 1 到 n 为了快速求每一段的和，可以先预处理前缀和数组 s。 这样每一段的和都可以 O(1)O(1)O(1) 求出。 最后枚举所有合法分法，更新答案即可。 时间复杂度为 O(n2)O(n^2)O(n2)。 参考代码

让我们来好讨论一下0.999...是否等于1吧。 首先，我会先来逐个击破@风铃Wind bell在帖子中的四种方法 对于F1： x=0.9999...，10x=9.9999...990≠9.999... 10x-x=8.999...991≠9 对于F2： 1/3=0.333...+ϵ(无穷小)≠0.333.... 对于F3： 因为1和1.000...0001之间没有数，所以1=1.000...0001，1.000...0001和1.000...0002之间也没有数，1.000...0001=1.000...0002 因为等号具有传递性，所以1=1.000...0002，但1和1.000...0002之间有数1.000...0001，1≠1=1.000...0002，故上述方法错误 对于F4： 1/9=0.111...+ϵ(无穷小)≠0.111....

比赛 防护伞 * 思路整理：找到最小的一个伞的半径，使得该伞在以某个黑子为伞的圆心时可以覆盖到其他所有的黑子，那么要想使的伞半径最小肯定是刚好某个点位于伞的边缘上，因为不能浪费材料。所以这个半径一定是在任意两个点之间的距离中选出的。 * 解题思路：枚举圆心，那么此时半径就是圆心到距离该圆心最远的那个点之间的距离，在这个枚举的过程中找到最小半径，时间复杂度是O(n2)O(n^{2})O(n2)。 图像压缩 * 思路整理：256级灰阶中每个像素点是以16进制形式给出，我们要找出出现次数前16像素点，进行编号，其他像素点需要根据距离来映射到前16个像素点的某一个，最后将原来256级的灰阶按照编号转为16级灰阶 * 解题思路：map统计出现次数，结构体排序，排出前16像素点，后续转化阶段就暴力找与之匹配的像素点并输出其对应的16进制即可； 二进制 思路整理：在二进制下*和/分别对应左移和右移，+1和-1则是在对应位上进行累加，那么使用延迟标记的思想，当除时再去推标记，最后结束后做最后的进位操作 三角魔方 * 思路整理：一个三角形魔方可以从三个方向去转动，显然是存在循环的，可以从某一个位置去入手，一个位置经过一次操作序列会到达另一个位置，若该位置是之前在转动过程中已经到达过的，那么显然是构成了循环，因为位置是有限的（16个）因此最多执行操作序列16次就会出现循环，那么利用该循环即可快速找到该位置字符最终的位置。 * 解题思路： * 首先是对于魔方转动的模拟处理 * 一种是把三角形的魔方映射到二维数组中，参考杨辉三角，然后观察每一个转动的规律来实现模拟，这样的话会比较麻烦，有点烧脑。 * 一种比较直白的想法，直接映射到一维数组中，然后再图上给A~P按顺序标号，就可以知道每次操作是把谁和谁交换了。 * 设计一个函数来找循环节，找到循环节后，减去之前已经执行过的操作次数，再去模上循环节，在转动该次数，即可得到当前字符最终的位置。 * 同时考虑不存在循环节的情况，也就是操作次数小于16时，此时直接暴力转动即可。 课堂练习 公交换乘 * 整理思路：搭乘地铁获得公交优惠卷，坐公交时一定会先使用优惠卷，如果没有满足条件的优惠卷可以用再去花钱。对于优惠卷使用时的限制：1、优惠卷的获得时间与当前公交开始乘坐的时间不得超过45分钟。2、优惠卷对应的地铁价格不得低于当前公交的价格 。3、如果有多张满足前两个条件的，优先用最先获得的优惠卷 * 解法：对于优惠卷我们需要用一个数据结构去维护，当我们坐公交时从数据结构中找是否存在满足条件的优惠卷。根据条件限制，要求我们优先使用最早获得的，对应我们的queue 。如果存所有的优惠卷然后每次都去一一判断就是超时时间复杂度为：O(n2)O(n^2)O(n2)，但是我们发现当一个优惠卷因为时间问题不可用时，下一次公交车也一定不会用，所以我们可以提前把因不满足时间的优惠卷给丢出去。这样就是最多45个优惠卷，去找满足条件2的优惠卷即可。最终的时间复杂度为O(45∗n)O(45*n)O(45∗n) 密码锁 * 题意理解：给定 n 个"锁后状态"，找一个密码 P，使得每个状态都能从 P 一次操作到达。 * 整理思路：重点在于每个状态都要从P一次操作达到，意味着要从 每个状态操作一次得到新的集合中找出这些这些集合的交集。 * 解法： * 法1：暴力枚举每个状态操作一次得到的新的集合，并对其中的状态打上标记，最后看那些状态被打上了n次标记，那这个状态就是交集，因此答案就要+1。时间复杂度为O(81∗n+105)O(81*n+10^5)O(81∗n+105) * 法2：既然要求交集那么就意味着满足条件的状态一定在第一个锁后状态进行一次操作得到状态集合中，那么我们就可以拿着这个集合去检查有哪些状态是其他锁后状态可以通过一次操作得到的，在经过n次筛选最后剩下的就是答案。 一元二次方程 * 整理思路：给出一个一元二次方程的各项系数，让我们输出他的两个解，如果没有解则输出No。有的话需要我们按照最简的形式给出：p1+p2,其中p1和p2都得是最简，最简定义：分数要化简，开根要化简。 * 解法： * 1、首先根据公式判断是否存在解 * 2 、有解的情况下要判断Δ是否是完全平方数 * 3、若不是则不需要加sqrt直接对p1和p2进行分数化简：利用GCD来化简 * 4、处理Δ不是完全平方数的情况 * 是否是完全平方数的倍数，是则提取最大的出来变成整数 * 对p1和p2进行分数化简 儒略日 * 整理思路：给出儒略日的起始日期 、在 儒略历 和 格里高利历下天数的计算规则。那我们就把时间线分为儒略历时期和 格里高利历 以及特殊时期 那么我们根据上述划分，就可以找到儒略日rir_iri 所对应的年份，得出年后就可以根据年份来得出具体的月和日 * 解题思路： * 可以发现对于儒略历和格里高利历之间的唯一区别是闰年的判断不同，要想定位到年，那么只用考虑每年具体的天数然后做除法计算即可，那么就按照三个时期来进行计算。 * 儒略历 是满足4的倍数即为润年。因此计算出1582这个分界线与起始日期之间有多少个4的倍数即可解决，对于格里高利历来说则是4的倍数但不是100的倍数或者是400的倍数即可，也是找出这些数即可解决问题。可以从数学角度来计算a到b之间有多少x的倍数的数 * 注意由于天数在1e9那么年份就在1e7左右如果暴力去求rir_iri 对应的年份的话时间上会比较紧张，那么可以考虑二分加速查找。 * 得出年份后进行分类讨论即可得出月份

rt.

好难呀谁给个题解

刷罐还有脸了

666GESP8级两道题全是黄

细节：通过率0%