互动｜CSP考试交流站，冲鸭！

🚀互动话题#4｜ #CSP考试交流站# 😎明天就是CSP考试啦！这个话题是咱们今天的交流小站，而且会持续一周（截止到 2024 年 9 月 26 日 24 点）哦 截止时间至10月7日24点，不管是考前紧急抱佛脚，还是考完来回顾，都可以畅所欲言。 📖考前最后一搏 1. 快速复习法 * 我打算再瞅一眼数据结构的重点，你们都在复习啥？是刷几道经典算法题找手感，还是死磕那些易错概念呢🧐 2. 解压小妙招 * 现在紧张到飞起，感觉心跳比代码跑得还快。你们有啥缓解紧张的好办法呀？是听音乐、做运动，还是自我催眠“我能行”😉 🎉考后回顾（考完可来分享） 1. 考试初印象 * 考完后，第一时间来吐槽下考试难度呀，是像打怪升级轻松过关，还是被虐得“体无完肤”呢🤪 2. 经验总结 * 分享下考场上的经验教训，哪些地方是下次要注意的，或者哪些策略超有效。 🎁 话题奖励 第一周奖励（5 名盲盒幸运奖）：留言时间为 9 月 20 日至 9 月 27 日。 ID 昵称 4010083 亚洲卷王 AK IOI 3251288 zhouty 2963055 社 jdymck 炎 3317115 熊二 2801735 胡译月^ 第二周奖励（3 名盲盒幸运奖）：留言时间为 9 月 28 日至 10 月 7 日。 ID 昵称 🎈奖励领取方式：AC君将通过站内私信获取收件信息。由于国庆期间处于节假日，所有奖励统一在国庆后发布。😉 大家快来畅所欲言呀😎💪

24年教师节周记

本帖预计将在24~28年中每年教师节这周更新，建帖的意义是记录美好生活。 9.10 首先要对我“吃键盘”这事说说我自己的看法。键盘是有寿命的，打字就会减少键盘的寿命，减少寿命又意味着键盘会逐渐消失（能量消耗），意为“吃”键盘；还有就是猫会挠或啃、咬键盘。 9.11 开学的第一场雨，挺难受的，这几天感冒咳嗽还得在教室开空调。咳第四天，没有好的迹象，同学中到是有不少留在家里了。该是羡慕还是嫉妒他们不用写作业？咳咳咳…… 开学一周时校内多了个打饭的地方，就是一个人守在口锅前，添的饭菜不好评价，因为我没吃，据同学所说还挺好吃，但那是给小学生吃的，所以……（我与语文课代表没吃，其他都有） 我：你是劳技课代表，要带好模范作用 劳技：带头抢饭的作用 我：你看人家语文课代表就没去，他带的模范作用难道不够好吗？ 劳技：（咀嚼声）（摇头） 我：你看人家语文课代表凭什么能当语文课代表，你怎么就不向人家学学？ 心理课代表：（噗嗤） 我：还有你这个地理课代表，人家语文课代表能当语文课代表一定有他的原因，你咋就不向人家学学？ 地理：语文课代表!@#$%^&* 心理：（噗嗤*2） 我：还有你，一个心理课代表难道就不是课代表了吗，一样要带好模范作用 语文：（被骂后跳出来） 语文：你看你，整天就知道吃吃吃 我：人家小朋友都瘦的骨架子似的，你还跟人家抢饭 语文：！@#￥%……&* 我：！@#￥%……&* 地理：我看你俩就是嫉妒我们吃得好，故意对着干 劳技：就是就是，你要就自己盛 我：都被你们抢完了我去干嘛 地理：又没抢你的 我：咋就没抢，我不也是小朋友 地理：…… 劳技：就你还小朋友，哪来一米七的小朋友 我：我说有就有 劳技：好好好…… 9.12 晚上咳嗽又犯了，喉咙有痰，挡着呼吸，还拼命咳，睡不好o(╥﹏╥)o 想问一下现在还有谁那是开空调上课的？反正我们是，还一天到晚开着，咳嗽老好不了…… 我们班的体育委员平时到看不出文质彬彬的，今天却拿出来个西游记……（本人对西游记没有任何恶意） 我：你染上西游记了？ 语文：染上西游记的后果你不知道吗？ 劳技：染上西游记的人都变得像吴承恩一样了！ 语文：吴承恩都洗了！你难道也要像他一样吗？ 我：你看你以前那么虎虎生风，现在居然染上西游记，你对得起你自己吗？ 劳技：口口生生说要当体委，你怎么就这么不争气呢？ 体委：我上早八！我就看个西游记咋地了？ 我：瞧你那样子都应该染上西游记半个小时了，居然还会顶嘴了！ 劳技：就是就是，这种害人的东西以后别看了，交给我们帮你保管吧！ 体委：好好好…… 其实有好多染上**，但是换汤不换药，就不一一举例了 9.13 马上就痊愈了，再也不用晚上翻来覆去的咳。也许是我在学校脏话讲太多了遭报应了，acgo上就不能说脏话。 我想问一下，调休不就是个法定“朝三暮四”吗？为什么在网络上被贬低成这样，大人都是周末加班上班加班时时加班的，调休好像也没多大影响啊？至于我们……我觉得是没什么影响 从开学到昨天我们班主任都是在办公室吃午饭，今天她却莫名其妙的出现在教室，导致我们开不了麦，但也有没被房主关麦的人在后门视觉死角闹了笑话（不好笑）： 教室：（除了咀嚼声以外死一样的寂静） 体委：（从后门进入）自从我发现那个隐藏加饭点……（90分贝）（发现老师） 老师：（走下讲台）哪里的隐藏加饭点，学校给的饭让你吃你就吃 …… 地理：楼下不是能打吗？我看好多人都去打了（100分贝）（发现老师） 老师：（看了看地理课代表）你上来一下 地理课代表后来就喜提了400左右检讨 …… 盛汤时我又遇到两个非本班人讨论我们班： 男1：为什么他们11班的可以下去打饭啊？ 我：（被提起注意）（抬头） 男2：这不就有个11班的？ 男1：你们班主任允许你们下去吗？ 我：我们主任不管，但不是所有人都去，我反正是不去的 男1：（打断我）你看也不是都去的 我：而且我是强烈反对去打饭的（劳技课代表走出来），你看他就是去添的，你看你，人家小学生长得骨瘦如柴的，你都长的一米七五了你还吃那么多，就不能让一让小盆友？ 劳技：？？？（莫名被骂了一遍） 9.14 1.终于离开校园了，上了六天学突然不上了莫名有些伤感，因为作业变多了，达到了之前的四倍,其中还得写一篇中秋中的一个事。虽然只要300字，但我总不能把ACGO写上来吧？暂时还没想好写什么，留给明天来做决定吧。 2.现在还是看不懂调休是什么操作，把每天都有的早饭掰一块分给偶尔的下午茶怎么就变好吃了？那放了大半天不就成预制菜了？ 3.我美味的信技课被下周的中秋节挤掉了（悲） 4.晚上睡觉我发现一个很奇怪但是有效防咳嗽的睡姿：把枕头卷成拱形，趴着然后把下巴枕在枕头上（手得抱住枕头），一晚上都没咳嗽，我的脑回路这新奇。 9.15 今天被复仇者_帅童（不加团队）在找一下AC君唬了一下，都跑去问AC君了结果他说闹着玩的，咳咳咳……给我气攻心疾，旧伤复发。下次有机会我等快递从广东到江苏经安徽时才告诉你我唬你的，哈哈哈哈哈哈哈哈哈哈咳咳咳咳咳咳咳咳。好了开个玩笑，也不能把我耍了一下就对别人这样嘛（貌似他也只有一个） 我对他没有任何恶意 都看到这了给我点点赞帮助我早日康复吧 9.16 本来想明天说得，但是昨天迫不及待说漏嘴了，今天再说一点：虽然标题是俩cake一起吃，但我其实只能吃一个cake，另一个不给买。 外面台风乌拉拉的吹，那房顶上还飘着层白花花的雾气，希望台风后天一个转弯闪现来无锡强行延长一天假😁 按我老家的规矩（保守的经典的中式思想），是没生日这个节的，我妈那边的所有人的生日都是我小姨承包的：舅父舅妈、外公外婆、表弟表妹，至于我……我生日都开学了，没那福气违背祖宗。那帖也不想一直放着，说不定哪天就删了。 9.17 终于是最后一天了，太不容易了，先啃一口birthmoon cake。 昨天台风下午4:31刮得断电，今天还得拿我妈热点来更新。那贝碧嘉提溜了一圈就走了，希望普拉桑赶在9.18七点前开始刮，这样就不用上学了。 16：00左右回电啦！更新个帖庆祝一下 下一章还在测试阶段，别点 <<上一章 ....................................................................................12..................................................................................下一章>>

互动｜#你有哪些收藏很久的宝藏网站#

🚀 互动话题来袭！#你有哪些收藏很久的宝藏网站# 🌠 芜湖，最近笑喷在#开学精神状态#话题里，看来大家都很擅长分享！🎉 为了给大家继续给发福利（bushi)，我们决定每周推出一个新话题。 🚀 vol.2 #你有哪些收藏很久的宝藏网站# 在日常编程或学习生活中，肯定悄悄收藏了一些超实用的“宝藏网站”。它们可能是某个小众但功能强大的在线工具，或是某个能让你效率翻倍的神奇网站。 📝 活动玩法： 1. 分享你的宝藏网站：在评论区留言，顺便简单介绍一下它的特色和你的推荐理由哦！ 2. 推荐范围：无论是学习资源、技术网站、在线工具，还是开发者社区、效率提升神器，统统都可以！ 3. 惊喜奖励：随机挑选5位同学，送出盲盒！🎁 ⏰ 活动时间： 现在就开始，截止到9月19日晚上24:00！ 🎁 获奖公布： ID 昵称 3131901 米哈游miHoYo 1921358 𝑇𝑖𝑘𝑎𝑧.泽 2461770 诡道哥 3710621 姜凌溪 3310442 181****9819

moon&birthday cake？

本人9.17生日，今年中秋又刚好在9.17，哈哈哈哈哈 阴历的闰月每19年一个轮回，大白话就是19年后我的生日与中秋又将重合 加急消息： 为了不让晚于9.17看到本帖的人太内疚，所以我准备搬出最后一包生日蜡烛： 9.17我公历生日，9.22是农历生日，只要在9.22前依然算生日祝福

ACGO 排位赛#13 - 预告&答疑

首先先预祝大家有一个快乐的国庆节（虽然我没有国庆节，这真是个悲伤的事情）。 关于比赛的任何问题，都可以在评论区回复我。数据合法性的验证代码也会在比赛开始后公布。 比赛答疑 1. 五张一样的牌算高牌，应该输出 High Card 2. 请仔细看题。 比赛预告 > "The view's not so good from inside the city, though…" > "Next time, then. I know a place where you can see them more clearly. I'll take you there in fifty years." > "Transformation starts with one change in a world of rules." > "Where chaos meets order, and everything finds its form." > "Cards aren't just about luck, are they?" > "No, it's about knowing the best combos." > "The strategy lies between the points." > "Exactly, it's all about the connections." > "Even small decisions matter in a world of possibilities." > "Yeah, it’s not about the center but where paths align." > "Territory isn't just about space." > "Right, it's about peace and balance." > "In the digital age, data isn't the only cost." > "True, energy powers the future… Macw's AI startups are all over that." ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 中文翻译如下： > “在城市里看风景不太好吧……” > “下次吧。我知道有个地方能看得更清楚。五十年后带你去。” > “在规则的世界里，变化从一个小小的转变开始。” > “当混乱与秩序交汇，一切都会找到自己的形态。” > “打牌可不仅仅是靠运气，对吧？” > “没错，关键在于你能组合出最好的牌。” > “胜负的关键其实在点与点之间。” > “正是如此，连接才是策略的核心。” > “在无限可能的世界里，连小决定都至关重要。” > “对，关键不是中心，而是所有道路汇聚的地方。” > “领地不仅仅是空间。” > “对，是真正的平衡与和平。” > “在数字时代，代价不仅是数据。” > “没错，能源才是推动未来的力量……Macw 的 AI 初创公司正是踩在这个浪潮上。” 数据合法性校验 T1 - 纪元流星雨 T2 - MARCONCATENATION T3 - TNT接力 T4 - 小丑牌 T5 - VERTEX VERSE T6 - 最优政府大楼选址 - 2 T7 - 乌龟养殖场 T8 - 数据中心能耗分析

原创猜谜-第二期

我看着家建起，那是曾属于我的辉煌 家的喜悦感染着我，兴奋不已 方寸之地，可容一身 万亩之地，可容几身？ 可依旧会迎来午夜，家被黑暗吞噬，家人陷入其中 我愣在原地，看着一切 突然，我清醒了过来，奔跑在黑暗中 站在高处，不知何做 清醒过晚，已时不早 灰暗的天，蒙了眼 一己之力，可敌几身？ 家的分裂，已成定局

CSP-J1试题+答案|速收!!!

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#C++小知识# 1.那些不同的排序算法

总所周知，排序是一种十分重要的知识 所以呢，我就想简单地讲一些常用的排序 若有遗漏，请补充，thanks 点赞过100更新下一期 (Macw07都点赞了，你不来看看) The First part（What is 排序）: 排序的定义： 简单来说，就是将一组数据（通常是一个列表、数组或任何可以遍历的集合）按照某种特定的顺序重新排列的过程。这个特定的顺序可以是从小 到大、从大到小、按照字母顺序、根据某个属性的值等等。排序的目的是让数据变得有序，便于后续的查找、分析或处理。 举个例子来说明排序的过程： 假设你有一堆乱序的卡片，每张卡片上写着一个数字。现在，你希望将这些卡片按照数字的大小顺序重新排列。这个过程就是排序。你可以通过比较相邻卡片的数字大小，然后交换它们的位置（如果它们的顺序不符合你的要求），重复这个过程直到所有的卡片都按照你想要的顺序排列好。 The second Part (不同的的排序): 1.冒泡排序（Bubble Sort) 定义：‌冒泡排序‌是一种简单的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大，则交换两数位置，这样，每一轮遍历都将当前未排序部分中的最大值“浮”到未排序部分的末尾。这个过程重复进行，直到整个数列都有序为止。由于越大的元素会逐渐“浮”到数列的顶端，因此这种排序算法被形象地称为冒泡排序。 视频展示：https://i-blog.csdnimg.cn/blog_migrate/8a300c4d3f82b20977174713fd7cb886.gif 代码： 2.选择排序（Selection Sort） 定义：‌选择排序是一种简单直观的排序算法，其基本思路是在未排序的序列中找到最小（或最大）元素，然后将其存放到序列的起始位置 视频展示：https://5b0988e595225.cdn.sohucs.com/images/20200513/312439ee96f0451d99b20685a054d2d2.gif 代码： 3.插入排序（Insertion Sort） 定义：插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 视频展示：https://img2018.cnblogs.com/blog/1757387/201910/1757387-20191017212916558-1582886173.gif 代码： 4.桶排序： 定义： 工作原理是将数组分 into 几个桶，每个桶分别排序，然后按顺序输出。它是一种稳定的排序算法，适用于一些特定的场景，例如数据分布均匀的情况。 图片展示：https://image-static.segmentfault.com/394/203/3942036120-81b89dadc641bc15_fix732 代码 5.计数排序 （桶排序的优化） 定义：‌简单描述就是，在一个有确定范围的整数空间中，建立一个长度更大的数组，如当输入的元素是 n 个 0 到 k 之间的整数时，建立一个长度大于等于k的数组。该数组的每一个下标位置的值代表了数组中对应整数出现的次数。根据这个统计结果，直接遍历数组，输出数组元素的下标值，元素的值是几， 就输出几次。 图片展示： https://bkimg.cdn.bcebos.com/pic/5366d0160924ab18d9ef57593bfae6cd7a890be6?x-bce-process=image/format,f_auto/quality,Q_70/resize,m_lfit,limit_1,w_536 代码： 6.归并排序 定义: 将已有序的子序列合并以得到完全有序的序列。归并排序的核心思想是将一个大问题分解为小问题，然后递归地将这些小问题合并起来以解决大问题。具体来说，归并排序的步骤包括： 1.分解‌：将数组分割成两个较小的子数组，直到每个子数组只包含一个元素。 2‌.合并‌：将两个已排序的子数组合并成一个大的有序数组。 补充：归并排序由约翰·冯·诺伊曼发明 视频与图片展示： https://i-blog.csdnimg.cn/blog_migrate/ea2dc22d7869f262a987fc78c2fed5dd.png#pic_center https://i-blog.csdnimg.cn/blog_migrate/4e5b705de8ab41ca710b3412fa3ee070.gif#pic_center 代码： 7.快速排序 定义： 将未排序元素根据一个作为基准的"主元"分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个子序列用类似的方法进行排序 视频展示： https://pic4.zhimg.com/v2-671296f1b5e64b40d75605460ef6ed3f_b.webp 代码 8.希尔排序： 核心思想： 先进行预排序，让数组接近有序； 直接插入排序 视频展示： https://img.jbzj.com/file_images/article/202205/2022051810363218.gif 代码： 8.堆排序： 定义： 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。 视频展示 堆排序 代码： The Third Part(不同排序的时间复杂度，空间复杂度，稳定性) 在C++中，常见的排序算法时间复杂度如下： 冒泡排序（Bubble Sort）：O(n^2) 选择排序（Selection Sort）：O(n^2) 插入排序（Insertion Sort）：O(n^2) 快速排序（Quick Sort）：平均O(n log n)，最坏O(n^2) 归并排序（Merge Sort）：O(n log n) 计数排序（Counting Sort）：O(n+k)（当k是数组中的最大值时） 桶排序（Bucket Sort）：O(n+k) 希尔排序（Shell Sort）：O(n log n) ~ O(n^2) 堆排序：O(nlogn) 在C++中，常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。下面是一些常见排序算法的空间复杂度： 冒泡排序（Bubble Sort）：O(1) 插入排序（Insertion Sort）：O(1) 选择排序（Selection Sort）：O(1) 快速排序（Quick Sort）：最坏情况O(n)，平均O(log n) 归并排序（Merge Sort）：O(n) 希尔排序：O(n^2) 桶排序: O(n^2) 计数排序：O(n + k) k是最大位数 堆排序：O(n) 稳定性： 不稳定：快速排序，希尔排序，选择排序,堆排序 稳定：剩余的 好啦，以上的排序，你用过几个呢？ （持续更新中...） 第二集已出，麻烦看一下 第二集

互动｜#十一去哪儿玩#

互动｜#十一去哪儿玩#😎 🎈国庆假期已到来！此刻的你正在哪里尽情玩耍呢？是在远方的美景中沉醉，还是在周边的欢乐中徜徉？ 😃快来分享你的游玩实况吧！💖 一、远方的精彩：如果你正在远方旅行，分享你邂逅的美丽风景📍、品尝到的特色美食🍰、旅途中的有趣故事……让我们一同感受远方的魅力。 二、周边的惊喜：若是在周边游玩，也可以分享你发现的宝藏地点、参与的趣味活动或者偶遇的美味小吃……让大家一起发现身边的美好。 💬快来踊跃发言，抽3名送周边！

当01背包学会变形术

本文拥有MACW07,アイドル(作者曰：致敬传奇排位出题王)，SJZ08和AC君的点赞，含金量极高，确定不来看看吗？ -1.在这篇文章之前 01背包，相信大家都会（不会请自学）。 然而，在アイドル的排位赛中，总有那么几道01背包，在模板上加一些奇妙的东西使其变得非常不可读 所以，饱受火星背包折磨的我，将做出此文，为抵抗01变式做出贡献 0.前置知识 01背包，众所周知，不会就去上网学 1.最初的起点——01背包模板 01背包第一形态：模板形态 【背包】01背包(优化) 题目描述 一个旅行者有一个最多能装 C 的背包，现在有 n 件物品，它们的重量分别是 w1，w2，...,wn,w_1，w_2，...,w_n,w1 ，w2 ，...,wn ,它们的价值分别为v1,v2,...,vn，v_1,v_2,...,v_n，v1 ,v2 ,...,vn ，每件物品都可以选择装入背包或者不装入，求旅行者能获得最大总价值。 输入格式 第 1 行：两个整数，C (背包容量，0 < C ≤ 30000) 和 N (物品数量，0 < N ≤ 10000)； 第 2~N+1行：每行二个整数 wi，viw_i，v_iwi ，vi ，表示每个物品的重量和价值。 输出格式 仅一行，一个数，表示最大总价值。 样例 #1 样例输入 #1 样例输出 #1 经典01背包，当然要套最经典的模板 复杂度也是经典的O(nm) CODE: 2.当N开始变小的时候 当n开始变小的时候，就说明你要做火星背包全家桶了 火星背包I 01背包第二形态：N小余极形态 这题观察到我们的wi,vi,mw_i,v_i,mwi ,vi ,m都特别大，显然最终的时间复杂度肯定只能带n了 咋办？？ 不急，是时候掏出黑科技——折半搜索了（选学，因为我也不懂） 时间复杂度为O(2n2)O(2^{\frac{n}{2}})O(22n ) CODE: 火星背包II 01背包第三形态：火星式逆转形态 这题一看n和viv_ivi 都小，其余的我们承受不住。所以显然时间复杂度显然只能带n和viv_ivi 。 不妨想一下，你n和viv_ivi 都小，我们是不是可以反过来，直接枚举最后的答案然后判断答案是否可行呢？ 这么一思索，脑子里便能瞬间变出一个dp[i]呢（dp[i]指在想让最后价值变为i时的最小重量） 在思索一下，是不是dp[0]=0呢 这边界和公式都有了,接下来就交给代码了 时间复杂度为O(n∑i=1nvi)O(n\sum_{i=1}^nv_i)O(n∑i=1n vi ),最大1e8,勉强卡常过去 CODE 3.当N开始变大的时候 01背包第4形态：多重01形态 显然，你就要去写一些思维题了 这道题比较有价值，建议思考一下再看题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解： 1.直觉 你在刚看到这题的反应估计是：这不 01 背包模板题吗，为啥会在绿题？ 于是，你就高高兴兴的把 01 背包的模板修改了一下，放了上去。 结果就会这样 。 也是在这时，你看到了数据： n,m≤105n,m \le 10^5n,m≤105 。 所以说，这题用传统 01 背包的 O(nm)O(nm)O(nm) 还真做不出来。 然而正在你苦苦思索时，你一看 aia_iai 和 bib_ibi 的数据。 0≤ai,bi≤100\le a_i,b_i \le 100≤ai ,bi ≤10。 2.思路 aia_iai 和 bib_ibi 这么小，所有男家丁的状态最多只有 11×1111\times1111×11 多种，nnn 又很大，肯定会有重复的情况，于是我们就可以定义一个二维数组 sss 来保存当前状态的男家丁有多少个，这样子我们就得到了一个多重背包问题。 2.1二进制优化 然而普通多重背包的时间复杂度是 O(n×m×(背包个数))O(n \times m \times(背包个数))O(n×m×(背包个数))，显然是会超时间的。所以说还得用到二进制优化，把时间复杂度优化为 O(n×m×log⁡2背包个数)O(n\times m \times \log_2背包个数)O(n×m×log2 背包个数)。 ⋇\divideontimes⋇:这里的 nnn 最大为 10510^5105，mmm 最多为 11×1111\times1111×11， log⁡2\log_2log2 (背包个数) 顶多也就 101010 多一点点地样子，开个O2时间勉强能卡过。 3.MYCODE\MATHBF{3.MYCODE}3.MYCODE ： //抄袭可耻！！！ 4.探寻本质 看了这么多题目，相信你也发现了： 1.01变式最重要的就是挑软柿子捏，找到小的数据，根据这个想出对应的思路 2.没有小数据的背包一般都不在考背包 所以，“山重水复疑无路，柳暗花明又一村”，只要它还是背包，就一定是有一个比较简单的解的（火星背包I除外）。 5.结语 看到这里的，请按照以下操作进行： 1.@AC君：精选置顶 2.其他：点赞，评论（发个ding都行） byebye~