🎉栏目 「码上开聊」 正式上线啦！🎉 作为我们ACGO社区的全新专栏，这里将不定期采访社区中的大佬们，让大家更加了解他们的编程历程与心得，探讨更多的技术细节，也让更多成员有机会与他们交流。 如果你也有有趣的编程经历，或者希望在社区分享你的成长故事，欢迎私信AC君！！💪 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ VOL1：镇站之宝-MACW ww 这是一篇攒了很久的访谈，终于可以发出啦！ > 个人档案 * 姓名：王盛祺 * 年级：高二 * 坐标：美洲东部 * 爱好：编程、旅游、睡觉 * 社区主页：ACGO个人主页 * 入站时间：2023.11.09 * 获奖经历： * USACO 金组别 * OUCC Elite 组国际荣誉奖 * ACSL Senior 个人最高奖，团队金奖 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 高能访谈 Q1 最开始为什么选择学习编程？ Macw： Q2 在学习C++过程中遇到过哪些困难，通常是怎么解决的？ Macw : 我感觉最大的困难就是会遇到瓶颈期，等学习到某几个阶段之后就会感觉很难的去提升自己。题目做来做去就是类似的题目，但那些具有挑战性的题目又比较畏惧去做，就会卡在这个状态，久而久之这个程序设计能力就一直没有提升。有点类似我们要突破舒适圈，而突破舒适圈这个过程是很艰辛的。 我个人认为没有特别好的解决办法，就是拼命多学习算法，多练。我觉得算法就是熟能生巧。如果实在感觉到累了，就去休息（休息个一个半月这样子），等重新拾取动力之后再行动。（休息也不是放着不管，中途可以去回过头阅读一下自己以前写的代码，把不熟悉的题再巩固巩固。 Q3 是什么促使您在社区中这么活跃？ Macw：（我可以说我比较清闲吗。还有就是无聊的时候会写文章。可以理解为，顺手的事。 Q4 出题的灵感来源是什么？ Macw：身边发生的一些的事，很多题都有真实的故事的，有时候我会写在题干里。 Q5 你觉得哪道题最满意？ Macw：都是我出的，我都非常满意。 Q6 在社区出题对学习有什么帮助？ Macw：出题可以加深和巩固你对有些算法的理解。而且出题的前提是你需要对某一类算法运用地非常熟练。所以可以在出题的过程中找到自己的问题。还有就是出题后你要写题解。 Q7 写题解有什么好处？ Macw：写题解时能重新审视问题，加深对题目的理解。具体可以参考这个题解链接 Q8 编程学习中最难忘的经历是什么？ Macw：通宵修 bug（哈哈哈哈）。因为小数精度问题，导致两段同样正确的代码无法同时通过所有测试点。最终还是没解决，我只能把数据量调小（那时候 ACGO 还没有 SPJ）。这真是尴尬，这既不是我的问题，也不是 C++ 的问题，而是电脑从诞生起就存在的问题。计算机诞生之初就诞生了很多历史遗留问题。 前几天我还跟我朋友做项目的时候提到了时间戳的问题，MySQL 数据库的时间戳最多到 2147483647，也就是说到了 2038 年，数据库的日期就爆 int 了。这真是一个很大的问题，到时候估计又要重现 2000 年的千年虫的事件了。 Q9 听说你还写过书？ Macw：去年写了一本书作为生日礼物送人，今年可能会有续篇。 这本书主旨在为初次尝试深入计算机编程的学生提供一个全面且系统性的教学参考材料，通过对基础知识的深入探究，为学生未来的学习之路预先铺平道路。它的目的远不仅仅是编写一本教程，更是对我自身在探寻编程之路上所积累的心血的回馈，犹如一份长期的学习笔记。 虽然我已尽力保证本书的质量，但入目所见的排版和文案可能存在一些不完美之处。我不能保证完全避免所有的错别字或排版错误。因此，我强烈建议读者在阅读过程中发现问题能够积极反馈给我，以力争使这部作品达到更高的完善度。 值得一提的是，这本书的完成还有赖于我的朋友们的无私帮助和建设性建议，她们在我编写本书的过程中给予了我极大的支持和帮助。对干她们那愿意陪伴我走过这条艰难旅程的精神，我感慨万分并深感感激。因此，我将这本书献给那些与我并肩作战的朋友们，希望她们能从中得到一些记忆的回馈。 Q 10 你觉得自己是一个怎样性格的人？ Macw: Q11 对刚学习C++的萌新有什么建议？ Macw：多动手、多练习，遇到问题要善于查资料和思考。 Q12 今年的项目收获有哪些？ Macw: 1. 帮上海某知名国际学校搭建社团管理系统。 2. 搭建自动化的学籍管理、LOE 审批系统。 3. 为社区的某一位小伙伴搭建作业展示系统。 收获 keywords：之前一直做的是后端开发，今年为了诸多项目转战全栈开发。在做项目的过程中学习到了很多有价值的前端知识 etc. 同时也结交了很多朋友。 Q13 未来有哪些规划？ Macw：未来打算选择计算机专业，具体学历还没确定（听说现在研究生很普遍）。之后的工作方向可能也会主要集中在计算机领域。 Q14 你希望希望社区有哪些改变？ Macw：我希望社区能够增加社区志愿管理者、题解审核功能，并允许用户投稿自己的题目。投稿题目在审核通过后可以加入主题库（对投稿用户的段位有要求）。目前看来 ACGO 的题解区有些 “乱糟糟” 的，从一个外人的角度出发，根本没有办法在数百篇题解中找到能用的。 与此同时，鉴于 ACGO 目前的用户群体的程序设计能力有了一个大的提升，可以考虑在后续增加团队公开赛供社区内的所有用户参加。 顺便一提，我真的很期待着小鱼的新 OJ 的上线。 群里还有人跟我提及到 PMS 的事情，PMS 和 ACGO 题库编号的不一致性（历史遗留问题）也比较令人头疼，希望 ACGO 将来可以有自己的题库（或许重构 PMS 是一个更好的选择）。 > 一些话 Macw真的太优秀啦，回顾过去一年，Macw就像完全是在为爱发电。他特别热心地积极参与到社区论坛当中，不管大家提出什么样的疑问，他都耐心细致地答疑解惑。 在这一年里，Macw积极参与社区论坛、答疑解惑，被官方认证为ACGO的“饲养员”。他不仅举办了多场比赛，还深度参与了多项出题和验题工作，翻译了许多Codeforces的题目。在社区里，他几乎是“秒回”式的解答者，同时也在各个方面默默维护着社区的稳定运行。 今年暑假，他更是凭借着自己的实力和认真负责的态度，受邀担任了集训营的副讲师呢。在这个岗位上，他依然保持着一贯的严谨作风，一丝不苟地完成每一项讲师任务，给参与集训的同学们带来了满满的收获。 希望在未来的日子里，Macw同学能够在自己所热爱的道路上越走越顺，相信他一定会绽放出更加耀眼的光芒的！

第一次写欢乐赛全题解，请多谅解！！！（主要是太菜AK不了） T1 题目 直接输出即可，但要注意转义符‘\’不能直接输出，应加上‘\’； Python题解 C++题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 题目 利用求和公式可以得到1到n的和为n*(n+1)/2，依次输出； （别忘了不开long long见祖宗） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 题目 遍历字符串，依次记录a,e,i,o,u的次数，再分别乘以各自的W并相加即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 题目 （关于这题用了我7遍提交记录这件事，注意平方优化） 先算出数组中各数的因子数量，再对因子数量进行排序，从大到小相加直到 大于等于m，输出数量即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 题目 遍历数组，先记录下标为奇数和偶数对应的元素的和，比较是否相等； 再遍历数组，判断是否全部A[i]=A[n−i+1]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 题目 看到这恐怖的数据范围，一定需要找规律。先对个位数进行特判，直接输出。 再观察，可以看出只有全部由9构成，字典序才能最大。因此判断，如除个位以外都为9， 直接输出，其余输出（位数-1）遍9. ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点个赞吧，谢谢！！！

第一题.A33695.换行 回到题目 这道题需要输出\n，那我们可以把\和n分开输出。 我们还可以直接输出\n 第二题.A33696.求和 回到题目 这道题只需要用等差数列求和公式(1+n)*n/2，需要注意的是和有可能大于int变量的范围，所以要定义成long long类型。 第三题.A33697.权重 回到题目 这道题要在字符串中找到相应字符a,e,i,o,u的出现次数并乘以他们的权值，最后把这些结果相加并输出。这里每一个字符的权值的最大值是两倍的int类型的范围，所以变量要定义成long long类型的。 第四题.A33698.因子 回到题目 这道题要把每一个数的因子个数统计出来并排序，先判断最多的一个数的因子个数是否大于等于m，不满足就从大到小把每个数的因子个数相加并判断是否大于等于m，成立就直接输出。 第五题.A33699.美丽数组 回到题目 这道题只需要判断每一个数组是否满足美丽数组的条件，可以定义两个函数来实现。 第六题.A33700.字典序问题 回答题目 这道题只要找到一个除最后一位外都是9且小于等于字符串n的字符串，再在字符串的末尾根据情况加上可以加上的最大数。

温馨提示：由于考试时懒得写，所以代码就不给了. T1 签到题，输出 \n 即可.注意 "\" 是转义字符，输出代码应为 cout << "\\n"; 或 cout << R"(\n)"; T2 经典高斯求和题目，解法如下： 1+2+3+4+...+(n−1)+n1+2+3+4+...+(n-1)+n1+2+3+4+...+(n−1)+n =(1+n)+[2+(n−1)]+[3+(n−2)]+...=(1+n)+[2+(n-1)]+[3+(n-2)]+...=(1+n)+[2+(n−1)]+[3+(n−2)]+... 如果 nnn 为奇数，还得加上 n+12\frac{n+1}22n+1 . 所以答案为 n(n+1)2\dfrac{n(n+1)}22n(n+1) . 当然也可以用递归分治实现 T3 按题意模拟即可. 1.求出 a,e,i,o,ua,e,i,o,ua,e,i,o,u 在字符串中出现的次数. 2.分别乘以对应的权值，相加. T4 贪心，首先求出每个数的质因子数，往质因子数多的数挑，直到大于 mmm. T5 小模拟，分别判断奇数下标之和是否等于偶数下标，和是否回文. T6 在 1∼45141\sim 45141∼4514 中 999999999 的字典序最大. 在 1∼99891\sim 99891∼9989 中 999999999 的字典序最大. 在 1∼99901\sim 99901∼9990 中 999099909990 的字典序最大. 在 1∼99911\sim 99911∼9991 中 999199919991 的字典序最大. 所以如果 nnn 除了个位的所有位均为 999 则其中最大的是 nnn，否则就是 9999...9999...9999...（nnn 的位数减一位）

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

> 对于任何问题，可以在评论区发布意见或建议，也可以在 ACGO 官方社区找我沟通。 为什么要写题解？ 首先要清楚知道一点，写题解不仅是帮助别人在做题遇到困难时指明方向，更是提升自己的最快途径。经常有人问我：“如何提升自己的程序设计能力”。我都会回答：“写题解”。 写题解可以帮助你彻底掌握某一个知识点。无论一道题目是否是你独立写出来的，你都应该去尝试写题解。对于许多人来说，他们往往在不会写题目的时候就打开题解区查看别人的代码，并照着别人的样子把代码写出来。然而，他们也许只是模棱两可地了解了的做题的大致思路，但并没有彻彻底底地钻研算法每一步的机制。这种现象的一个显著原因是大部分人可能并不知道自己的弱点。对于这一群人来说，写题解能帮助他们快速地查漏补缺，他们可以在写题解中不断问自己问题 - “为什么这里要这么写？”。 而如果你是依靠着自己独立 AC 题目的，那么写题解可以帮助你在做题后重新梳理自己之前的做题思路，加深自己对某一个知识点的理解和记忆。 不知道大家有没有听说过”费曼“这个人，他是20世纪最杰出的科学家之一。“费曼学习法”是他索提出的一个快速提升自己的方法，“费曼学习法”通过以教为学的方式来深入理解和记忆知识。写题解也正是费曼学习法的其中一种应用。具体地，费曼学习法的基本步骤如下： 1. 选择一个概念：选择你想要学习的概念或主题。 2. 解释给别人听：以你所理解的方式向别人解释这个概念，可以是朋友、同学，甚至是一张白纸。通过尽可能简单和清晰地解释，来确保你真正理解了这个概念。 3. 找出你的理解中的不足：当你尝试向别人解释时，可能会发现你对某些方面的理解并不清晰或不完整。这时，回到学习材料中，重新学习并填补这些空白。 4. 简化和回顾：尝试以更简单的方式解释这个概念，确保你可以用简单的语言和概念来说明。然后，定期回顾你所学习的内容，以加深记忆和理解。 这种方法的核心思想是通过将知识表达出来，来检查自己对知识的理解程度。费曼学习法强调了深度理解和简化概念的重要性，以及通过教学他人来加深自己的理解。 什么是一篇好题解？ 个人认为，一篇好的题解应该尽量包含以下几点要素： 1. 在讲解题目之前先对题干信息作出解读。 2. 题解需要包含主要的做题思路，需要使用到的算法或数据结构。 3. 排版美观，数学公式需要使用 LaTeX\LaTeXLATE X 语法，代码片段需要使用 Markdown 语法。 4. 题解内容可以借鉴他人的想法，但不可以无故抄袭，需要尊重原创。 相反，这些情况都是不好的题解： 1. 没有给出任何的做题思路，只提供代码。 2. 提供的代码无法通过题目所有测试点。 3. 题解内容涉及大篇幅抄袭且并没有经过原作者同意。 4. 排版混乱，使得普通用户在阅读过程中产生理解障碍。 与此同时，一篇好的、完整的题解应该包括以下几部分： 1. 题干信息解读 2. 整体做题思路 3. 题目中的难点和注意事项 4. 提供可通过所有测试点的标准程序 5. 分析代码的时间复杂度和空间复杂度 题干信息解读 题干信息解读并不是单纯把题干复制粘贴下来，你应该使用简洁且浓缩的语言讲题目的中心思想传递到位即可。其中，你可能需要将题干背景抽象化，并将一些无意义的内容删减。 复述题干信息的目的是为了让读者一眼就可以知道题目的大致意思和程序目标。 例如题目 股票购买方案数，在撰写题解的时候你可以直接向用户说明：“本题是一个‘逆序对’的模版题，本质上就是求解在给定数组中‘正序对’的数量。”。 整体做题思路 在这一部分，你需要告诉用户本题的正确做法和思路。你应该阐述算法的具体过程和一些可能在编写程序中遇到的错误。 对于某些算法题目，可能需要使用各种类型的数据结构作为辅助（例如单调栈、线段树、ST表等），你可以向用户阐述所使用的数据结构的优点和缺点（例如树状数组，优点是快速进行单点修改和区间查询操作...）。 对于部分高难度算法问题，如果需要前置条件，应当附上外链帮助用户更好地理解。例如题目 眼红的同学，在做题之前的前置知识为 1. 使用树状数组求逆序对。 2. 熟练使用归并排序等分治算法。 提供标准程序 请注意：在提供 AC 代码的时候，请务必使用 Markdown 格式的多行代码语法来包裹代码块。 为了方便读者更好的理解代码中每一部分的内容，在提供正确代码的时候需要尽量对每一个代码块做好充足的注释。与此同时，请不要为了减少代码的行数而无意义的压缩代码，请使用适当的缩进和大括号保持代码的可读性和美观性。 与此同时，对于部分题目而言，可能使用非优秀的解法可以拿到部分分数，那么你在撰写题解思路的时候可以适当给出可以拿到部分分的代码。 例如题目 寻找特别之数，正确算法应该是使用数位DP思想暴力按位枚举，但是使用暴力算法可以拿到部分分。在撰写题解时可以适当给出思路。 时间与空间复杂度 在题解的最后，你应该给出最终程序的时间复杂度以验证程序可以在规定时间和规定数据规模下输出正确结果。分析题目的数据规模可以帮助 OIer 反推出题目可能需要使用的算法（哈哈哈，投机取巧）。 可以参考题目 来自领导的烦恼 中的时间复杂度分析。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后，祝大家多写题解，丰富 ACGO 社区！RP++。

8月13日： my name is 米方蕊，舍友们都叫我米哈游。。。。。 我们宿舍是214，就我一个不玩原神。。。。。。。。 **但我们爱phigros ** **有空的找我玩。（女生们） ** 学习： 今天学了贪心吧（应该是） 掌握的好像应该大概还行 今天我的舍友们都迷上了写规则怪谈。（受启发于six） 看蓝色监狱、天官赐福的快来找我！！！！！ 无聊推荐：1.（女）来214，一般人挺多。 2.看six（ACGO）的诡怪 ，超推荐！！！ 3.酒店前台可以买饮料，但要是想买到，就别说你是小码王的。 如果他问了就说你是营地的 or 你是大地之野的。 今日题号及代码： A22674.[USACO1.3] 混合牛奶 Mixing Milk #include<bits/stdc++.h> using namespace std; struct fa{ int p,num; }; int cmp(fa a,fa b){ return a.p<b.p; }int main(){ int n,m,ans=0; fa a[5050]; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i].p>>a[i].num; }sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++){ if(a[i].num>=n){ ans+=na[i].p; break; }else{ ans+=a[i].pa[i].num; n-=a[i].num; }} cout<<ans; return 0;} 答案仅供参考 T20341.凑零钱 #include<bits/stdc++.h> using namespace std; int a[4000050]={0}; int main(){ int n,ans=0; cin>>n; ans+=n/10; n=n%10; ans+=n/5; ans+=n%5; cout<<ans; return 0; } 答案仅供参考 就这俩吧，其他的太简单了（这俩也是）。 8月14日： 今日一切安好，大家都还健在。 参加了几个比赛。挺好。 今天有件事: 老师杀虫。 天气逐渐转凉，雨渐渐的下大了。蚊香又停止了它每日3秒的工作。一直小指大的蚂蝗悄无声息的飞进了寝室。 “啊！！你..你们看！那是什么？”舍友大声喊道。 “哎呀小小蚂蝗，又不咬人？只是有剧毒罢了”我云淡风轻的讲着。 之间2名舍友风似的爬上了商铺。谁料那蚂蝗也以惊人的速度飞上了屋顶。眼见蚂蝗近在咫尺，我动作迅速的绕过了2个行李箱又身手矫健的跨过了垃圾桶。就在这千钧一发之际，我“啪”一声吧窗户关上又打开了。蚂蝗害怕的躲开了。我的舍友们“砰”一下跳下了床。 这时我们终于想到了一件好东西----老师！！！！ 我们叫来了老师。三名强大的老师齐聚一堂，蚂蝗感到了极强的压迫，但它仍不服输。只见老师抄起来手边的《算法竞赛》 拍向了蚂蝗，蚂蝗牺牲了。 先看下我今天的食谱吧： 早:包子2，馒头1，榨菜1,牛奶3，稀饭2，蒸饺5，烧卖*1。 早饭挺好吃，不然我也不会吃这么多。牛奶实在是太好喝了（我班主任从山下带的2箱都喝完了，才3天） 午：卤鸡，排骨汤，蒜蓉空心菜？等 也挺好吃，就是那汤吧，闻着羊味吃着牛味问了一下是猪肉。。。。 晚：炸虾，青菜，炖汤，牛排骨！！ 巨好吃！！！ 好了又到了无聊的代码环节： 这些题号明天说，找不到了。。。 #include<bits/stdc++.h> using namespace std; int main(){ string a; getline(cin,a); cout<<a; } 第二个了 #include<bits/stdc++.h> using namespace std; int a[10000]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int x,y,h; cin>>x>>y>>h; for(int i=x;i<=y;i++){ a[i]+=h; } for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } } number three #include<bits/stdc++.h> using namespace std; int a[10000]; int main(){ int n; cin>>n; if(n<=5){ cout<<n+2; }else if(n==6){ cout<<1; }else{ cout<<2; } } 四是完形填空 #include <iostream> using namespace std; int a[100010]; int main() { int n,m,x; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; while(m--){ cin >> x; int flag = 0; /补全以下代码,下划线记得完全删除哦/ int l = 1 , r = n ; while (l<r) { int mid = (l+r)/2 ; if( a[mid]>=x ) r=mid ; else l = mid+1; } if(a[l] != x) cout << -1<< endl; else cout << l << endl; } return 0; } 这个五简单 #include<bits/stdc++.h> using namespace std; int a[10000]; int main(){ int n; cin>>n; int ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]>=100&&a[i]<1000){ ans++; } } cout<<ans; } 好了再见。 8月15日： 我们还活着。嘿嘿，给大家推荐个小说，作者ACGO名：周籍。帮我去评论区催催更呗。 第一章：https://www.acgo.cn/discuss/rest/23707 第二章：https://www.acgo.cn/discuss/rest/24168 第三章：https://www.acgo.cn/discuss/rest/24366 更到第六章了。 今天早饭还是挺好？ 中午吃了巨多鸡米花。 晚上也挺好。 考试只能说摆烂了。 今天学了栈和队列但考试和这个没有任何关系..... 分享一下吧： A70 #include <cstdio> int n, a[30]; int main(){ scanf("%d", &n); a[0] = 1, a[1] = 1; for(int i=2; i<=n; i++){ for(int j=0; j<i; j++){ a[i] += a[j] * a[i-j-1]; } } printf("%d", a[n]); return 0; } 就这样吧，再见。 8月17日： 精神逐渐发疯 精神值：5 下山去医院领了复活卡 我复活了 据说今天学了深搜 就这样吧，服了 8月18日： 一切安好，病好多了。 学了广搜 代码见下： #include<bits/stdc++.h> using namespace std; long long a[1000010]={0},s[1000010]={0}; int main(){ long long n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int i=1;i<=k;i++){ int l,r; cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; } 这是前缀和

AC君表示写的可以点个赞： 也是会实时更新的 目录： 1.开启与关闭文件 2.时间复杂度与空间复杂度 3.埃式筛与线性筛 4.vector动态数组 5.进制转换 6.如何更安全的定义变量 7.原码反码补码 > 1.开启与关闭文件 > 这个代码十分重要，到时候你考CSP-S/J或者其他信奥赛时都会用到，已这题为例： > 原题链接 > 2.时间复杂度与空间复杂度 > 相信每个小码王集训营学员对这俩玩意毫不陌生，因为第一天学的就是这玩意 > 时间复杂度其实是计算或衡量程序或算法执行效率或者执行速度；通常是以大O记法（O(时间)）大O记法规则是：O(1)代表所有时间复杂度；修改后时间频率只保留最高价；若最高阶系数存在且不是1就删去该常数（如果看不懂就主动找老师重新学一遍再来看） > 空间复杂度不太经常用到，一般因为在比赛中一个正常的C++程序内存为128MB，十分充裕，除非你是直接While(true)否则根本不会超时一般就O(1)或O(n)； > 怕你看不懂所以上时间复杂度表格（别问我为啥不上空间复杂度） 注：每10810^{8}108为1秒，也就是说，你在比赛中C++程序不能超过10810^{8}108，否则就会有可能TLE（超时），如果是1秒以上当我没说 大O记法 时间 例子 O(1) 常数时间 1 O(logn) 对数时间 10 O(n) 线性时间 1024 O(nlogn) 对数线性时间 1024x10 O(n2n^{2}n2) 二次时间 102421024^{2}10242 O(n3n^{3}n3) 三次时间 2302^{30}230 O(2n2^{n}2n) 指数时间 210242^{1024}21024 O(n!) 阶乘时间 1x2x3x……x1024 > 3.埃式筛 > 这玩意想必是每个参加过X-02的学员的噩梦，因为埃式筛是要求背下来的，且会进行默写的......（如果是X-02以外的或是就让看看就行的就当我没说） > 埃式筛说白了就是求质数用的，思想是把不大于根号n的所有表数的倍数全部剔除（还是老样子，看不懂的问授课老师，质数不知道的问小学数学老师，根号不知道的问初中数学老师） > 所以代码长啥样？ > 长这样： 当然，你喜欢暴力解决的话就长这样： 线性筛代码： > 4.vector > 注意了，某些卡莫纳人，vector是一个动态数组，不是鼠鼠修脚枪。 > vector其实是一个动态数组，可以根据需要，无限制的动态扩容，比普通数组好用，这么好用的东西需要一个头文件#include<vector>。 > 那么vector如何定义？用手定义用这串代码vector<类型名> 动态数组名，当然，vector支持整型、字符型、结构体。当然，你也可以定义二维动态数组vecort<vector<类型名>> 动态数组名。 > vector定义完了，咋访问？那肯定用下标啊，下标范围是0 - v.size() - 1，v.size是啥？看下面STL代码。 > vector也可以进行构造函数（不知道构造函数啥意思的问老师）就这些： > vector <元素类型> v(n) <- 有n个元素的vector，初始化为0 > vector <元素类型> v(n, value) <- 有n个元素的vector，元素为value > vector <元素类型> v(other) <- 从other的vector复制元素 > 既然都是数组，那肯定都可以排序，咋排序呢？我也懒得打了看代码吧 > sort(a.begin(), a.end(), cmp); > 当然，vector的STL代码，不一一写了，看下面： STL代码 解释 v.push(插入元素) 将元素插入到动态数组中 v.size() 返回动态数组元素个数 v.front() 返回动态数组第一个元素 v.back() 返回动态数组最后一个元素 v.resize() 调整大小为n，如果n大于当前大小，新元素就初始化 > 5.前缀与差分，本知识点可以正常呼吸。 > 前缀，就是前缀和，前缀和说白了我白说了就是在一个数组中求下标L~R的区间和，其实就是计算区间和的优化，就只需把两行代码理解，记住就行了： > pre[i] = pre[i - 1] + a[i]; // 生成前缀和数组 > sum = pre[r] - pre[l - 1]; // 求区间和 可以参考一下这道题进行练习 > 差分，就是差分也和好理解，就是前缀和的逆运算。在一维数组差分问题中，差分值即是相邻元素的差值，也是记住这两行代码就行： > d[i] = a[i] - a[i - 1]; // 生成差分数组 > c + d[l] += c; d[r + 1] -= c // 针对区间[l, r]每个元素同时 > 带入到代码中就是输入数组的同时生成前缀/差分数组；在输入l和r的元素时进行计算并输出即可 > 5.进制转换，CSP-J/S初赛必考，建议第一次考CSP的看看，本知识均为小码王X02集训营笔记 > 首先，在数学中，有常用的十进制、二进制、八进制、十六进制（其实还有其他进制，以上是以常用进制），那么知道中文，那英文是啥？看下面： 进制 英文 简写 二进制 binary BIN 八进制 octal OCT 十进制 decimal DEC 十六进制 hexadecimal HEX > K~挠，知道了每个进制的英文和英文缩写，那么如何转换捏？ > 十进制转N进制，是： > > 图画的可能比较飘逸，电脑绘画，请谅解！ > N进制转十进制是（以二进制转10进制为例子）： > （11000） = 141^{4}14 + 131^{3}13 + 020^{2}02 + 010^{1}01 + 000^{0}00 > 算法：第位权值为ni−1n^{i - 1}ni−1然后相加 > 小数算法也是一样 > 还有一种是适用于二进制： > > 最后就潦草的展示十六进制的数字为结尾： 十六进制数 表示十进制数 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 A 10 B 11 C 12 D 13 E 14 F 15 10 16 (指进一位) > 6.关于定义变量的问题，K，可能有些人就问定义变量会有问题的danm，实际上问题百出，我就问是不是有人这么定义变量过： > > 或者这样： > > 这样定义过的在评论区发"1"。如果你这样定义过，恭喜你，废了 > 因为上一个定义变量n还好，因为有输入，但是是第二个这种没有输入的定义且没有赋值的可能就会直接输出一些奇怪的东西，但是有些人这样写N年都没事因此就不信，但是直接不输入不赋值就直接用sum变量会有可能不是0！！！，因为本人在集训营就吃过这样的亏，其实出现这种情况是因为，C++语言规定，在main函数中定义一个不输入不赋值的变量就会随机生成一个值，所以本人建议这么定义： > > 或者这样： > 总之，这两种定义方式肯定不会错，因为第一种在C++语言中规定：main函数外的变量均默认为0所以累加器建议定义在main函数外；第二种我就不用多说了，定义在main函数里，但是赋值了。 > 7.原码反码补码，K，又是个“可爱”的初赛知识，这玩意听集训营老师说这玩意经常考，确实，今年CSP考了，但好像做错了反正，原码反码补码统称为计算机储存一个具体数字编码方式，当然，数值在计算机中以补码形式储存其中：1为负、0为正（初中生别告诉我没学负数）。so其实上面说的是三个码大体定义，而具体的则是： > 原码：机器数表示数的形式为原码，一般以符号位（就是二进制设计时，第一位表示符号就是上面说的1为负、0为正）数值来表示。（范围：+127~-127） > 反码：（到这里可能需要些初中知识，小学生如果承受不了的可以问问你的树穴老师，然后再看）首先，在正数中的反码跟原码没区别；但是，负数的反码就是除符号位外，其他的取反就是负数反码。 > 补码：同样，正数补码跟原码没区别；就是负数的补码是反码+1就行了。 > 当然，通常这三个码二进制位数顶多就8位，因此范围是：-128~127 > K，这个知识点告诉了我们什么？在学校不要欠老斯作业，否则就要+1告诉我们原码反码补码学完了。真的没了。 有建议和补充在评论区说，不用憋着，对了 所以 报集训营的在评论区发个“J”我康康有多少怨种爱好学的人。 学废了吗？ 学会了就切回团队

X01时： 现在： 6题20次？ 集训营同学：

**数学月考差一点点就120了； 啊啊啊就差一份啊！！！！

对于每个价格，计算它作为最大值和最小值的贡献。 使用两个单调栈分别记录价格作为最大值和最小值时的左右边界。 对于每个价格，计算它作为最大值和最小值时的贡献并累加到总波幅之和中。 时间复杂度：O(N)，因为每个价格只会进出单调栈一次。 空间复杂度：O(N)，用于存储单调栈和边界信息。

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

dp0,i,dp1,idp_{0,i},dp_{1,i}dp0,i ,dp1,i 分别表示第 iii 种状态的重量、最大价值 什么？你问这个方法有什么优点？ 好吧确实没有 时间复杂度 O(2n×n)O(2^n\times n)O(2n×n)，空间复杂度 O(2n)O(2^n)O(2n) 都不如深搜（

前言 > 像使用 std::vector 一样，使用「线段树」。 本文将介绍 AC(AtCoder) Library 中提供的 segtree 模版。 本文最后提供的 Segtree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。 同时由于本文的线段树的结构与常规的使用递归实现的线段树，存在很大的不同，本文介绍的线段树「无递归」，效率很高。 下文在介绍操作的使用方式的同时将会逐步剖析其源码的实现。 阅读代码实现部分需要读者对「面向对象」，「模板」，「函数指针」有一定的了解，并且需要一定的数学基础，能够理解 「函数」 和一些「代数」的知识。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 简介 本文将介绍一种高效的支持「单点修改」，「区间查询」以及「二分查找」的线段树。 这是一种用于幺半群 (S,⋅:S×S→S,e∈S)(S, \cdot: S \times S \to S, e \in S)(S,⋅:S×S→S,e∈S) 的数据结构，即满足以下性质的代数结构： * 结合律：对于所有 a,b,c∈Sa, b, c \in Sa,b,c∈S，(a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c)(a⋅b)⋅c=a⋅(b⋅c) * 存在单位元 eee：使得对于所有 a∈Sa \in Sa∈S，a⋅e=e⋅a=aa \cdot e = e \cdot a = aa⋅e=e⋅a=a 给定一个长度为 NNN 的数组 AAA，它可以在 O(log⁡N)O(\log N)O(logN) 的时间内处理以下操作。 * 更新一个元素的值 * 计算给定区间内所有元素的「积」 为了方便描述，在本文中我们假设 op 和 e 的时间复杂度为 常数。如果这些操作的时间复杂度为 O(T)\mathrm{O}(T)O(T)，那么本文中所有操作的时间复杂度将乘以 O(T)\mathrm{O}(T)O(T)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 操作 1. 构造函数 * (1)：它会创建一个长度为 n 的数组 a，所有元素都被初始化为 e()。 * (2)：它会创建一个长度为 n = v.size() 的数组 a，初始化为 v。 应定义以下内容。 * 存储的元素类型 T * 二元操作 T op(T a, T b) * 单位元 T e() 限制： * 0≤n≤1080 \le n \le 10^80≤n≤108 复杂度： * O(n)\mathrm{O}(n)O(n) 例如，对于一个值域不超过 10910^9109 的，总共有 101010 个元素的「区间最小值查询」的问题，我们可以用以下方式来定义： 原理与代码实现 本文介绍的线段树，结构基于「完全二叉树」，所有操作不采用递归实现。 令 n\tt{n}n 为线段树存储的元素的大小，size\tt{size}size 为 bit_ceil(n) 即不小于 nnn 的最小的 222 的非负整数次幂。 我们这里令 n=11\tt{n = 11}n=11，那么 size=16\tt{size = 16}size=16。创建一个大小为 size×2\tt{size \times 2}size×2 的数组 d\tt{d}d，我们将真实的数组 a\tt{a}a 中的数据存储在 d16,d17,⋯d26\tt{d_{16}, d_{17}, \cdots d_{26}}d16 ,d17 ,⋯d26 ，如下图所示。 对于数组 d\tt{d}d 保存以下数据： 1. d0\tt{d_0}d0 保存数据为单位元 eee。 2. 对于 1≤i<size\tt{1 \le i \lt size}1≤i<size 每个 di\tt{d_i}di 维护 op(d2i,d2i+1)\tt{op(d_{2i}, d_{2i + 1})}op(d2i ,d2i+1 )。 3. 对于 size≤i<size+n\tt{size \le i \lt size + n}size≤i<size+n 每个 di\tt{d_i}di 保存原数组中的元素 a0,a1,⋯ ,an−1\tt{a_0, a_1, \cdots, a_{n - 1}}a0 ,a1 ,⋯,an−1 。 4. 对于 size+n≤i<size×2\tt{size + n \le i \lt size \times 2}size+n≤i<size×2 每个 di\tt{d_i}di 保存数据为单位元 eee。 据此我们可以按照以下方式实现构造函数： 其中 update() 操作实现为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. SET 将 a[p] 赋值为 xxx。 限制： * 0≤p<n0 \le p \lt n0≤p<n 复杂度： * O(log⁡n)\mathrm{O}(\log{n})O(logn)。 原理与代码实现 由于上面完全二叉树的特殊性质，我们可以自底向上更新数组 d\tt{d}d。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. GET 返回 a[p]。 限制： * 0≤p<n0 \le p \lt n0≤p<n 复杂度： * O(1)\mathrm{O}(1)O(1)。 原理与代码实现 直接访问 d[p + size] 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. PROD 返回数组区间 [l,r)[l, r)[l,r) 的「积」，即 op(a[l], ..., a[r - 1])，假定其满足幺半群的性质。 若 l=rl = rl=r，则返回 e()。 限制：0≤l≤r≤n0 \le l \le r \le n0≤l≤r≤n 复杂度：O(log⁡n)\mathrm{O}(\log{n})O(logn)。 原理与代码实现 根据以上线段树实现，对于 d\tt{d}d 数组，我们有以下性质。 1. 数组中下标为偶数的元素必定为左儿子； 2. 除根节点以外，数组中下标为奇数的元素必定为右儿子； 3. di=op(d2i,d2i+1), 1≤i<size\tt{d_i = op(d_{2i}, d_{2i + 1}),\ 1 \le i \lt size}di =op(d2i ,d2i+1 ), 1≤i<size。 我们可以将查询拆分成若干个 di\tt{d_i}di ，我们取这些 di\tt{d_i}di 的「积」即可。 那么令 l\tt{l}l 为查询区间左端点， r\tt{r}r 为查询区间的右端点，我们以完全二叉树的视角考虑 d\tt{d}d 数组，l,r\tt{l, r}l,r 在树中对应的真实下标为 l+size,r+size\tt{l + size, r + size}l+size,r+size，但不妨我们分别将其记为 l,r\tt{l, r}l,r，称为「左」和「右」。 以树的深度考虑，从底到顶，不断缩小 l\tt{l}l 和 r\tt{r}r 的距离，不同深度选择相应的 did_idi ，直到 l≥r\tt{l \ge r}l≥r。 对于「左」，若 l\tt{l}l 为偶数，那么显然 dl\tt{d_l}dl 和 dl+1\tt{d_{l + 1}}dl+1 都处于区间查询范围内，那么我们便不需要取 dl\tt{d_l}dl ，而是直接跳到其父亲 dl2\tt{d_{\frac{l}{2}}}d2l ；若 l\tt{l}l 为奇数，那么显然 dl−1\tt{d_{l - 1}}dl−1 已经取过，或者不在范围内，我们直接取 dl\tt{d_{l}}dl ，同时为了避免重复取值，我们可以令 l←l+1l \gets l + 1l←l+1 从而使其跳过原来的父亲 dl2\tt{d_{\frac{l}{2}}}d2l 。 对于「右」，若 r\tt{r}r 为偶数，那么显然 dr−2\tt{d_{r - 2}}dr−2 和 dr−1\tt{d_{r - 1}}dr−1 都处于区间查询范围内，那么我们便不需要取 dr−1\tt{d_{r - 1}}dr−1 ，而是直接跳到其父亲 dr2\tt{d_{\frac{r}{2}}}d2r ；若 r\tt{r}r 为奇数，那么显然 dr\tt{d_r}dr 已经取过，或者不在范围内，我们直接取 dr−1\tt{d_{r - 1}}dr−1 ，同时为了避免重复取值，我们可以令 r←r−1r \gets r - 1r←r−1 从而使其跳过原来的父亲 dr2\tt{d_{\frac{r}{2}}}d2r 。 「左」和「右」每次检查完当前层的 did_idi 是否选取之后，都跳到下一层。 因此我们可以按照以下步骤来选择数组 d\tt{d}d 中的一些元素并求「积」： 1. 令当前查询区间对应的左边界为 l\tt{l}l，右边界为 r\tt{r}r，所取结果为 [l,r)\tt{[l, r)}[l,r) 内的「积」。 2. 令 l←l+size, r←r+size\tt{l \gets l + size,\ r \gets r + size}l←l+size, r←r+size。 3. 若 l\tt{l}l 为奇数则取 dl\tt{d_l}dl ，并同时另 l←l−1\tt{l \gets l - 1}l←l−1。 4. 若 r\tt{r}r 为奇数则取 dr−1\tt{d_{r - 1}}dr−1 ，并同时另 r←r−1\tt{r \gets r - 1}r←r−1。 5. 令 l←l2, r←r2\tt{l \gets \frac{l}{2},\ r \gets \frac{r}{2}}l←2l , r←2r 。 6. 重复执行步骤 3,4,53, 4, 53,4,5 直到 l≥r\tt{l \ge r}l≥r。 我们以上述 n=11\tt{n = 11}n=11 的数组 $\tt{a} $为例，若查询 [2,9)[2, 9)[2,9) 内所有元素的积。则在数组 d\tt{d}d 中选取的元素有 d9,d5,d24\tt{d_9, d_5, d_{24}}d9 ,d5 ,d24 ；我们只需要求 op(d[9], d[5], d[24]) 的结果即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5. ALL_PROD 返回数组中所有元素的「积」，即 op(a[0], ..., a[n - 1])，假定其满足幺半群的性质。 若 n=0n = 0n=0，返回 e()。 复杂度：O(1)\mathrm{O}(1)O(1)。 原理与代码实现 直接访问 d[1] 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6. MAX_RIGHT * (1)：在线段树上执行二分查找需要定义函数 bool f(T x)。 * (2)：需定义一个以 T 为参数，返回类型为 bool 的函数对象。 它返回一个满足以下两个条件的下标 r： * r = l 或 f(op(a[l], a[l + 1], ..., a[r - 1])) = true * r = n 或 f(op(a[l], a[l + 1], ..., a[r])) = false 如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最大的 r。 限制： * 如果以相同的参数调用 f，其应该返回相同的值，即 f 无副作用。 * f(e()) = true * 0≤l≤n0 \le l \le n0≤l≤n 复杂度： * O(log⁡n)\mathrm{O}(\log{n})O(logn) 原理与代码实现 我们令 sm←e\tt{sm \gets e}sm←e 存储从 l\tt{l}l 开始从左到右，统计的所有元素的「积」。 与区间查询类似，我们利用完全二叉树的性质，当 l\tt{l}l 为左儿子时，让其不断向上。 若当前对应的 dl\tt{d_{l}}dl 若满足 f(op(sm,di))=False\tt{f(op(sm, d_i)) = False}f(op(sm,di ))=False，则向下查询，否则令 sm←op(sm,dl), l←l+1\tt{sm \gets op(sm, d_l),\ l \gets l + 1}sm←op(sm,dl ), l←l+1，即跳过其父亲，继续向上查询，直到某一层的最后一个元素为止； 向下查询的过程中，先查询左儿子 dl×2\tt{d_{l \times 2}}dl×2 是否满足 f(op(sm,dl×2))=True\tt{f(op(sm, d_{l \times 2})) = True}f(op(sm,dl×2 ))=True，若为真，同样取左儿子的值，即 sm←op(sm,dl×2)\tt{sm \gets op(sm, d_{l \times 2})}sm←op(sm,dl×2 )，再向下查找， 否则不取左儿子的值；重复执行，直到树的最后一层结束。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 7. MIN_LEFT 它返回一个满足以下两个条件的下标 l： * l = r 或 f(op(a[l], a[l + 1], ..., a[r - 1])) = true * l = 0 或 f(op(a[l - 1], a[l], ..., a[r - 1])) = false 如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最小的 l。 限制： * 如果以相同的参数调用 f，其应该返回相同的值，即 f 无副作用。 * f(e()) = true * 0≤r≤n0 \le r \le n0≤r≤n 复杂度： * O(log⁡n)\mathrm{O}(\log{n})O(logn) 原理与代码实现 与 max_right 操作类似，先令 r←r−1\tt{r \gets r - 1}r←r−1，然后令 sm←e\tt{sm \gets e}sm←e 存储从 r\tt{r}r 开始从右到左，统计的所有元素的「积」。 再利用完全二叉树的性质，当 r\tt{r}r 为右儿子时且不为根时，让其不断向上。 若当前对应的 dr\tt{d_{r}}dr 满足 f(op(dr,sm))=False\tt{f(op(d_r, sm)) = False}f(op(dr ,sm))=False，则向下查询，否则令 sm←op(dr,sm)\tt{sm \gets op(d_r, sm)}sm←op(dr ,sm)，跳过其父亲，继续向上查询，直到某一层的第一个元素为止； 向下查询的过程中，先查询右儿子 dr×2+1\tt{d_{r \times 2 + 1}}dr×2+1 是否满足 f(op(dr×2+1,sm))=True\tt{f(op(d_{r \times 2 + 1}, sm)) = True}f(op(dr×2+1 ,sm))=True，若为真，同样取右儿子的值，即 sm←op(dr×2+1,sm)\tt{sm \gets op(d_{r \times 2 + 1}, sm)}sm←op(dr×2+1 ,sm)，再向下查找， 否则不取右儿子的值；重复执行，直到树的最后一层结束。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ SEGTREE.CPP

如标题

动态规划大题解来啦！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言： 动态规划（dynamic programing（简称DP））通过记忆化的方式弥补了暴力搜索（如BFS，DFS等）重复计算某些区间的缺点。有的题目用动规甚至可以把时间复杂度从O(2^N) 降维打到O(N^2)。不过同时，这一算法也有一定门槛，是许多C++小白的一生之敌。 近期，我将会分两批，把ACGO官方的动规题单中的题目统一发放题解在一个帖子里面。这次的帖子是动规题单中相对简单的9道题（差不多占题单的50%）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 动规步骤 在正式开始之前，我需要说明做动态规划题目的步骤以及必须确定的及部分： 第一步： 众所周知，动规算法的主心骨是DP数组。但是与递推算法不一样的是，不一定所有的DP数组都自带答案。而如果不知道DP数组的含义而盲目去做只会导致越做越废（比如说那时的我）。所以做动规题目的第一步是确定该怎样定义DP数组 （也就是确定“DP[i][j]” 或 “DP[i]”的含义）。 第二步： 这一步是难倒大部分人的部分，也就是推导动态转移方程。听起来很高深，说白了就是当你有了前几项的答案，如何得出下一步的答案。其实有两种办法。1.（这一种很有用）打表+总结+AC。2.当你牛到了一定程度可以直接推导计算+AC。 第三步： 有的人万事俱备了，但是之后一通乱写，结果全部爆红。原因就是没有初始化好。怎样初始化呢？你可以把自己的大脑想成一个计算机，先自己推一下，把那些无法用转移方程推出来的找出来，它们就是初始化的对象。 第四步： 遍历顺序。这一点也是不可忽略的。比如像01背包和完全背包，遍历顺序完全是相反的（这一点也是和递推很不一样的一点）。具体该怎样要随机应变（反正很重要）。 第五步： 万事俱备，顺水推舟就行。 以上几点可能大家暂时体验不到，现在步入正题。来人！把准备的九道题搬出来，让他们体验一一下具体的五步！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 九道题的题解 1.A7927.兔子数列 本题个人认为反而更像递推，就是一道毫无争议的模板题。DP[n]就是本题答案。而且动态转移方程也告诉我们了。唯一要注意的就是初始化。从道理上来讲，应该初始化DP[1]和DP[2]。 代码如下： 但是，有人过了离开了，有人还在研究。这题还可以只用三个变量解决。具体逻辑大家自己理。 代码： 2.A7928.钞票问题 本题也是动规模板题。相信很多新手都是在这里死磕贪心挂掉的（忽略玩特判的）。动规做法的DP定义也很简单，DP[n]就是答案。但是在动态转移方程上面，就和递推有所不同了。他并不是通过前面一两位来获得后面的答案。这里就要展现记忆化搜索的强大之处了。由于我们是从前往后推的，因此DP数组当前位置的前面的所有位数已经知道了。而只有三种情况达到这个答案：1.i - 1加了一个1元的钞票变成i。2.i - 5加了一个5元的钞票变成i。3.i - 11 加了一个11元的钞票变成i。因此，只需要在DP[i - 1],DP[i - 5]和DP[i - 11]中找到最小值并+1就可以了（记得判边界）。 代码如下： 3.A7929.不同的路径 这题不难，我们需要知道除了上边界以及左边界以外，对于每一个，要么从左边来，要么从上面来。所以DP[i][j] = DP[i - 1][j] + DP[i][j - 1]。对于上边界，只能从左边来；对于左边界，只能从上边来，所以全初始化为1。 代码如下： 4.A627.数字三角形 题单里面没有这题，是我自己补进来的。（当然是因为它很重要）。其实这和上一题是一个循序渐进的过程。上题是求方案数，这题是求最大值（想到Dj了么）。是上方和左上方两个方位，用max来取最值。 代码如下： 5.A7932.数塔升级版 这题和上一题大同小异，二叉改三叉了，最大改成了最小。但是我这题用另外一种方法来解——即用父节点先初始化子节点。看得懂的可以找机会帅一把。 代码如下： 6.A7933.数塔升级版2 这题看起来很难，有的人感觉像是广搜/深搜（结果看了看数据范围直接老实了）。但是我们要有逆向思维，还是从上往下推，具体思路和前两题差不多。只不过找答案的时候记得要在下面中间的格子找。 代码如下： A7931.传球游戏 本体对于新手来说有难度，因为需要开新的一维用来从传一次球推导到传两次球……最后推导到传m次球。初始化DP[1][0]即可，因为一开始的球是在小蛮手里的。 代码如下： 8、9.A7934.最长上升子序列 A7956.导弹拦截 在题单里面有很多与这两题题相似的题，本帖就讲这两个两个，也算是为下篇开了个头。这两道题都是纯纯的模板题，与数塔相似,都使用贪心思想。在求答案方面有所不同，需要每一位都求一下。 代码如下： 导弹拦截： 最长上升子序列： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如果本帖对你有用，请点一个赞，支持一下。 （AC君都点了，你不点一下？） 未完待续……

定理 首先我们先要知道费马小定理。费马小定理很简单，只有一句话： ap−1≡1 ( mod  p)a^{p-1}\equiv1\ (\bmod\ p) ap−1≡1 (mod p) 其中 aaa 是正整数，ppp 是素数，且 aaa 与 ppp 互素。 费马小定理最常用于求模意义下的乘法逆元。模意义下的乘法逆元定义为：如果存在一个整数 a−1a^{-1}a−1，使得 a×a−1≡1 ( mod  p)a\times a^{-1}\equiv1\ (\bmod\ p)a×a−1≡1 (mod p)，则称 a−1a^{-1}a−1 为 aaa 在模 ppp 意义下的逆元。这样在模 ppp 的意义下，÷a\div a÷a 就可以被 ×a−1\times a^{-1}×a−1 所替代，而模意义下的乘法比除法简单很多。所以，学会求逆元是很重要的。 我们发现，根据费马小定理，在 ppp 是素数，且 aaa 与 ppp 互素的情况下，a×a−1≡ap−1 ( mod  p)a\times a^{-1}\equiv a^{p-1}\ (\bmod\ p)a×a−1≡ap−1 (mod p)。变形得：a−1≡ap−2 ( mod  p)a^{-1}\equiv a^{p-2}\ (\bmod\ p)a−1≡ap−2 (mod p)。因此，ap−2mod  pa^{p-2} \mod pap−2modp 就是 aaa 的逆元。这样我们就完成了在 ppp 是素数，且 aaa 与 ppp 互素的情况下的逆元求解。计算时选用快速幂算法，可以实现在 O(log⁡p)O(\log p)O(logp) 的时间复杂度求解逆元，相当高效。 所以来看题吧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 实战 【模板】有理数取余 （你问我为什么不放“模意义下的乘法逆元”模板题？问就是那题卡费马小定理的复杂度，要用线性推逆元。） 首先，这个数据范围就挺吓人的。但是根据模的性质，我们只需要分子分母（即 aaa，bbb）在模 192608171926081719260817 意义下的值。所以可以写一个快读，边读边模就行了。 然后，我们开始思考怎么做这题。发现 abmod  19260817\dfrac ab \mod 19260817ba mod19260817 中，除以 bbb 就相当于乘 bbb 的逆元，即 ab≡a×b−1 ( mod  19260817)\dfrac ab \equiv a\times b^{-1}\ (\bmod\ 19260817)ba ≡a×b−1 (mod 19260817)。注意到 192608171926081719260817 是个素数，所以求逆元只需要用费马小定理就行了。答案即为 a×bp−2mod  19260817a\times b^{p-2}\mod 19260817a×bp−2mod19260817。直接使用快速幂，时间复杂度 O(log⁡p)O(\log p)O(logp)。 细节：当 bbb （分母）在模 ppp 的意义下为 000 时，这个分数在模 ppp 意义下显然是无意义的。特判输出无解即可。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 费马小定理求逆元相当快。例如求模 109+710^9+7109+7 的意义下的乘法逆元，数据量为 10710^7107 个数时，本机测试对比如下。 费马小定理 拓展欧几里得定理 不开优化 12.13500s 16.81400s 吸氧（O2）（比赛用氧） 11.88500s 14.78300s 吸臭氧（O3） 13.34900s 18.26300s 吸快氧（Ofast） 14.18300s 17.56700s 为什么有些氧气会有负优化？我也不知道。 不过费马小定理的局限性就在于 ppp 不是素数是无法使用。所以各种逆元求法都要学一下。接下来附测试代码。 TEST.H 费马小定理 拓展欧几里得定理 测试数据生成器

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. 这是脚注的内容，用于解释示例的含义。 ↩︎

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

不会真有人不用列表吧，一个一个列出来的： if(a%7==0) { cout<<"monday"; } 这种