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

COCR 普及赛 #1 题解 比赛结束后公布

个人难度：红红红红红红红橙橙 官方难度：红红红红红？红橙黄 T1 经典题目，非常简单 T2 两重for + if判断 可以用两个数组存相对坐标（dx和dy） 最后注意检测（第22行） T3, T4, T5都是最简单的输出，直接上代码（这里为了方便用的是PY） T3 T4 T5 T6 这题是数学题，令人尴尬的是本蒟蒻数学很菜所以直接下一道 （此时队长坐不住了） T7 这道题目直接求积然后数字逆序即可 注意不能用to_string()再字符串逆序，因为会有前导0 T8 重点是质数判断，剩下的就好做了 T9 个人认为最难的题 主要思路就是按输入顺序一个个按照循环次数减一，直到减成0换到下一位 感谢： 题解人@古希腊掌管AC和WA的神 队长@忘川秋库

欢迎大家使用该程序，初创，无较好的界面，感谢支持！ 其中“ASK2”中要填192.168.0.112 代码

LaTeX数学公式的常用语法讲解传送门 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Markdown是一种轻量级标记语言，用于格式化纯文本，本文为Markdown的一些常用语法讲解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 标题： 使用#符号来创建标题，1个#代表一级标题，2个#代表二级标题，以此类推，最多支持六级标题。 效果： 一级标题 二级标题 三级标题 四级标题 五级标题 六级标题 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 强调和斜体和划线： 使用*包围文本以实现斜体效果，使用**包围文本以实现加粗效果，使用~~包围文本以实现加粗划线效果。 效果： 斜体文本 加粗文本 划线文本 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 链接： 创建链接使用[],()。[]中放置链接文字，()中放置链接地址。 效果： 点击这里百度一下 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图片： 插入图片使用!,[],()。[]中放置替代文字，()中放置图片链接。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 列表： 无序列表使用-,+,*开头，有序列表使用数字 +.。 效果： * 无序列表项 * 无序列表项 1. 有序列表项 2. 有序列表项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 引用： 使用>来创建引用块，可以引用叠引用。 效果： > 这是引用的内容 > > > 这也是引用的内容 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码块： 用三个反引号`包围代码块，后面可以跟着一个语言名称来指定代码块的语言，以便语法高亮。 记得去掉\。 效果： 一个反引号`可以作为单行代码块。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 水平分隔线： 使用三个或更多连续的*来创建水平线。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 表格： 表格由表头和表格内容组成，使用|,-来分隔不同的行列，下面是一个简单的表格示例： 使用|来分隔每一列，而使用-在表头下创建分隔线。表头是必需的，它定义了每一列的标题。 效果： 标题1 标题2 标题3 内容1 内容2 内容3 内容4 内容5 内容6 希望表格的内容居中或靠右对齐，可以使用:来指定对齐方式，例如： 输出结果如下： ---左对齐--- ---居中对齐--- ---右对齐--- 内容1 内容2 内容3 内容4 内容5 内容6 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 脚注： 在文本中需要添加脚注的位置，使用[^]来标记脚注的引用标记，方括号内可以填写任何标识符，通常是数字例如[^1]。 在文档的末尾，添加一个相匹配的脚注内容，使用[^]: 内容的形式来定义脚注内容。例如[^1]: 这是脚注的内容。 下面是一个示例： 结果： 这是一个示例[1]，在文末可以看到脚注的解释。 脚注会显示在全文的最下面，请到最底部查看脚注。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 数学公式： 单个$用于表示行内数学公式或数学表达式，用于排版数学符号、方程式、上下标、分数等数学内容，他的使用通常与LaTeX\LaTeX{}LATE X数学语法相对应，因为Markdown支持一些LaTeX\LaTeX{}LATE X的数学语法，例如： 效果： y=mx+by = mx + by=mx+b 两个$用于表示多行数学公式或数学表达式，例如： 效果： n!k!(n−k)!=(nk)\frac{n!}{k!(n-k)!} = \binom{n}{k} k!(n−k)!n! =(kn ) 数学公式里，^,_用于表示上标与下标，后面可以用括号包括进一大串数字与字母 效果： ai+j+bja^{i+j}+b_{j}ai+j+bj ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以上是Markdown的常用语法讲解，欢迎评论讨论。 评论区用不了Markdown，题目，团队介绍能用，忘记说了赶紧补充 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 这是脚注的内容，用于解释示例的含义。 ↩︎

ACGO欢乐赛#44题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是本蒟蒻第一次写题解，请各位大佬们多多指点 注：个人代码习惯不喜欢写空格，敬请谅解。 本场欢乐赛整体难度太水了较为简单，评级如下。 题目 真实难度 个人难度 O 入门 入门 行图 入门 入门 罚时计算 入门 入门 困难的字符串改造问题 普及- 入门 追求更多的玫瑰花 入门 入门 进制转换 入门 普及- 话不多说，直接开始—— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目解析 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 -- O 知识点：输入输出 题目描述：要求出100以内的所有数中，哪一个数的“O”最多，数字 0,4,6,9 里面有 1 个 "O"，数字 8 中有 2 个 "O"。 解析：其实题目中已经说得很明确了，对单一一个数字来说，8是有最多“O”的数，所以两位数88所含有的“O”最多，直接输出即可。 代码 时间复杂度：O(1) T2 -- 行图 知识点：循环结构，条件语句 题目描述：输入n个整数，第二个数开始，对于每个数，判断这个数是否为上一个数的因数，累计总数。 解析：定义一个num用来记录上一个数，一个sum用来统计数量，每次判断并累计数量。 代码 时间复杂度：O(N) T3 -- 罚时计算 知识点：循环结构 题目描述：输入n表示有n个人，随后对于每个人，输入m个数，表示每道题提交的次数，每道题除第一次提交外，随后的提交每多一次，罚时20min,求出每个人的总罚时。 解析：直接循环遍历即可，注意每次累加器清零。 代码 时间复杂度：O(N*M) T4 -- 困难的字符串改造问题 知识点：字符串 题目描述：输入一个字符串，每遇到一个空格，就将它替换成下一个字母（A到Z，Z下一个是A）。 解析：定义一个num记录目前遇到的空格数量，每次遇到空格就求现在应该替换的字母，并替换。注意输入处理，用getline，否则输入不了空格。 代码 时间复杂度：O(|S|) T5 -- 追求更多的玫瑰花 知识点：输入输出，条件语句 题目描述：给定一个n个数的数组，其中的每一个数只能是1或-1，再有m次询问，每次给出两个数l和r，判断能否调整数组顺序使得[l,r]中的数加起来为0（即1与-1的数量相等），输出"happy"或"sad"。 解析：思维题。统计数组中1(变量zheng)与-1(变量fu)的数量，若区间有奇数个数，则直接输出"sad"，否则判断有没有区间数量/2个1与-1，输出。 代码 时间复杂度：O(N+M) T6 -- 进制转换 知识点：进制转换，sort排序 题目描述：给定n个数，先将它们转换成八进制，随后： * 先按照的最低位从大到小排序。 * 如果最低位的数一样，那么就按这个数进行从小到大排序。 解析：将八进制的数存在数组b中（用十进制的方式存储，方便排序），再排序（用sort,写一个cmp）,注意一定要开long long，否则会WA!! 代码 时间复杂度：O(N LOG N) 最后，希望大家支持一下第一次写题解的我，AC君给个周边吧，谢谢！

T4 个人难度：绿 下位 一眼并查集。 题目问题是如果某些人离开群后有多少人得不到消息，我们可以假设这些人在一开始时就离开， 然后再将查询反转，把问题转换成第 pip_ipi 个人加入第 cic_ici 个群后会有多少人收不到消息。这样就转换成简单的并查集问题了，只需要查询班长所在的集合有多少人即可。 注意特判（如样例二）的情况，就是班长没有加入任何一个群，这时得不到消息的人数为 n−1n-1n−1 而不是 nnn，因为班长是知道这个消息的。 时间复杂度：O((∑ki+m+q)log⁡m+(q+∑ki)log⁡n)O((\sum k_i+m+q)\log m+(q+\sum k_i)\log n)O((∑ki +m+q)logm+(q+∑ki )logn)（我也不知道啊，我乱写的） T5 个人难度：黄 中位 首先打个正常的 DP，令 dp[i][j]dp[i][j]dp[i][j] 为到达第 iii 行第 jjj 列时宝藏价值最大值，则有 dp[i][j]=max⁡k=imdp[i−1][k]+a[i][j](k≠j)dp[i][j]=\max_{k=i}^{m} dp[i-1][k]+a[i][j](k\not= j) dp[i][j]=k=imaxm dp[i−1][k]+a[i][j](k=j) 如果暴力硬算，时间复杂度 O(n×m2)O(n\times m^2)O(n×m2)。 注意到这个 max 可以分成左右两部分，即 dp[i][j]=max⁡(max⁡k=1i−1dp[i−1][k],  max⁡k=i+1mdp[i−1][k])+a[i][j]dp[i][j]=\max(\max_{k=1}^{i-1} dp[i-1][k],\space\space\max_{k=i+1}^m dp[i-1][k])+a[i][j] dp[i][j]=max(k=1maxi−1 dp[i−1][k],  k=i+1maxm dp[i−1][k])+a[i][j] 我们可以使用线段树来求出区间和。 注意使用滚动数组，否则会 MLE；还要特判 m=1m=1m=1 的情况。 时间复杂度：O(n×mlog⁡m)O(n\times m\log m)O(n×mlogm)。 什么？你说直接记录前缀最大值和后缀最大值也能过？没错，赛时我唐了。 T6 个人难度：绿 上位 本题是道大模拟题，我将使用分类讨论的思路讲解。为方便表示时间复杂度，我们令 nnn 为数字个数，即 n=4n=4n=4。 注意到题目只需要我们凑出 242424 的倍数，所以除法是个诈骗，可以不用管。 于是我们可以把构造结果分成 555 种情况，分别判断。 1. a×b×c×da\times b\times c\times da×b×c×d。 模拟难度：红 中位 显然，只有一种情况，直接判断、输出即可。注意乘法取模。 时间复杂度：O(n)O(n)O(n) 。 2. a±b×c×da\pm b\times c\times da±b×c×d。 模拟难度：红 上位 我们可以选择一个数作为 aaa，剩下三个数就作为 b,c,db,c,db,c,d。 时间复杂度：O(n2)O(n^2)O(n2)。 3. a±b±c±da\pm b\pm c\pm da±b±c±d 。 模拟难度：橙 上位 ai,bi,ci,dia_i,b_i,c_i,d_iai ,bi ,ci ,di 都有两种选择情况：正，负。 所以我们可以爆搜一波，如果有可能的结果，就对应输出。 注意，第一个数不能为负，所以如果 ai<0a_i\lt 0ai <0，需要找一个大于 000 的数代替 aia_iai 。 时间复杂度：O(2n)O(2^n)O(2n) 。 4. (a±b)×(c±d)(a\pm b)\times(c\pm d)(a±b)×(c±d)。 模拟难度：橙 上位 我们先选好配对的两个数，再和第三种情况一样，爆搜四个数的状态，最后输出即可。 时间复杂度：O(n×2n)O(n\times 2^n)O(n×2n)。 5. a×(b±c±da\times (b\pm c\pm da×(b±c±d 。 模拟难度：黄 中位 这里的右括号可以加在任何地方，如 a×(b)±c±d,a×(b±c)±d,a×(b±c±d)a\times (b)\pm c\pm d,a\times (b\pm c)\pm d,a\times(b\pm c\pm d)a×(b)±c±d,a×(b±c)±d,a×(b±c±d) 。 我们先挑选 aaa，即乘数，然后搜索每个数的 444 个状态。假设现在要枚举状态的数为 kkk，则 444 种状态的结果如下： 1. kkk，这是 kkk 在括号外面，并且符号为正的结果。 2. −k-k−k，这是 kkk 在括号外面，并且符号为负的结果。 3. a×ka\times ka×k，这是 kkk 在括号里面，并且符号为正的结果。 4. −a×k-a\times k−a×k，这是 kkk 在括号里面，并且符号为负的结果。 接着，我们把所有在括号内和在括号外的数分别进行组合、输出。 时间复杂度：O(n×4n)O(n\times 4^n)O(n×4n)。 卧槽类似我了 谁抄我题解我 [数据删除]

只能对一半QAQ 测试点搞错了TAT 以下是源代码

#5 MLE 和 #8 UKE会归为RE，批注：作者也不知道为什么！

阿哈来凑热闹了

ACGO排位分机制大揭秘 1、原理解释 积分机制是基于ELO积分（埃洛积分），该积分最早应用于国际象棋，理论核心是胜率差。ELO在解释选手对战的情况分为三个部分： 1. 根据战力差来计算对战胜率情况：多少分差对应多少胜率。 2. 选手根据对手情况和战斗结果所表现出来的水平分。 3. 选手完成对局后实际获得的积分增长。 1.1 预期胜率计算公式 Pi,j=11+10rj−ri400P_{i,j} = \frac{1}{1+10^{\frac{r_j-r_i}{400}}} Pi,j =1+10400rj −ri 1 公式中 ( P_{i,j} ) 代表选手 ( i ) 战胜选手 ( j ) 的概率，( r_i ) 代表选手 ( i ) 的当前积分值，( r_j ) 代表选手 ( j ) 的当前积分值。可以观察到： * 当 ( r_j = r_i ) 时，( P_{i,j} = \frac{1}{2} )，即对手实力与自己相当，我方胜率恰好一半。 * 当 ( r_j > r_i ) 时，( P_{i,j} < \frac{1}{2} )，即对手实力强于自己时，我方胜率不足一半。 * 当 ( r_j < r_i ) 时，( P_{i,j} > \frac{1}{2} )，即对手实力弱于自己时，我方胜率高于一半。 并且 ( P_{i,j} + P_{j,i} = 1 )，即我方胜率加对方胜率等于1，均符合“常识认知”。 1.2 背后原理 该公式的背后原理（涉及概率论，此处笼统介绍）为：任何一名选手的即时表现都应该是符合正态分布的（围绕某一个水平上下波动），如下图： 实际上，可以依据上图，使用微积分来计算出两位玩家相互之间的胜率，其所对应的图像，与采用最小二乘法优化后得到的式子 ( P_{i,j} = \frac{1}{1+10^{\frac{r_j-r_i}{400}}} ) 拟合度较高，因此使用该式作为胜率计算的公式。 通俗地来说，这个公式与通过概率论计算的胜率情况非常接近，且计算相对简便，因此使用了该式作为概率公式。 1.3 预期排名公式 seedi=∑j=1,j≠inPj,i***eed_i = \sum_{j=1, j \neq i}^n P_{j,i} + 1 seedi =j=1,j=i∑n Pj,i +1 即将每个人打败选手 ( i ) 的概率累加起来，再加一作为选手 ( i ) 比赛的预期排名。 我们可以得到： ∑i=1nseedi=∑i=1n∑j=1,j≠inPj,i+n\sum_{i=1}^n seed_i = \sum_{i=1}^n \sum_{j=1, j \neq i}^n P_{j,i} + n i=1∑n seedi =i=1∑n j=1,j=i∑n Pj,i +n 由于 ( P_{j,i} + P_{i,j} = 1 )，故上式为： =(n−1)⋅n2+n=(n+1)⋅n2= \frac{(n-1) \cdot n}{2} + n = \frac{(n+1) \cdot n}{2} =2(n−1)⋅n +n=2(n+1)⋅n 注意到最后的实际排名是 ([1,n]) 的一个排列，排名总和为 (\frac{(n+1) \cdot n}{2})。 会发现使用该预期排名公式后，预期排名能够显示出所有人之间实力对获胜概率的影响，并且所有人的预期排名总和与实际排名总和相等。 1.4 依据真实排名所计算出的表现分 比赛结束后第 ( i ) 名选手的真实排名记作 ( rank_i )。令 ( m_i = \sqrt{seed_i \cdot rank_i} )，即期望排名与真实排名的几何平均数。 之后我们使用二分算法来找到一个分数 ( R_i ) 作为选手 ( i ) 在这场比赛的表现分。( R_i ) 需要满足在该场比赛的预期排名计算时，如果把 ( r_i ) 替换为 ( R_i )，其他人的分数不变的情况下，计算出的 ( seed_i = m_i )。 实际上非常容易可以定性分析出，分数（实力）更强的人在同一场比赛中的预期排名应该更低（指的是数值）。这样就建立了一个分数-排名之间的单调关系，使得我们可以使用二分算法来找到 ( R_i )。 依此来计算表现分，既考虑到了真实排名的情况下，又能够依靠原始分计算出的预期排名来做一个对原始分的“锚定”效果，使得表现分有一个与原始分相接近的趋势。同时由于表现分的二分计算过程也是与预期排名公式中的原理相同，因此该分数也考虑到整场比赛所有人参与人的水平。 1.5 分数变化值 取表现分 ( R_i ) 与原分值 ( r_i ) 差值的一半作为选手 ( i ) 赛后的分数变化值。 即选手 ( i ) 的分数变化值 ( change_i = \frac{R_i - r_i}{2} )。 综合上述所有计算过程，会发现计算结果满足以下两个性质： * 若赛前 ( r_A < r_B )，比赛结果 ( A ) 依然比 ( B ) 差，那么更新后 ( r_A \leq r_B )。 * 若赛前 ( r_A < r_B )，比赛结果 ( A ) 比 ( B ) 好，那么 ( rating ) 改变量 ( change_A \geq change_B )。 2、排位分是否上涨的因素 在上述算法的影响下，比赛排位分是否上涨，主要由对手的能力决定： 如果当前选手水平很牛逼，但是赛事的其他选手水平很菜，本场赛事结果中，即便当前选手获得了不错的成绩，也不会加很多排位分，因为elo算法认为这应该是理所当然的，因此用户没法通过大量战胜低等级的对手来提升排位分。 反之，一个菜鸡在满是牛逼用户的竞争中取胜，则会获得特别高的排位分。该算法能让用户的竞赛分值更趋向于其真实水平，从而使我们的排位分更具公信力。

附魔不要书架吗

这种题不就白坑我一次看测试点吗

一、下载 VS CODE 1. 打开浏览器，进入 VS Code 官方网站 。 2. 在官网首页，点击Download for Windows 3. 下载完成后，运行安装程序，按照安装向导的提示完成安装。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、安装 中文语言包 扩展 1. 打开 VS Code。 2. 点击左侧栏的扩展图标（四个方块的图标）。 3. 在搜索框中输入 “Chinese”，找到 “Chinese (Simplified) (简体中文) Language Pack for ” 扩展，点击 “安装” 按钮进行安装。该扩展为 VS Code 提供了 中文 语言支持。 4. “Ctrl+Shift+P”组合键以显示“命令面板”，然后键入“display”以筛选并显示“Configure Display Language”命令，随后点击“中文(简体)”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、安装 C++ 扩展 1. 打开 VS Code。 2. 点击左侧栏的扩展图标（四个方块的图标）。 3. 在搜索框中输入 “C++”，找到 “C/C++” 扩展，点击 “安装” 按钮进行安装。该扩展为 VS Code 提供了 C++ 语言支持。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、配置 C++ 编译器 1. 安装编译器，如在 Windows 上可安装 MinGW-w64 。下载地址：MinGW-w64，点击 。下载完成后，解压到合适的目录，例如 “C:\mingw-w64”。 2. 配置环境变量： * 在 Windows 系统中，打开“控制面板”，搜索“查看高级系统设置”，点击“环境变量” 点击“Path” 随后点击“新建”，把你的MinGW-64的‘gcc’的地址输进去，例如：“C:\mingw64\bin\gcc.exe”，然后一直点确定。 3. 验证编译器安装：打开命令提示符，输入 “g++ -v”，若显示编译器版本信息，则安装成功。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、配置 VS CODE 的 C++ 环境 完成上述步骤后，还需要对 VS Code 进行一些配置，以确保它能正确找到编译器并进行编译和运行。 1. 创建一个 C++ 项目 在 VS Code 中，点击菜单栏的 “文件” -> “新建文本文件r”，选择一个你希望存放项目的文件夹。 2. 创建C++ 文件 3. 配置调试文件 点击Ctrl + Shift + D,点击运行和调试，选择g++，然后在运行和调试下面点击创建 launch.json 文件。紧接着会弹出来一个框，选C++ (GDB/LLDB)。 右下角添加配置，选择(gdb) 启动。 回到你的c++文件，点击 就可以了！ 喜欢就点个赞吧

AC狗是外星生物，具体是那个星球我也不知道。 外星人侵入地球，大家一定要保护好自己的脑袋！

食用说明:主播第一次上完DP写的小笔记,应该比较亲民,但是主播在上课之前是有C++基础的 适用群体:学过输入输出,判断,for循环的人类 DP(动态规划)的用处:当n>20,也就是不能用爆搜(DFS)解决时,可以尝试用DP来解决. 一.DP模板 1.状态表示 一般就是答案要求什么，就表示什么 比如：斐波那契数列： a[i]就是第i个斐波那契数列得知 2.答案 根据状态表示，决定答案 3.状态转移方程 重要在转移：从先前求出的数值转移，决定要求的数值 4.遍历方向 比如数字金字塔：就可以从上到下或者从下到上 5.初始化 状态转移时数字可能会越界，所以就需要初始化 当这5个条件全部考虑到位,你就能AC了(窝老史说的) 接下来列举一些有关它们的题目,帮助理解: 二.例题 钞票问题: 1.状态表示: 上文提到过,答案要求什么就表示什么:这个表示指的是你要列一个怎样的数组. 比如钞票问题要求凑够n元需要的最少纸币. 那么可以做出一个数组: dp[i]表示凑够n元需要的最少纸币. 2.答案: 既然dp[i]表示的是凑够n元需要的最少数量的纸币,那么答案就是dp[n] 3.状态转移方程: 上文提到过"转移"就是从先前求出的数值转移，决定要求的数值. 那么在钞票问题中如何利用先前求出过的数值转移呢? 我们知道有1,5,11元的纸币. 那么在我们求dp[i]的时候,我们可以从3个之前求出过的数值来"转移",它们就是: 只要将这三个数值中的最小值+1就是dp[i]的数值 *因为分别由1,5,11的三张钞票;最小值是因为要求最少数量的纸币. 此时不需要考虑遍历方向 5.初始化: 只有一个点需要注意: 上文提到的 i-1 , i-5 和 i-11 是否会是负数 解决方案:判断一下就好了 但这个好像不算初始化吧 核心代码: 数字金字塔: 1.状态表示: 虽然它是一个金字塔,但可以直接看成数组: 题目想要路径经过数字最大和(也就是从第一行到最后一行经过的数字和的最大值) 那么我们可以用一个二维数组: dp[i][j]表示从第1行第1列的数到第i行第j列的数的最大值(听起来可能怪怪的,但希望大家尝试去理解) 2.答案 最大值一定在最后一行里,所以直接利用for循环取出最后一行的最大值. 3.状态转移方程: 我们知道,这个橙色的点,可以到达自己左下方的点和自己右下方的点(也就是那两个绿的): 所以,同样的每一个绿点会有自己左上方的点和右上方的点,它可以选择左上方的累计值,也可以选择右上方的累计值,我们当然选更大的,也就是: 别忘了,(i,j)这个位置本身也是有值的,所以就是: 4.遍历方向: 这里有两个方向: 1.从上至下 2.从下至上 由于主播太菜,所以只学习了从上至下(这样比较适合新人理解),所以这里我们选择从上至下 (有感兴趣的小伙伴也可以自己研究一下从下至上哦) 5.初始化 从上至下不需要初始化. 核心代码: 类似题目:T18992.不同的路径 传球游戏:

T1 - 变色龙 完整代码 深度分析 关键公式 子矩阵枚举范围： [ i \in [1, n - m + 1], \quad j \in [1, n - m + 1] ] 常见错误 * 子矩阵范围错误：写成 i <= n 导致越界。 * 字符比较错误：直接比较 v1[k][l] 和 v2[k][l] 的 ASCII 值而非字符。 改进建议 1. 哈希优化：预处理每个子矩阵的哈希值，比较哈希值而非逐字符。 2. 提前终止：当子矩阵左上角不同时，跳过整个区域。 3. 输入验证：添加 if (m > n) 处理无效输入。 T2 - 打印机 完整代码 深度分析 关键公式 双面打印纸张数： [ \text{pages} = \left\lceil \frac{m}{2} \right\rceil ] 常见错误 * 奇数页处理错误：x/2 未考虑向上取整。 * 边界条件遗漏：未处理 m=0 或 n=0。 改进建议 1. 数学简化：直接计算 (m + 1) // 2 代替集合操作。 2. 逻辑优化：比较单面和双面成本时，统一使用整数运算。 3. 测试用例：添加 m=0、n=0 和 m=1 的测试。 T3 - 机器人 完整代码 深度分析 关键公式 移动后的坐标： [ \text{new_x} = \begin{cases} \text{障碍物右侧第一个空位} & \text{向右} \ \text{障碍物左侧第一个空位} & \text{向左} \ \text{障碍物上侧第一个空位} & \text{向上} \ \text{障碍物下侧第一个空位} & \text{向下} \end{cases} ] 常见错误 * 二分查找方向错误：add 函数中未正确比较 v[mid] >= x。 * 坐标越界：未处理移动后超出网格范围的情况。 改进建议 1. 二分优化：使用 lower_bound 和 upper_bound 替代手写二分。 2. 边界限制：添加 nowx 和 nowy 的范围约束。 3. 代码复用：合并 add 和 sub 函数为通用移动逻辑。 T4 - 公告 完整代码 深度分析 关键公式 并查集合并： [ \text{size}[y] += \text{size}[x] ] 常见错误 * 节点编号混淆：学生和边的编号未正确区分。 * 逆向处理错误：未正确恢复边的状态。 改进建议 1. 节点编号设计：将学生和边的编号范围明确划分（如学生 1~n，边 n+1~n+m）。 2. 离线处理优化：使用栈记录合并操作，逆向时撤销合并。 3. 空间优化：改用 vector<vector<int>> 存储边。 T5 - 登塔 完整代码 深度分析 关键公式 状态转移方程： [ f[i][k] = \max_{j \neq k} f[i-1][j] + a[i][k] ] 常见错误 * 极值维护错误：优先队列未正确维护前两大值。 * 特殊情况处理：未处理 m=1 时无法移动的情况。 改进建议 1. 极值优化：直接记录每一层的最大值和次大值，而非依赖优先队列。 2. 边界处理：在 m=1 时，直接输出 arr[1][1]。 3. 动态规划优化：将状态压缩为两个数组（当前层和前一层）。 T6 - 24点 完整代码 深度分析 关键公式 8的倍数构造： [ \begin{cases} 1 + 7 = 8 \ 3 + 5 = 8 \ 2 \times 4 = 8 \ 2 + 6 = 8 \ 4 \times 6 = 24 \end{cases} ] 常见错误 * 余数分类遗漏：未处理 i=0 的情况。 * 表达式构造错误：未考虑除法。 改进建议 1. 余数分类完善：添加 i=0 的处理逻辑。 2. 表达式验证：生成表达式后计算结果，确保等于24。 3. 除法实现：添加除法判断逻辑，处理整除情况。 全题改进总结 1. 算法优化：优先使用哈希、并查集等高效数据结构。 2. 边界处理：重视输入范围和特殊情况（如 m=0、n=1）。 3. 代码规范：拆分复杂函数，添加注释，避免冗余逻辑。 4. 数学思维：加强模运算、抽屉原理等数学方法的应用。 5. 测试覆盖：针对不同数据范围和边界条件设计测试用例。 致歉： 部分LATEX & MARKDOWN公式无法在ACGO上完整显示，对于公式显示不全导致您阅读困难的情况，深表歉意😣 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 写法支持： Markdown的常用语法讲解 LaTeX数学公式的常用语法讲解 鸣谢： 各位大佬有什么意见就在评论区提，很感谢也很期待各位大佬们的指正

这个ACGO怎么第一题就那么难?

3行代码秒了

求助！！！ @MACW07 @AC君 @暗沙业步汇 @法兰西玫瑰 @‮队团加不）童帅_者仇复 快来！